Коды Хаффмана

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности, что позволяет однозначно их декодировать. В отличие от кодов Шеннона – Фано, которые в настоящее время практически не применяются, коды Хаффмана находят широкое применение при кодирование сообщений [1-3, 5, 7].

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана

Рассмотрим алгоритм построения кодов Хаффмана на следующем примере: пусть имеется источник с алфавитом X, включающий шесть сообщений x ₁… x ₆. У каждого сообщения имеется своя вероятность появления, приведенная в таблице 5.

Таблица 5

Вероятность появления сообщений источника информации

Сообщения источника	x 1	x 2	x 3	x 4	x 5	x 6
Вероятность появления сообщения	0,3	0,2	0,15	0,15	0,1	0,1

1. Выбираем два сообщения с наименьшими вероятностями и заменяем их одним с вероятностью равной сумме вероятности данных сообщения (выбранные сообщения выделяем темным цветом), таблица 6:

Таблица 6

Формирование промежуточных алфавитов

	x 1	x 2	x 3	x 4	x 5	x 6
Объединяем сообщения	0,3	0,2	0,15	0,15	0,1	0,1
Упорядочиваем по вероятности появления	0,3	0,2	0,2	0,15	0,15
Объединяем сообщения	0,3	0,2	0,2	0,15	0,15
Упорядочиваем по вероятности появления	0,3	0,3	0,2	0,2
Объединяем сообщения	0,3	0,3	0,2	0,2
Упорядочиваем по вероятности появления	0,4	0,3	0,3
Объединяем сообщения	0,4	0,3	0,3
Упорядочиваем по вероятности появления	0,6	0,4
Объединяем сообщения	0,6	0,4

2. В результате проведенных операций мы получили 4 промежуточных алфавита (X ₁ – X ₄). Результат перепишем в следующем виде, таблица 7:

Таблица 7

Промежуточные алфавиты

Вероятности
Исходный алфавит X	Промежуточные алфавиты
X 1	X 2	X 3	X 4
0,3	0,3	0,3	0,4	0,6
0,2	0,2	0,3	0,3	0,4
0,15	0,2	0,2	0,3
0,15	0,15	0,2
0,1	0,15
0,1

3. Далее проведем процедуру кодирования, таблица 8. Кодирование выполняется в обратном порядке от алфавита X ₄ к исходному алфавиту X.

Двум знакам последнего алфавита X ₄ присваиваем коды 0 (сообщение с вероятностью 0,6) и 1 (сообщение с вероятностью 0,4). Условимся в дальнейшем, что верхний знак будет кодироваться символом 0, а нижний – 1.

Сообщение с вероятностью 0,6 алфавита X ₄ было получено как сумма вероятностей 2-ух сообщений алфавита X ₃ с вероятностями 0,3 и 0,3. В данном случае эти сообщения кодируются уже двухразрядным кодом. Старшим разрядам обоих сообщений присваивается 0, так как нулем было закодировано сообщение с вероятностью 0,6 алфавита X ₄. Младшему разряду верхнего сообщения в таблице присваивается 0, а нижнему – 1 (было определено выше). Сообщение с вероятностью 0,4 алфавита X ₃ будет кодироваться также как и сообщение с этой же вероятностью в алфавите X ₄.

По аналогии кодируются остальные сообщения алфавитов, в результате получаем закодированный исходный алфавит кодом Хаффмана, в котором сообщения, имеющие большую вероятность, кодируются кодом меньшей длины, а с меньшей вероятностью кодами большей длины.

Таблица 8

Процедура кодирования

Вероятности
Исходный алфавит X	Промежуточные алфавиты
X 1	X 2	X 3	X 4
0,3 (00)	0,3 (00)	0,3 (00)	0,4 (1)	0,6 (0)
0,2 (10)	0,2 (10)	0,3 (01)	0,3 (00)	0,4 (1)
0,15 (010)	0,2 (11)	0,2 (10)	0,3 (01)
0,15 (011)	0,15 (010)	0,2 (11)
0,1 (110)	0,15 (011)
0,1 (111)

Пример 7. Закодируем русский алфавит с помощью описанного выше алгоритма Хаффмана, используя таблицу 1.

Решение: Результат кодирования приведен в таблице 9.

Таблица 9

Результат кодирования букв русского алфавита кодом Хаффмана

Буква	Двоичное число	Буква	Двоичное число	Буква	Двоичное число
«−» о е а и т н с р в л		к м д п у я ы з ъ, ь б г		ч й х ж ю ш ц щ э ф

Пример 8. Пусть по каналу связи получено сообщение (слово на русском языке) закодированное кодом Хаффмана: 10001101001111011010110.

Необходимо декодировать данную последовательность, используя таблицу 9.

Решение: Процесс декодирования основывается также на свойстве префиксности кода и выполняется слева на право, таблица 10.

Таблица 10

Процесс декодирования сообщения

Принятая кодовая последовательность

-

-

к

к

-

к

н

к

н

-

к

н

и

к

н

и

-

к

н

и

-

к

н

и

-

к

н

и

г

к

н

и

г

-

к

н

и

г

а

Можно повысить эффективность кодирования, если строить код не для символа, как в рассмотренных выше примерах, а для блоков из n символов. В этом случае частота блока рассчитывается как произведение частот символов, которые входят в блок.

Дата добавления: 2015-07-02