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

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

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

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

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

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

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

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

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

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

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

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

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