Алгоритм Хаффмана

Алгоритм кодирования Хаффмана был придуман в 1952 году Дэвидом Хаффманом как более оптимальный вариант алгоритма Шеннона-Фано. Этот алгоритм весьма прост и служит основой многих компьютерных программ сжатия текстовой и графической информации. Его можно использовать как непосредственно, так и в составе многоуровневого сжатия сложной информации. Если в кодировании по Фано все вероятности кодируемых сообщений разбиваются на две примерно равные группы и далее на основе этих групп строится кодовое дерево, то в алгоритме Хаффмана используется принцип попарного сложения наименьших вероятностей.

Рассмотрим этот алгоритм подробнее. Предположим, что нам дано 5 символов «а1», «а2», «а3», «а4», «а5» с вероятностями 0.1, 0.1, 0.2, 0.2 и 0.4 соответственно.

1) Наименьшие вероятности у символов «а1» и «а2» - объединяем их в пару и складываем их вероятности, получаем символ «а12» с вероятностью 0.2. Теперь в нашей последовательности 4 символа: «а12», «а3», «а4» и «а5» с вероятностями 0.2, 0.2, 0.2 и 0.4 соответственно;

2) На следующем шаге возможно пойти несколькими путями: объединить «а12» с «а3», либо «а12» с «а4», либо «а3» с «а4». Выберем произвольно первую пару: получим символы «а123», «а4» и «а5» с вероятностями 0.4, 0.2 и 0.4 соответственно. (В дальнейшем будет продемонстрирована важность выбора определенной пары в случае, когда вариантов несколько);

3) На третьем шаге также возможно несколько путей: один из двух оставшихся символов с вероятностью 0.4 нужно объединить с «а4». Возьмем «а123» и получим на выходе всего два символа: «а1234» с вероятностью 0.6 и «а5» с вероятностью 0.4;

4) Теперь нам остается лишь объединить два оставшихся символа и получить символ «а12345» с вероятностью 1.

Теперь для осуществления дальнейшего кодирования представим данный алгоритм в виде дерева.

Рис.1

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

Рис.2

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

а1 = 1100 (4 бита)

а2 = 1101 (4 бита)

а3 = 111 (3 бита)

а4 = 10 (2 бита)

а5 = 0 (1 бит)

Каждый символ первоначально представлялся 8 битами (1 байт). Как видно, кодирование Хаффмана позволило нам уменьшить размер каждого символа в битах, а следовательно – размер выходного файла. Покажем это в виде таблицы.

Частота	Первоначально	После кодирования	Уменьшено на
а1 - 1	1Х8 = 8	1Х4 = 4
а2 - 1	1Х8 = 8	1Х4 = 4
а3 - 2	2Х8 = 16	2Х3 = 6
а4 - 2	2Х8 = 16	2Х2 = 4
а5 - 4	4Х8 = 32	4Х1 = 4

Первоначальный размер файла: 80 бит

После кодирования: 14 бит

14 – 17,5% от 80, следовательно, файл сжат на 17,5%.

Как уже было сказано выше, при составлении кодов Хаффмана можно пойти разными путями. Какой же путь будет наиболее предпочтительным? Если сжатый файл записывается на диск, то пути построения кода не имеют значения. Если же планируется передавать файл по линиям связи, то особую важность приобретает дисперсия кода – величина, показывающая, насколько сильно отклоняются длины индивидуальных кодов от их среднего. Биты сжатого файла помещаются по мере их генерации в буфер, и легко видеть, что для файла с большей дисперсией потребуется буфер большего размера, а для файла с меньшей дисперсией – меньшего.

Проиллюстрируем всё вышесказанное ещё одним примером. Возьмем строку «топот_копыт». Имеем следующие символы и их вероятности:

Символ	«т»	«о»	«п»	«_»	«к»	«ы»
Вероятность	3/11	3/11	2/11	1/11	1/11	1/11

Как и в предыдущем примере, здесь мы можем построить дерево Хаффмана различными способами. На рис. 3.1 и 3.2 показаны два из них – деревья высоты 4 и 3 соответственно.

Рис. 3.1 Рис.3.2

Чтобы посчитать дисперсию кода, необходимо вычислить его среднюю длину. Средняя длина кода является суммой произведений вероятностей символов и присвоенных им кодов. В нашем примере средняя длина кода равна:

1) (1Х4 + 1Х4 + 1Х3 + 2Х2 + 3Х2 + 3Х2) /11 = 2,45

2) (1Х3 + 1Х3 + 1Х3 + 2Х3 + 3Х2 + 3Х2) /11 = 2,45

Легко видеть, что средняя длина кода при определенном наборе символов одинакова для всех кодов.

Кстати, стоит упомянуть об одном крайне интересном свойстве средней длины кода Хаффмана. Если сложить значения вероятностей всех внутренних узлов кодового дерева, то полученное значение будет равно средней длине кода. Проверим это:

(2+3+5+6+11)/11 = 2,45. Свойство справедливо.

Это дает простой способ вычисления средней длины для кодов Хаффмана без использования операции умножения. В общем случае свойство будет звучать так: в дереве, в котором каждый узел есть сумма своих потомков, взвешенная сумма листьев, где вес листа – это его расстояние до корня, равна сумме всех внутренних узлов (Salomon 40).

Теперь рассчитаем дисперсию:

1)(1Х(4-2,45)² + 1Х(4-2,45)² + 1Х(3-2,45)² + 2Х(2-2,45)² + 3Х(2-2,45)² + 3Х(2-2,45)²)/11 = 0,61

2) (1Х(3-2,45)² + 1Х(3-2,45)² + 1Х(3-2,45)² + 2Х(3-2,45)² + 3Х(2-2,45)² + 3Х(2-2,45)²)/11 = 0,25

Соответственно, код 3.2 предпочтительнее, чем 3.1.

1.2.1. Декодирование Хаффмана

Для того, чтобы произвести декодирование, необходимо, чтобы соответствующий рабочий модуль прочел начало файла и построил дерево Хаффмана для алфавита. Так как декодирующее дерево обладает определенным объемом, оно уменьшает эффективность кодирования (в среднем процентов на 60-70). Дальнейший алгоритм не сложен: начиная с корня дерева декодер идет по направлению к листу дерева; в случае нахождения нулевого бита декодер идет по нижней ветке дерева, в случае нахождения единичного бита – по верхней. Достигая листа дерева, декодер узнает ASCII-код первого несжатого символа. В дальнейшем процедура повторяется для всех символов.

Продемонстрируем это на примере. Дано 5 символов а1, а2, а3, а4, а5 с равными вероятностями (рис. 4). Входная строка «а1а5а4» закодирована последовательностью 0001110. Декодирующий модуль начинает читать последовательность от корня и, прочитав «000», доходит до символа а1. Затем от возвращается обратно в корень и, прочитав «11», доходит до символа а5, и т.д.

Рис.4.