2.5. Модификации кодов Хафмана

Классический алгоритм Хафмана относится к двухпроходным, т. е. требует вначале набора статистики по символам и сообщениям, а потом описанных выше процедур. Это неудобно на практике, поскольку увеличивает время обработки сообщений и накопления словаря. Чаще используются однопроходные методы, в которых процедуры накопления и кодирования совмещаются. Такие методы называются ещё адаптивным сжатием по Хафману [48].

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

После введения очередного символа входной последовательности пересматривается кодовое дерево: пересчитываются веса вершин и при необходимости вершины переставляются. Правило перестановки вершин следующее: веса нижних вершин наименьшие, причём вершины, находящиеся слева на графе, имеют наименьшие веса.

Одновременно вершины нумеруются. Нумерация начинается с нижних (висячих, т. е. не имеющих детей) вершин слева направо, потом переносится на верхний уровень и т.д. до нумерации последней, исходной вершины. При этом достигается следующий результат: чем меньше вес вершины, тем меньше её номер.

Перестановка осуществляется в основном для висячих вершин. При перестановке должно учитываться сформулированное выше правило: вершины с большим весом имеют и больший номер.

После прохождения последовательности (она называется также контрольной или тестовой) всем висячим вершинам присваиваются кодовые комбинации. Правило присвоения кодов аналогично вышеизложенному: количество разрядов кода равно количеству вершин, через которые проходит маршрут от исходной до данной висячей вершины, а значение конкретного разряда соответствует направлению от родителя к «ребёнку» (скажем, переход влево от родителя соответствует значению 1, вправо – 0).

Полученные кодовые комбинации заносятся в память устройства сжатия вместе с их аналогами и образуют словарь. Использование алгоритма заключается в следующем. Сжимаемая последовательность символов разбивается на фрагменты в соответствии с имеющимся словарём, после чего каждый из фрагментов заменяется его кодом из словаря. Не обнаруженные в словаре фрагменты образуют новые висячие вершины, приобретают вес и также заносятся в словарь. Таким образом формируется адаптивный алгоритм пополнения словаря.

Для повышения эффективности метода желательно увеличивать размер словаря; в этом случае коэффициент сжатия повышается. Практически размер словаря составляет 4 – 16 килобайт памяти.

Проиллюстрируем приведённый алгоритм примером. На рис. 2.12 приведена исходная диаграмма (её называют также деревом Хафмана). Каждая вершина дерева показана прямоугольником, в котором вписаны через дробь две цифры: первая означает номер вершины, вторая – её вес. Как можно убедиться, соответствие весов вершин и их номеров выполняется.

Рис. 2.11. Исходное дерево кода Хафмана	Рис. 2.12. Изменение весов

Предположим теперь, что символ, соответствующий вершине 1, в тестовой последовательности встретился вторично. Вес вершины изменился, как показано на рис. 2.13, вследствие чего правило нумерации вершин нарушено. На следующем этапе меняем расположение висячих вершин, для чего меняем местами вершины 1 и 4 и перенумеровываем все вершины дерева. Полученный граф приведён на рис. 2.14. Далее процедура продолжается аналогично.

Рис. 2.13. Перестановки в дереве Хафмана

Следует помнить, что каждая висячая вершина в дереве Хафмана соответствует определённому символу или их группе. Родитель отличается от детей тем, что группа символов, ему соответствующая, на один символ короче, чем у его детей, а эти дети различаются последним символом. Например, родителю соответствуют символы «кар»; тогда у детей могут быть последовательности «кара» и «карп».

Приведённый алгоритм не является академическим и активно используется в программах-архиваторах, в том числе и при сжатии графических данных (о них речь пойдёт ниже).