Методические указания к заданию 3.3

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

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

Рис. 4. Первый этап формирования дерева Хаффмана

На втором шаге аналогично объединим общим родителем узлы, соответствующие символам «5» и «6». На третьем шаге, имея несколько возможностей для объединения узлов, выберем сформированные на первых двух шагах узлы с весом 2 (рис. 5).

Рис. 5. Третий шаг построения дерева Хаффмана

Продолжая действовать аналогично, получаем итоговое дерево (рис. 6).

Рис. 6. Дерево Хаффмана

Кодовые слова формируются так же, как и в случае кода Шеннона-Фано. Все разрешенные кодовые комбинации кода Хаффмана приведены в таблице.

Закодированное сообщение выглядит так: «000110010000000010101111010101110011110110111». Общая длина закодированного сообщения равна 45 бит, средняя длина кодовой комбинации бит/символ. Избыточность сжатого сообщения равна:

.

Средняя длина и избыточность такие же, как у кода Шеннона-Фано

Таким образом, применение кода Хаффмана позволило сократить избыточность сообщения до минимума.

Полученные коды Шеннона-Фано и Хаффмана обладают свойством префиксности. Это означает, что ни одна кодовая комбинация не является началом другой, что позволяет обеспечить однозначное декодирование.

Как уже отмечалось ранее, для кодирования и декодирования сообщений, сжатых по методам Шеннона-Фано и Хаффмана, кодек должен обладать априорной информацией о статистике сообщения. Поэтому кроме самого сообщения на приемную сторону необходимо передать таблицу частот встречаемости символов, что увеличивает длину передаваемых данных и снижает фактическую эффективность сжатия. Тем не менее, этот недостаток нивелируется при сжатии больших объемов данных, например, при сохранении изображений в формате JPEG.

Список литературы

1. Алексеев А.П. Информатика 2007.– СОЛОН-ПРЕСС, 2007. – 608 с.

2. Shannon C. E. «A mathematical theory of communication», Bell Sys. Tech. Jour., vol. 27, pp. 379-423; July, 1948.

3. Huffman D. A., «A method for the construction of minimum-redundancy codes», Proc. Inst. Radio Engineers, vol. 40, no. 9, pp. 1098-1101, Sep. 1952.

Приложение 1

Таблица СР-1251