9.5. Метод Хаффмена

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

Пусть сообщения входного алфавита А = {а₁, а₂, …, а_k} имеют соответственно вероятности их появления р₁, р₂, ..., р_k.

Тогда алгоритм кодирования Хаффмена состоит в следующем.

1. Сообщения располагаются в столбец в порядке убывания вероятности их появления.

2. Два самых маловероятных сообщения a_k-1, и а_k объединяем в одно сообщение b, которое имеет вероятность, равную сумме вероятностей сообще­ний a_k-1, а_k, т. е. p_k-1+p_k. В результате получим сообщения a₁, a₂, …, a_k-2, b, вероятности которых p₁, p₂, …, p_k-2, (p_k-1+p_k). Полученные сообщения вновь располагаем в порядке убывания вероятностей.

3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.

4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые комбинации можно определить, приписывая левым ветвям объединения символ «1», а правым - «0». Впрочем, понятия «левые» и «правые» ветви в данном случае относительны.

Так как в процессе кодирования сообщениям сопоставляются только кон- цевые узлы, полученный код (код Хаффмена) является префиксным и, следовательно, всегда однозначно декодируемым.

Построение кода Хаффмена для восьми сообщений, появляющихся с вероятностями 0.2; 0.2; 0.15; 0.13; 0.12; 0.1; 0.07; 0.03, иллюстрируется таблицей 8 и рисунком 5.

Таблица 8 - Кодирование методом Хаффмена

Сообщение	Вероятность		Вспомогательные столбцы
a1		0.20		0.20	0.20	0.25	0.35	0.40	0.60	1
a2		0.20		0.20	0.20	0.20	0.25	0.35	0.40
a3		0.15		0.15	0.20	0.20	0.20	0.25
a4		0.13		0.13	0.15	0.20	0.20
a5		0.12		0.12	0.13	0.15
a6		0.10		0.10	0.12
a7		0.07		0.10
a8		0.03

Из точки, соответствующей сумме всех вероятностей (в данном случае она равна 1), направляются две ветви. Ветви с большей вероятностью присваивается единица, с меньшей - нуль. Продолжая последовательно разветвлять дерево, доходим до вероятности каждого символа (Рисунок 3).

Рисунок 3 – Кодовое дерево кода Хаффмена

Из таблицы 9 видно, что полученный код является неравномерным, причем сообщению с максимальной вероятностью появления соответствует минимальная длина кодовой комбинации (2 бита), а сообщению с минимальной вероятностью - максимальная (4 бита).

Таблица 9 - Полученный код

	Вероятность появления сообщения	Структура кодовой комбинации	Длительность кодовой комбинации
a1	0.20	01	2 бита
a2	0.20	111	3 бита
a3	0.15	110	3 бита
a4	0.13	101	3 бита
a5	0.12	100	3 бита
a6	0.10	000	3 бита
a7	0.07	0011	4 бита
a8	0.03	0010	4 бита

Пусть переданная последовательность сообщений а₁, а₂, а₃, а₄, а₈ отображается двоичной последовательностью

01

111

110

101

0010…

(11)

Рассмотрим влияние одиночной ошибки во втором разряде принятой кодовой последовательности на результат декодирования. При этом получим

00

111

101

101

0010...

(12)

Полученная последовательность расшифровывается следующим образом

0011

111

01

01

0010

a7, a2, a1, a1, a8

(13)

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

Среднее число двоичных символов l на одно сообщение алфавита объемом К, для неравномерных двоичных кодов, определяется выражением

(14)

Эффективность неравномерных кодов оценивается следующими параметрами:

1) коэффициентом статистического сжатия, который характеризует уменьшение числа двоичных символов на знак при применении методов эффективного кодирования по сравнению с применением равномерного кода:

(15)

где l_p.k - средняя длина кодовой комбинации при равномерном кодировании;

2) коэффициентом относительной эффективности, который показывает степень близости средней длины кодовой комбинации к теоретически возможному пределу Н(А):

(16)