Описание программы кодирования Хаффмана

В любом случае, декодер должен прочесть начало файла и построить дерево Хаффмана для алфавита. Только после этого он может читать и декодировать весь файл. Алгоритм декодирования очень прост. Следует начать с корня и прочитать первый бит сжатого файла. Если это нуль, следует двигаться по нижней ветке дерева; если это единица, то двигаться надо по верхней ветке дерева. Далее читается второй бит и происходит движение по следующей ветке по направлению к листьям. Когда декодер достигнет листа дерева, он узнает код первого несжатого символа (обычно это символ ASCII). Процедура повторяется для следующего бита, начиная опять из корня дерева.

Процедура для алфавита из 5 символов. Входная строка « » кодируется последовательностью 1001100111. Декодер начинает с корня, читает первый бит «1» и идет вверх. Второй бит «0» направляет его вниз. То же самое делает третий бит. Это приводит декодер к листу  . Получен первый несжатый символ. Декодер возвращается в корень и читает 110, движется вверх, вверх и вниз и получает символ  , и так далее.

Рис. 3. Коды Хаффмана с равными вероятностями.

 

На рис.3а представлено множество из пяти символов с их вероятностями, а также типичное дерево Хаффмана. Символ А возникает в 55% случаев и ему присваивается однобитовый код, что вносит вклад в   в среднюю длину. Символ Е возникает лишь в 2% случаев. Ему присваивается код длины 4, и его вклад равен  . Тогда средняя длина кода равна   бит на символ.

Удивительно, но тот же результат получится, если сложить значения вероятностей четырех  внутренних узлов кодового дерева:  . Это наблюдение дает простой способ вычисления средней длины для кодов Хаффмана без использования операции умножения. Надо просто сложить значения внутренних узлов дерева. Табл. 3 иллюстрирует, почему этот метод будет работать.

 

0.05 =		= 0.02 + 0.03
0.20 =	0.05 + 0.15	= 0.02 + 0.03 + 0.15
0.45 =	0.20 + 0.25	= 0.02 + 0.03 + 0.15 + 0.25
1.00 =	0.45 + 0.55	= 0.02 + 0.03 + 0.15 + 0.25 + 0.55

Табл.3. Состав узлов.

(В таблице  внутренние узлы выделены.) В левом  столбце выписаны величины всех  внутренних узлов. В правых  столбцах показано, как величины  складываются из величин предыдущих  узлов и из величин листьев.  Если сложить числа в левом  столбце, то получится 1.7, а  складывая числа в остальных столбцах, убеждаемся, что это число 1.7 есть сумма четырех 0.02, четырех 0.03, трех 0.15, двух 0.25 и одного 0.55.

Это рассуждение  годится и в общем случае. Легко  видеть, что в дереве типа Хаффмана (т.е., дереве, в котором каждый узел есть сумма своих потомков) взвешенная сумма листьев, где вес листа - это его расстояние до корня, равна сумме всех внутренних узлов. (Это свойство было мне сообщено Джоном Мотилом.)

0.05 =		= 0.02 + 0.03 + …
	0.05 + …	= 0.02 + 0.03 + …
		= 0.02 + 0.03 + …
		= 0.02 + 0.03 + …
1.0 =		= 0.02 + 0.03 + …

Табл. 3.1. Состав узлов.

На рис. 3.1b показано такое дерево, где предполагается, что два листа 0.02 и 0.03 имеют коды Хаффмана длины  . Внутри дерева эти листья являются потомками внутреннего узла 0.05, который, в свою очередь, связан с корнем с помощью   внутренних узлов от   до  . Табл. 3.2 состоит из   строк и показывает, что две величины 0.02 и 0.03 включаются в разные внутренние узлы ровно   раз. Сложение величин всех внутренних узлов дает вклад от этих двух листьев равный  . Поскольку эти листья выбраны произвольно, ясно, что эта сумма включает в себя аналогичный вклад от всех остальных узлов, то есть, равна средней длине кода. Эта число также равно сумме левого столбца или сумме всех внутренних узлов, которая и определит среднюю длину кода.

Отметим, что  в доказательстве нигде не предполагалось, что дерево - двоичное. Поэтому это  свойство выполнено для любого дерева, в котором узлы являются суммой своих  потомков. 

Метод Хаффмана предполагает, что частоты символов алфавита известны декодеру. На практике это бывает крайне редко. Одно возможное решение для компрессора – это прочитать исходные данные два раза. В первый раз, чтобы вычислить частоты, а во второй раз, чтобы сделать сжатие. В промежутке компрессор строит дерево Хаффмана. Такой метод называется полуадаптивным, и он работает медленно для практического использования. На практике применяется метод адаптивного (или динамического) кодирования Хаффмана. Этот метод лежит в основе программы compact операционной системы UNIX.

Рис.3.2. Деревья для кодов Хаффмана.

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

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

Декомпрессор  зеркально повторяет это действие. Когда он читает несжатый символ, он добавляет его на дерево и присваивает  ему код. Когда он читает сжатый код (переменной длины), он использует текущее  дерево, чтобы определить, какой  символ отвечает данному коду, после чего модифицирует дерево тем же образом, что и кодер.

Рис. 3.4. Коды ecs.

Однако, имеется  одно тонкое место. Декодер должен знать  является ли данный образчик просто несжатым символом (обычно, это 8-битный код ASCII) или же это код переменной длины. Для преодоления двусмысленности, каждому несжатому символу будет предшествовать специальный esc (escape) код переменной длины. Когда декомпрессор читает этот код, он точно знает, что за ним следуют 8 бит кода ASCII, который впервые появился на входе.

Беспокойство  вызывает то, что esc код не должен быть переменным кодом, используемым для  символов алфавита. Поскольку это  коды все время претерпевают изменения, то и код для esc следует также  модифицировать. Естественный путь –  это добавить к дереву еще один пустой лист с постоянно нулевой частотой, чтобы ему все время присваивалась ветвь из одних нулей. Поскольку этот лист будет все время присутствовать на дереве, ему все время будет присваиваться код переменной длины. Это и будет код esc, предшествующий каждому новому несжатому символу. Дерево будет все время модифицироваться, будет изменяться положение на нем пустого листа и его кода, но сам этот код будет идентифицировать каждый новый несжатый символ в сжатом файле. На рис.3.4 показано движение этого ecs кода по мере роста дерева.

Этот метод  также используется в известном  протоколе V.32 передачи данных по модему со скоростью 14400 бод. 

Если сжимаемые  символы являются кодами ASCII, то им можно  просто присвоить свои значения для  представления в несжатом виде. В общем случае, когда алфавит имеет произвольный размер, несжатые коды двух разных размеров можно также легко построить. Рассмотрим, например, алфавит размера  . Первым 16 символам можно присвоить числа от 0 до 15 в их двоичном разложении. Эти символы потребуют только 4 бита, но мы закодируем их пятью битами. Символам с номерами от 17 до 24 присвоим числа  ,  , и до   в двоичном представлении из 4 бит. Итак, мы получим шестнадцать 5-битовых кода 00000, 00001, ... , 01111, за которыми следуют восемь 4-битовых кода 0000, 0001, ... , 0111.

В общем случае, если имеется алфавит  , состоящий из   символов, выбираются такие числа   и  , что   и  . Первые   символов кодируются как  -битовые числа от 0 до  , а остальные символы кодируются  -битовыми последовательностями так, что код символа   равен  . Такие коды называются синфазными двоичными кодами.

Основная идея заключается в проверке дерева при  появлении каждого нового входного символа. Если дерево не является деревом  Хаффмана, его следует подправить. Рис. 3.5 дает представление о том, как это делается. Дерево на рис. 3.5а содержит пять символов А, В, С, D и Е. Для всех символов указаны их текущие частоты (в круглых скобках). Свойство Хаффмана означает, что при изучении дерева по всем уровням слева направо и снизу вверх (от листьев к корню) частоты будут упорядочены по возрастанию (неубыванию). Таким образом, нижний левый узел (А) имеет наименьшую частоту, а верхний правый (корень) имеет наибольшую частоту. Это свойство принято называть свойством соперничества.

Рис. 3.5. Обновление дерева Хаффмана.

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

Приведем последовательность операций при модификации дерева. Цикл начинается в текущем узле (соответствующем  новому входному символу). Этот узел будет листом, который мы обозначим  , а его частота пусть будет  . На каждой следующей итерации цикла требуется сделать три действия:

1. Сравнить   с его ближайшими соседями на дереве (справа и сверху). Если непосредственный сосед имеет частоту   или выше, то узлы остаются упорядоченными и ничего делать не надо. В противном случае, некоторый сосед имеет такую же или меньшую частоту, чем  . В этом случае следует поменять местами   и последний узел в этой группе (за исключением того, что   не надо менять с его родителем);

2. Увеличить  частоту   с   до  . Увеличить на единицу частоту всех его родителей;

3. Если   является корнем, то цикл останавливается; в противном случае он повторяется для узла, являющегося родителем  .

На рис. 3.5b показано дерево после увеличения частоты узла А с 1 до 2. Легко проследить, как описанные выше три действия влияют на увеличение частоты всех предков А. Места узлов не меняются в этом простом случае, так как частота узла А не превысила частоту его ближайшего соседа справа В.

На рис. 3.5с показано, что произойдет при следующем увеличении частоты А с 2 до 3. Три узла, следующие за А, а именно, В, С и D, имели частоту 2, поэтому А переставлен с D. После чего частоты всех предков А увеличены на 1, и каждый сравнен со своими соседями, но больше на дереве никого переставлять не надо.

Рис. 3.5d изображает дерево после увеличения частоты А до 4. Поскольку узел А является текущим, его частота (равная пока еще 3) сравнивается с частотой соседа сверху (4), и дерево не меняется. Частота А увеличивается на единицу вместе с частотами всех потомков.

На рис. 3.5е узел А опять является текущим. Его частота (4) равна частоте соседа сверху, поэтому их следует поменять местами.

Это сделано  на рис. 3.5f, где частота А уже равна 5. Следующий шаг проверяет родителя А с частотой 10. Его следует переставить с его соседом справа Е, у которого частота 9. В итоге получается конечное дерево, изображенное на рис. 3.5g.

Счетчики частот символов сохраняются на дереве в  виде чисел с фиксированной разрядностью. Поля разрядов могут переполниться. Число без знака из 16 двоичных разрядов может накапливать счетчик до числа  . Простейшее решение этой проблемы заключается в наблюдении за ростом счетчика в корне дерева, и, когда он достигает максимального значения, следует сделать изменение масштаба всех счетчиков путем их целочисленного деления на 2. На практике это обычно делается делением счетчиков листьев с последующим вычислением счетчиков всех внутренних узлов дерева. Каждый внутренний узел равен сумме своих потомков. Однако при таком методе целочисленного деления понижается точность вычислений, что может привести к нарушению свойства соперничества узлов дерева.

Простейший пример приведен на рис. 3.5h. После уполовинивания счетчиков листьев, три внутренних узла пересчитаны, как показано на рис. 3.5i. Полученное дерево, однако, не удовлетворяет свойству Хаффмана, поскольку счетчики перестали быть упорядоченными. Поэтому после каждой смены масштаба требуется перестройка дерева, которая, по счастью, будет делаться не слишком часто. Поэтому компьютерные программы общего назначения, использующие метод сжатия Хаффмана должны иметь многоразрядные счетчики, чтобы их переполнение случалось не слишком часто. Счетчики разрядности в 4 байта будут переполняться при значении равном  .

Стоит отметить, что после смены масштаба счетчиков, новые поступившие для сжатия символы будут влиять на счетчики сильнее, чем сжатые ранее до смены  масштаба (примерно с весом 2). Это  не критично, поскольку из опыта  известно, что вероятность появления символа сильнее зависит от непосредственно предшествующих символов, чем от тех, которые поступили в более отдаленном прошлом.