| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Для новичков > Алгоритм Хаффмана (Hufmann Algorithm) |
| Автор: w32blaster 2.12.2008, 21:00 |
| Господа, здравствуйте! Мне нужно написать по универу прогу на С, реализующая архиватор по алгоритму Хаффмана. Я вообще специальизировался на Яве и на РНР, но вот С меня поставил в тупик. Бьюсь уже почти месяц, а время поджимает.... Я конечно же не претендую на полное разъяснение, но, может, кто-то где-то делал и осталась прога? Последняя палка в колёсах перед дипломкой....  Спасибо заранее... email [email protected] |
| Автор: Acer 2.12.2008, 21:07 |
| http://algolist.manual.ru/compress/standard/huffman.php http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A5%D0%B0%D1%84%D1%84%D0%BC%D0%B0%D0%BD%D0%B0 |
| Автор: w32blaster 16.12.2008, 11:13 |
| Ok, я получил последовательность Хаффмана, то есть последовательность 0 и 1. Создал необходимое дерево. Но препод сказал, что этого мало - прога должна обязательно сжимать файлы и распаковывать. Вот. Как я читал во всех мануалах, нужно к полученной последовательности 0001100101010 ещё как-то прибавить само дерево, которое будет являться как бы "каротой", по которой можно будет расшифровать архив. Вот, собсна, и вопрос: как это сделать? Моё дерево я храню в массиве, где есть каждый элемент с его "Ид", "ПарентИд", значением "лево/парво" и "лист/не лист". По нему я могу сделать двоичную последовательность и, я надеюсь, в будущем смогу обратно восстановить. Но это в теории. А вот на практике я совсем не предстваляю, как это сделать..... :( В Инете во всех статьях повествование оканчивается на последовательности и всё.... жжжесть... из всего курса только один предмет загнал меня в тупик.... У кого-нить есть идеи, хотя б на словах? Или с примером кода? Благодарен за любую помощь. |
| Автор: MaXL 17.12.2008, 08:42 | ||
Ну самый просто вариант, это записывать это дерево в файл, перед шифрованными данными. А в самое начало файл писать "заголовок", т.е. размер этого дерева. И потом ты легко сможешь получить данные с деревом, ну и собственно саму упакованную информацию.
ну можно попробовать ничего не кодировать в двоичном виде, а просто подряд писать элементы с первого до последнего. Ид, можно не хранить, он и будет порядковым номер в этой последовательности. Под "ParentId" можно отвести один байт(если у тебя в алфавите 255 символов). под само значение опять таки один байт, зависит от алфавита ну и лево права снова один байт. вот собственно и всё. Размер массива хранить в заголовке. |
| Автор: Бонифаций 17.12.2008, 09:57 |
| когда то давно понадобилось написать подобную штуку, только с алгоритмом Шеннона-Фано.. Ну не важно. Там, вместо того, чтобы хранить дерево в файле. мне показалось проще хранить в результирующем файле статистику букв исходного файла. То есть (буква, число сколко раз встречалась)* , получалось компактенее. А дерево при расшифровке просто воссоздавал по этой статистике. |