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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2

Исходные символы 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,5a 0,5 0

0,25 b 0,25

1. 0

0,125 c 0,125 d

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

a - 1;

b - 01;

c - 001;

d - 000.

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

2. Примеры решения задач

Пример. Закодировать фамилию преподавателя методами Шеннона-Фано и Хаффмана.

3. Задание

Для выбранной в соответствии с вариантом задания задачи:

1. Закодировать сигнал методом Шеннона-Фано.

2. Закодировать сигнал методом Хаффмана.

3. Выполнить сравнительный анализ результатов кодирования.

4. Сделать выводы.