Теория информации
Конспект лекций
назад | содержание | вперед

4. ОПТИМАЛЬНОЕ ПОБУКВЕННОЕ КОДИРОВАНИЕ

 

4.4 Оптимальный код Хаффмана

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

Алгоритм построения оптимального кода Хаффмана основывается на утверждениях лемм предыдущего параграфа и заключается в следующем:

1. Упорядочим символы исходного алфавита  по убыванию их вероятностей .

2. Если , то .

3. Если  и известны коды , , то для алфавита  с новыми символами  вместо , и вероятностями , код символа заменяется на коды  и.

 

Пример 4.4.1. Пусть источник имеет алфавит  с вероятностями

Здесь символы источника уже упорядочены в соответствии с их вероятностями. Будем складывать две наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа. Тогда закодируем эти два символа 0 и 1. Далее кодовые слова достраиваются, как показано на рисунке 4.


 

Рисунок 4 Процесс построения кода Хаффмана

 

Таблица 5 Код Хаффмана

 

Посчитаем среднюю длину, построенного кода Хаффмана



при этом энтропия данного источника


 

 

Рисунок 5 Кодовое дерево для кода Хаффмана


Код Хаффмана обычно строится и хранится в виде двоичного дерева, в листьях которого находятся символы алфавита, а на «ветвях» – 0 или 1. Тогда уникальным кодом символа a является последовательность 0 и 1, которая получается при прохождении пути от корня дерева к вершине с символом a (такой путь в дереве единственный) (рис. 5).

 

Алгоритм на псевдокоде


Построение оптимального кода Хаффмана (n,P)

Обозначим

n – количество символов исходного алфавита

P – массив вероятностей, упорядоченных по убыванию

C – матрица элементарных кодов

L – массив длин кодовых слов

Huffman (n,P)

Функция Up (n,q) находит в массиве P место, куда вставить число q, и вставляет его, сдвигая вниз остальные элементы.

Процедура Down (n,j) формирует кодовые слова.

 

 

наверх

 


назад | содержание | вперед