Динамическое кодирование неравномерными кодами
статистических характеристик источника сообщений, в ходе которого
вычисляются оценки исходных вероятностей сообщения и производится
соответствующая модификация кодового дерева Хаффмена. В связи с
непрерывным изменением кодового дерева этот процесс получил название
динамического кодирования Хаффмена. Очевидно, что для правильного
восстановления сжатых данных, декодер также должен непрерывно
“учиться” наряду с кодером, осуществляя синхронное изменение кодовой
таблицы на приемной стороне. Для обеспечения синхронности процессов
кодирования и декодирования кодер выдает символ в несжатом виде, если
он впервые появился на выходе источника, и отмечает его на кодовом
дереве. При повторном появлении символа на входе кодера он передается
неравномерной кодовой комбинацией, определяемой позицией символа на
текущем кодовом дереве. Кодер корректирует дерево Хаффмена
увеличением частоты передачи символов, которые уже введены в дерево,
или наращивает дерево, добавляя в него новые узлы.
Важнейшим условием, которое должно соблюдаться при
модификации кодового дерева, является сохранение свойств
хаффменовского дерева. Для формулирования этих свойств обратимся еще
раз к алгоритму построения оптимального кода Хаффмена (п.3.2). При
статическом кодировании символы размещаются в списке в
невозрастающем порядке весов (вероятностей). Затем производится
объединение двух узлов наименьшего веса W
i
, W
j
и замена их внутренним
узлом с весом, равным сумме исходных весов W
i
+W
j
. Вновь образованный
узел размещается в списке таким образом, чтобы не нарушался порядок
расположения узлов по весам. Этот процесс повторяется до тех пор, пока в
списке не останется один, так называемый корневой, узел.
Рассмотрим еще раз примеры построения деревьев оптимального
кода Хаффмена (рис.3.3 и 3.4) и проанализируем их свойства. Как видно из
рисунков, узлы дерева расположены в неубывающем порядке их весов при
обходе дерева от крайнего нижнего узла к корню слева направо и снизу
вверх. В связи с тем, что узлы с весами W
i
и W
j
объединяются попарно, то
на одном уровне не может быть меньше двух узлов, причем пара узлов
является дочерней, так как имеет общий родительский узел, вес которого
равен сумме весов дочерних узлов. Нетрудно убедиться, что если при
построении дерева предположить, что дочерний узел с большим весом
соединен нулевой ветвью, а с меньшим - единичной, то хаффменовское
дерево остается упорядоченным по возрастанию весов при движении от
нижнего узла к корню по уровням справа налево.
При построении кодовых деревьев и их модификации
осущестляется нумерация узлов с первого до (2m–1)-го в порядке
увеличения их весов. Первый номер присваивается узлу с минимальным
весом. Здесь m - число символов алфавита источника. На рис.4.1 показано