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

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

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

14

_______________________________________________________________________________

дальнейших построениях дерева. Процедура объединения свободных узлов ве-дется до тех пор, пока не останется единственный узел (корень дерева).

На рис. 4 показан первый этап построения дерева.

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

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

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

На четвертом шаге объединяем узлы «3» и «Н», получая новый узел с ве-сом 5 (рис. 6).

Рис. 6 – Четвертый шаг построения дерева Хаффмана

На пятом шаге узлами с наименьшими весами, используемыми для по-строения, выберем «2» с весом 3 и составной узел «5, 6, И, Пробел» с весом 4 (рис. 7).

Рис. 7 – Пятый шаг построения дерева Хаффмана

15

_______________________________________________________________________________

На шестом шаге объединяем узел «7» с весом 4 и составной узел «3, Н» с весом 5 (рис. 8).

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

В результате объединения двух составных узлов «7, 3, Н» с весом 9 и «2, 5, 6, И, Пробел» с весом 7 получаем итоговое дерево (рис. 9).

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

Кодовые слова формируются так же, как и в случае кода Шеннона-Фано.

Все разрешенные кодовые комбинации кода Хаффмана приведены в таблице.

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

n ⁴⁵ 2,813 бит/символ.Избыточность сжатого сообщения равна:

16

16

_______________________________________________________________________________

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

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

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

17

_______________________________________________________________________________

Приложение 1

Таблица СР-1251

18