Коды Хаффмена

 

Познакомимся теперь с оптимальным в смысле данного выше определения методом кодирования источника – кодом Хаффмена. Построение данного кода базируется на ряде лемм. Пусть сообщения ансамбля занумерованы в порядке не возрастания вероятностей:

Лемма 2.4.1. В оптимальном двоичном коде длины слов не убывают, т.е. .

Из леммы 2.4.1 следует, в частности, что в оптимальном коде наименее вероятному сообщению отвечает слово максимальной длины.

Лемма 2.4.2. В оптимальном двоичном префиксном коде всегда присутствуют два слова, имеющие одну и ту же максимальную длину, отвечающие двум наименее вероятным сообщениям и отличающиеся только последним символом.

Пусть теперь имеется ансамбль с вероятностями . Рассмотрим ансамбль , полученный из объединением двух последних (наименее вероятных) сообщений и : . Ясно, что распределение вероятностей на имеет вид

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

Лемма 2.4.3. Префиксный код U для ансамбля X оптимален тогда и только тогда, когда оптимален код для ансамбля .

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

Полезно упорядочивать все сообщения по убыванию их вероятности перед началом построения кода Хаффмена. Это минимизирует разброс длин кодовых слов, не меняя, однако, средней длины кода. Следует также отметить, что в отличие от кода Шеннона–Фано, построение кодовых слов согласно алгоритму Хаффмена осуществляется в обратном порядке, т.е. от конца слова к его началу.

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

Пример 2.4.1. Рассмотрим ансамбль X из примера 2.3.1. В табл. 2.3 приведены семь последовательных шагов, на каждом из которых производится образование нового ансамбля путем объединения двух наименее вероятных сообщений текущего. Этой операции соответствуют две ветви выходящие (справа налево) из узла. Около каждого узла отмечены вероятности сообщений после объединения. Так, на первой итерации должны быть объединены сообщения x ₇ и x ₈, как наименее вероятные. На второй – результат объединения на первой и событие как наименее вероятные в новом текущем ансамбле и т.д. Каждая ветвь маркирована символом 0 или 1 и кодовые слова соответствуют путям по дереву от корня к концевому узлу. К сообщению x _4, например, ведет путь, маркированный последовательностью символов 11100, которая и является словом, кодирующим x ₄.

Таблица 2.3

		Итерации
X	p (x)	I	II	III	IV	V	VI	VII	Код
x 1	0,50
x 2	0,20
x 3	0,15
x 4	0,05
											0,50
x 5	0,04				0,09			0,30
x 6	0,03
x 7	0,02					0,15
					0,06
x 8	0,01		0,03

 

Все кодовые слова даны в последнем столбце табл. 2.3. Два слова максимальной длины отличаются лишь в последнем символе, как и предсказывалось леммой 2.4.2. Префиксность кода очевидна в свете сделанного ранее замечания о структуре дерева для произвольного префиксного кода. Вычисление средней длины кода приводит к итогу .

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