Деревья хаффмана - как с ними работать

[Sameone]

Не надо заниматься лесоводством - оставь это тем, кто пишет умные математические книжки. В программировании ты можеш выполнять действия, которых нет в математике (например читать память или писать в неё), поэтому в жизни всё проще. В методе Хаффмана непосредственно значения вероятностей отдельных символов напрямую использовать не обязательно, достаточно чтобы i-й символ был маловероятнее i-1го.
Пусть у тебя есть входной текст (последовательность символов, которую надо сжать) известной длины и список использованных в нём символов, отсортированных по убыванию их встречаемости в тексте. Тогда для всех символов входного текста, по порядку от первого до последнего:
1)читаешь символ из входного текста и находиш его в списке символов;
2)если это самый первый элемент, пишеш в выходной текст (закодированный) "0" и переходиш к обработке следующего символа входного текста;
3)иначе создаёш битовую строку длиной N, где N - номер символа в списке, но не длиннее чем M - номер предпоследнего элемента списка. Создаваемая битовая строка состоит из чередующихся "1" и "0", начинается с "1" (т. е. имеет вид 1010101...);
4)если N<>M, инвертируеш последний бит в последовательности (т. е. теперь битовая строка заканчивается двумя одинаковыми битами);
5)записываеш битовую строку в выходной текст.
ПРИМЕЧАНИЯ:
На 4-м шаге можно инвертировать бит для всех элементов списка кроме предпоследнего, но тогда заархивированный файл не сможет быть правильно прочитан архиватором-лесоводом (написанным математиком). Метод Хаффмана максимально эффективен если вероятность нахождения символов убывает как 1/(2^N), где N - номер символа в упорядоченном по убыванию списке. Если отличие отой этой зависимости велико, результат далёк от оптимального. Поэтому метод Хаффмана считается устаревшим и заменяется арифметическим кодированием, которое никогда не хуже, но в неудобных для метода Хаффмана случаях может быть в разы эффективнее. Подробнее об арифметическом кодировании смотри http://compression.ru/book/pdf/compr...ll_scanned.pdf с35-43 - там даже есть образцы реализации компрессора и декомпрессора (правда, на Си). Книга выложена её авторами на их собственном сайте.

[Advertiser]