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

Этот метод имеет два преимущества по сравнению с методом Шеннона-Фано: он устраняет неоднозначность кодирования, возникающую из-за примерного равенства сумм частот при разделении списка на две части (линия деления проводится неоднозначно), и имеет, в общем случае, большую эффективность кода.

Для построения кодовой таблицы исходное множество символов упорядочивается по невозрастанию частоты и выполняются следующие шаги:

1) объединение частот:

• две последние частоты складываются, а соответствующие символы исключаются из списка;

• оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;

• предыдущие шаги повторяются до тех пор, пока ни получится единица в результате суммирования и список ни уменьшится до одного символа;

Таблица 2.4

Исход- ные сим- волы	Час- тоты символов	Этапы построения кода				Формируемый код
		первое деление	второе деление	третье деление	первое деление		второе деление	третье деление
линия деления a	0,5	1= 0,5	код для символа aсформирован		1		-	-
линия деления b	0,25		1= 0,25	код для символа bсформирован	0		1	-
линия деления c	0,125	2=0,25+0,125+	2 = 0,125+0,125 = 0,25	1= 0,125 2 = 0,125	0		0	1
d	0,125	0,125=0,5			0		0	0

2) построение кодового дерева:

• строится двоичное кодовое дерево: корнем его является вершина, полученная в результате объединения частот, равная 1; листьями – исходные вершины; остальные вершины соответствуют либо суммарным, либо исходным частотам, причем для каждой вершины левая подчиненная вершина соответствует большему слагаемому, а правая – меньшему; ребра дерева связывают вершины-суммы с вершинами-слагаемыми. Структура дерева показывает, как происходило объединение частот;

• ребра дерева кодируются: каждое левое кодируется единицей, каждое правое – нулем;

3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» веса проходимых ребер.

Пример 2.23. Даны символыa, b, c, d с частотамиf_a=0,5; f_b=0,25; f_c=0,125; f_d=0,125. Построить эффективный код методом Хаффмена.

1) объединение частот:

Таблица 2.5

Исходные символы s	Частоты fs	Этапы объединения
		первый	второй	третий
a	0,5	0,5	0,5	1
b	0,25	0,25	0,5
c	0,125	0,25
d	0,125

2) построение кодового дерева:

1

1. 0

0,5 a 0,5

1. 0

0,25 b 0,25

1. 0

0,125 c 0,125 d

3) формирование кода:

a - 1;

b - 01;

c - 001;

d - 000.

Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.

Закодируем дискретное сообщение abbaпостроенным кодом: 101011.