Обзор алгоритмов сжатия без потерь

Метод Хаффмана

Идея метода

Метод сжатия информации на основе двоичных кодирующих деревьев был предложен Д. А. Хаффманом в 1952 году задолго до появления современного цифрового компьютера. Обладая высокой эффективностью, он и его многочисленные адаптивные версии лежат в основе многих методов, используемых в алгоритмах кодирования.

Идея алгоритма: зная вероятность вхождения символов в сообщение, можно описать процедуру построения кодов переменной длинны состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину. Динамический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана.

Алгоритм

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в ожидаемое сообщение.
2. Выбираются 2 свободных узла дерева с наименьшими весами.
3. Создается родитель с весом равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а двое его потомков удаляются из этого списка.
5. Одной дуге выходящей их родителя ставится в соответствие бит 1, другой – бит 0.
6. 6. Далее пункты повторяются, начиная со второго, до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Кодирование Хаффмана

Допустим у нас есть таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами – D и E. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6=11. Затем узлы D и E удаляются из списка свободных. Узел D соответствует ветви 0 родителя, узел E – ветви 1. На следующем шаге то же происходит с узлами B и C, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы B и C удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рисунке.

На следующем шаге "наилегчайшей" парой оказываются узлы B/C и D/E. Для них еще раз создается родитель, теперь уже с весом 24. Узел B/C соответствует ветви 0 родителя, D/E – ветви 1. На последнем шаге в списке свободных остается только 2 узла – это A и узел (B/C)/(D/E). В очередной раз создается родитель с весом 39, и бывшие свободные узлы присоединяются к разным его ветвям. Поскольку свободным остается только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Дерево представлено на рисунке.

Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева. Полученная таким образом последовательность битов является кодом данного символа, записанная в обратном порядке. Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом:

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения A закодирован наименьшим количеством битов, а наиболее редкий символ E – наибольшим.

Классический алгоритм Хаффмана имеет один существенный недостаток. Для восстановления содержимого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что приводит к увеличению размеров выходного файла. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и дерева), другого для собственно кодирования.