Теория информации |
Конспект лекций |
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) формирует кодовые слова.