скачать doc
1.9. Динамическое кодирование по Хаффману
Рассмотренный (статический) метод Хаффмана имеет некоторые недостатки, влияющие на эффективность его применения, например:
двухпроходность алгоритма (сначала вычисляются веса
, затем строится дерево (код) Хаффмана);
необходимость передавать кодовое дерево вместе с последовательностью закодированных сообщений.
Этих недостатков лишен так называемый динамический (однопроходный) метод Хаффмана, в котором кодирование осуществляется «на лету». При этом используется динамически изменяющееся дерево Хаффмана (изменяющийся префиксный код). Кодировщик и декодировщик работают в этом случае синхронно: начиная с пустого дерева, они строят одно и то же дерево Хаффмана, причём кодировщик – по последовательности сообщений, а декодировщик – по последовательности кодовых слов. Можно представить этот процесс в виде схемы, изображенной на рис.1.х (здесь ДХ(i) – дерево Хаффмана, построенное по последовательности символов (сообщений)
).
ci
ai
Кодировщик выполняет две основные операции: 1) получение кодового слова ci для очередного символа ai по текущему дереву Хаффмана ДХ(i 1); 2) перестройку текущего ДХ(i 1) в новое ДХ(i) с учётом поступившего символа ai. Декодировщик также выполняет две операции: 1) получение символа ai для очередного кодового слова ci по текущему дереву Хаффмана ДХ(i 1); 2) перестройку текущего ДХ(i 1) в новое ДХ(i) с учётом символа ai. Важно, что и кодировщик, и декодировщик перестраивают дерево Хаффмана по одному и тому же алгоритму.
Перейдём к рассмотрению алгоритма перестроения дерева Хаффмана.
Пусть дерево Хаффмана строится так, что левый сын имеет вес не больший, чем правый (эта свобода выбора в статическом методе Хаффмана имеется, см. 1.4). Кроме того, как мы знаем, дерево Хаффмана не единственно. Пусть, например, заданы веса W4 = (5, 4, 3, 2). Можно построить два дерева Хаффмана, показанных на рис. 1.хх (одно из них с минимальной высот
ой – на рисунке б). Листья дерева, соответствующие символам алфавита, изображены на рисунке квадратами, а внутренние узлы кругами. Внутри узлов помещены их веса. Дерево а удобно для добавления 1, при этом w1 заменяется на w1 +1 (6 5 + 1) и структуру дерева корректировать не надо. Дерево б удобно для добавления 4, при этом w4 заменяется на w4 +1 (3 2 + 1) и структуру дерева корректировать тоже не надо. Этот пример показывает, что было бы полезным в случае необходимости уметь преобразовывать различные деревья Хаффмана друг в друга в зависимости от добавляемого символа. Обратим внимание, что для деревьев а и б при их обходе узлов слева направо и снизу вверх по слоям (ярусам) получается одна и та же последовательность весов (2, 3, 4, 5, 5, 9, 14). Эта последовательность весов соответствует порядку взвешенного сочетания узлов (т. е. порядку выбора минимальных весов и порождению суммарного веса) в алгоритме Хаффмана.
Отметим, что дерево Хаффмана является строго бинарным и содержит ровно 2n 1 узлов, n из которых являются листьями. Действительно, пусть в строго бинарном дереве содержится n листьев (внешних узлов) и s внутренних узлов. Тогда число исходящих из внутренних узлов веток есть 2s. Подсчет этих же веток, как входящих во все узлы дерева, кроме корня, дает n + s 1. Т. о. 2s = n + s 1. Отсюда следует s = n 1 и общее число узлов n + s = 2n 1.
В общем случае неубывающая последовательность весов x1 x2 x3 … x2n 1, получаемых в порядке взвешенного сочетания узлов в алгоритме Хаффмана, инвариантна для всех деревьев Хаффмана с заданными весами w1 w2 … wn 1 wn. При этом
, причем внутренние узлы имеют веса x1 + x2, x3 + x4,…, x2n 3 + x2n 2 = x2n 1. Назовём строго бинарное дерево упорядоченным, если оно удовлетворяет условиям:
n внешних узлов (листьев) получили веса (w1, w2,…, wn) в каком-то порядке, и каждый внутренний узел получил вес, равный сумме своих сыновей;
2n 1 узлов (внутренних и внешних) можно перечислить в такой последовательности (y1, y2,…, yn 1, yn), что
если xi вес узла yi, то x1 x2 … x2n 1;
узлы y2j 1 и y2j братья (сыновья одного отца); в случае наличия нулевых весов отец этих узлов не должен предшествовать сыновьям в последовательности.
Можно показать по индукции [Кнут, статья], что такое упорядоченное дерево может быть построено алгоритмом Хаффмана. Тот факт, что дерево Хаффмана является упорядоченным деревом, был обоснован ранее.
Для динамической перестройки дерева Хаффмана существенным является то соображение, что из различных деревьев Хаффмана можно выбрать такое, которое не изменится при модификации w w +1. Такое дерево обладает следующим свойством. Для наглядности воспользуемся рисунком.
Пусть требуется изменение веса внешнего узла
(w w +1). Путь от листа к корню обозначен здесь как 
. Если 
, то увеличение на 1 веса узла и последующее увеличение веса 
его отца 
также на 1 не нарушит свойство упорядоченности последовательности на участке 
. Если неравенство 
выполняется для всех 
, то приращение на 1 всех весов на пути от к корню 
не изменит свойство упорядоченности дерева, и для такого дерева не потребуется перестройки. Если же в дереве отмеченное свойство (набор неравенств) по нужному пути к корню не выполняется, то его выполнение нужно обеспечить, переставляя (перевешивая) узлы с равными весами.Проиллюстрируем это примером. Пусть W = (11, 6, 5, 5, 3, 2). Рассмотрим дерево Хаффмана на рис. *, где узлы помечены своими весами и индексами от 1 до 11 в упорядоченной последовательности (2, 3, 5, 5, 5, 6, 10, 11, 11, 21, 32), которая есть инвариант дерева Хаффмана.
Е
сли речь идет об увеличении на 1 веса 3 в узле с индексом 2, то путь к корню определяется последовательностью индексов (2, 4, 7, 10, 11), и требуемое неравенство нарушается уже для узлов с индексами 4 и 5. После перевешивания этих узлов получим дерево Хаффмана с тем же инвариантом (2, 3, 5, 5, 5, 6, 10, 11, 11, 21, 32).
В этом дереве путь от листа к корню задается последовательностью индексов (2, 5, 8, 10, 11). Теперь требуемое неравенство нарушается для узлов 8 и 9. После их перевешивания получим дерево Хаффмана, изображенное на рис.**.
Это дерево также имеет инвариант (2, 3, 5, 5, 5, 6, 10, 11, 11, 21, 32) и теперь на всем пути (2, 5, 9, 11) к корню требуемые неравенства выполнены. Окончательно перестроенное дерево с измененными теперь уже узлами имеет следующий вид.
В итоговом алгоритме перестройки дерева Хаффмана процесс приращения веса текущего узла на пути от листа к корню можно совместить с перевешиванием узлов. Если ещё до увеличения веса текущего узла за ним в упорядоченной последовательности следуют несколько равных ему весов, то обмен следует сделать с последним из узлов этой подпоследовательности равных весов, а затем увеличить вес текущего узла на 1, после чего таким же образом двигаться далее к корню.
Рассмотрим пример работы динамического алгоритма Хаффмана.