Материал: 1_9ДХафф

36

«Сцепляется с 1.8»

1.9. Динамическое кодирование по Хаффману

Рассмотренный (статический) метод Хаффмана имеет некоторые недостатки, влияющие на эффективность его применения, например:

• двухпроходность алгоритма (сначала вычисляются веса , затем строится дерево (код) Хаффмана);

• необходимость передавать кодовое дерево вместе с последовательностью закодированных сообщений.

Этих недостатков лишен так называемый динамический (однопроходный) метод Хаффмана, в котором кодирование осуществляется «на лету». При этом используется динамически изменяющееся дерево Хаффмана (изменяющийся префиксный код). Кодировщик и декодировщик работают в этом случае синхронно: начиная с пустого дерева, они строят одно и то же дерево Хаффмана, причем кодировщик – по последовательности сообщений, а декодировщик – по последовательности кодовых слов. Можно представить этот процесс в виде схемы, изображенной на рис. 1.1 (здесь ДХ(i) – дерево Хаффмана, построенное по последовательности символов (сообщений) ).

c_i

Кодировщик выполняет две основные операции: 1) построение кодового слова c_i для очередного символа a_i по текущему дереву Хаффмана ДХ(i  1); 2) перестройку текущего ДХ(i  1) в новое ДХ(i) с учетом поступившего символа a_i. Декодировщик также выполняет две операции:

1) восстановление символа a_i по очередному кодовому слову c_i и по текущему дереву Хаффмана ДХ(i  1); 2) перестройку текущего ДХ(i  1) в новое ДХ(i) с учетом символа a_i. Важно, что и кодировщик, и декодировщик перестраивают дерево Хаффмана по одному и тому же алгоритму.

Перейдем к рассмотрению алгоритма перестроения дерева Хаффмана.

Пусть дерево Хаффмана строится так, что левый сын имеет вес не больший, чем правый (эта свобода выбора в статическом методе Хаффмана имеется, см. 1.4). Кроме того, дерево Хаффмана, вообще говоря, не единственно. Пусть, например, заданы веса W₄ = (5, 4, 3, 2). Можно построить 2 дерева Хаффмана, показанных на рис. 1.2 (одно из них с минимальной высотой – на рис. 1.2, б).

Листья дерева, соответствующие символам алфавита, изображены на рисунке квадратами, а внутренние узлы  кругами. Внутри узлов помещены их веса. Дерево а удобно для добавления ₁, при этом w₁ заменяется на w₁ + 1 (6  5 + 1) и структуру дерева корректировать не надо. Дерево б удобно для добавления ₄, при этом w₄ заменяется на w₄ + 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.

В общем случае неубывающая последовательность весов x₁  x₂  x₃  …  x_2n 1, получаемых в порядке взвешенного сочетания узлов в алгоритме Хаффмана, инвариантна для всех деревьев Хаффмана с заданными весами w₁  w₂  …  w_n  1  w_n. При этом , причем внутренние узлы имеют веса x₁ + x₂, x₃ + x₄, …, x_2n 3 + x_2n 2 = x_2n 1.

Назовем строго бинарное дерево упорядоченным, если оно удовлетворяет условиям:

1. n внешних узлов (листьев) получили веса (w₁, w₂, …, w_n) в каком-то порядке, и каждый внутренний узел получил вес, равный сумме своих сыновей;

2. 2n  1 узлов (внутренних и внешних) можно перечислить в такой последовательности (y₁, y₂, …, y_n  1, y_n), что если x_i  вес узла y_i, то x₁  x₂  …  x_2n 1; узлы y_2j 1 и y_2j  братья (сыновья одного отца); при наличии нулевых весов отец этих узлов не должен предшествовать сыновьям в последовательности.

Можно показать по индукции [20], что такое упорядоченное дерево может быть построено алгоритмом Хаффмана. Тот факт, что дерево Хаффмана является упорядоченным, был обоснован ранее.

Для динамической перестройки дерева Хаффмана существенным является то соображение, что из различных деревьев Хаффмана можно выбрать такое, которое не изменится при модификации веса w  w + 1. Такое дерево обладает описанным далее свойством. Для наглядности воспользуемся рисунком.

П усть требуется изменить вес внешнего узла (w  w + 1). Путь от листа к корню обозначен здесь как . Если , то увеличение на 1 веса узла и последующее увеличение веса его отца также на 1 не нарушит свойство упорядоченности последовательности на участке . Если неравенство выполняется для всех , то приращение на 1 всех весов на пути от к корню не изменит свойство упорядоченности дерев и для такого дерева не потребуется перестройки. Если же в дереве отмеченное свойство (набор неравенств) по нужному пути к корню не выполняется, то его выполнение нужно обеспечить, переставляя (перевешивая) узлы с равными весами.

Проиллюстрируем это примером. Пусть W = (11, 6, 5, 5, 3, 2). Рассмотрим дерево Хаффмана на рис. 1.3, где узлы помечены своими весами и ин-

дексами от 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, после чего таким же образом двигаться далее к корню.

Рассмотрим пример работы динамического алгоритма Хаффмана. Кодируется текст АБРАКАДАБРА!, содержащий 12 символов, включая специальный символ !, означающий конец текста. В строящемся дереве Хаффмана будет использоваться специальный узел нулевого веса, отображающий все символы алфавита, включая символ !, не встретившиеся до сих пор. Будем обозначать этот узел как !. Первые вхождения символов кодируются по текущему дереву Хаффмана кодом узла !, за которым следует код собственно нового символа в специальной кодировке. Рассмотрим ее далее отдельно, а пока обозначим такой код подчеркиванием символа.

Перед началом кодирования и передатчик (кодировщик), и приемник (декодировщик) знают лишь используемый алфавит (набор элементарных сообщений), в том числе количество символов алфавита (это важно для кодирования первых вхождений). Рассмотрим последовательно все 12 шагов кодирования: А₁Б₂Р₃А₄К₅А₆Д₇А₈Б₉Р₁₀А₁₁!₁₂.

1) Изначально все веса равны нулю, поэтому первая буква А кодируется непосредственно специальным кодом А, а текущее дерево Хаффмана становится таким: