Метод кодирования Хафмана

Правило образования кодов состоит из следующих пунктов.

1. Все сообщения ансамбля ранжируются в порядке убывания вероятности реализаций сообщений.

2. Последние два сообщения объединяются в одно сообщение с вероятностью реализации, равной сумме вероятностей, объединяемых сообщений.

3. Полученные сообщения вновь ранжируются в порядке убывания вероятности реализаций сообщений.

4. Процедура объединения и ранжирования сообщений продолжается до тех пор, пока не останется одно сообщение с вероятностью реализации, равной 1.

5. В результате процедуры объединения и ранжирования сообщений получается кодовое дерево. Каждому лучу, исходящему из узла, в котором объединяются сообщения, приписываются символы 1 и 0, (скажем, верхнему лучу приписывается символ 1, нижнему – символ 0).

6. Запись кода, соответствующего -му сообщению можно начинать как с вершины кодового дерева, так и с ветви, соответствующего -му сообщению. Если записывать код сообщения с ветви, соответствующего -му сообщению, получается не префиксный код. Поэтому рекомендуется производить считывание кода, начиная с вершины кодового дерева к ветви, содержащей -ое сообщение.

Процедура кодирования демонстрируется на примере.

Пример 3. В примере используется тот же ансамбль сообщений с теми же вероятностями реализаций элементов ансамбля. Характеристики , , , , остаются неизменными. На рисунке 1.3 показана реализация правила кодирования сообщений. В результате считывания символов, начиная с ветви -го сообщения, получены не префиксные коды. Для получения префиксных кодов производится зеркальное отображение не префиксных кодов, что показано в таблице 1

Характеристики , , , , остаются неизменными.

Рассмотрим ансамбль . По формуле полной вероятности получим = 0.5303, = 0.4697.

Количество информации, содержащееся в каждом символе ансамбля Y равно соответственно

0.915119 , 1.09019 .

Энтропия ансамбля Y равна

0.997349 .

Соответственно коэффициент сжатия и коэффициент избыточности будут равны

0.997349, 0.00265

Таблица 3.4 Код Хафмена
X	Вер.	не префиксный код	префиксный код		Условн. вер.
	0.2
	0.2				1/2
	0.19				1/3
	0.15				2/3
	0.10				1/3
	0.08				1/4
	0.06				1/5
	0.01				1/6
	0.01

На рисунке 3.5 приведено кодовое дерево, полученное при кодировании по методу Хафмена ансамбля X.

Средняя длина кода при кодировании по методу Хафмана уменьшилась также и равна

=1.34 .

Как видно из рисунка 3.5, ни одна кодовая комбинация не является началом другой кодовой комбинации, т.е. код является префиксным. Свойство префиксности кода позволяет однозначно декодировать последовательность кодовых комбинаций, что видно из таблицы 3.4 и рисунка 3.5.

Следует отметить, метод кодирования Хафмана позволяет получить показатели , , , более высокие, чем при кодировании по методу Шеннона. Это объясняется тем, что в методе кодирования по Шеннону допускается некоторый произвол при делении множества событий на группы.