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

От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода с наименьшей для данного распределения вероятностей средним числом символов на букву.

Для двоичного кода методика сводится к следующему. Буквы алфавита выписываются в порядке убывания вероятностей в один столбец. Две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность. Полученные буквы снова выстраиваются в дополнительный столбец, в котором вспомогательная буква из предыдущего столбца в новом столбце ставится в соответствии с ее суммарной вероятностью (в дополнительном столбце вспомогательные буквы подчеркнуты), а две последние буквы снова объединяются в одну. Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью равной 1. По данной методике составим таблицу.

Таблица 3.5

1 2 3 4 5 6 7 код
Z1 0,22 0,22 0,22 0,26 0,32 0,42 0,58 1 01
Z2 0,20 0,20 0,20 0,22 0,26 0,32 0,42 00
Z3 0,16 0,16 0,16 0,20 0,22 0,26 111
Z4 0,16 0,16 0,16 0,16 0,20 110
Z5 0,10 0,10 0,16 0,16 100
Z6 0,10 0,10 0,10 1011
Z7 0,04 0,06 10101
Z8 0,02 10100

Для составления кодовой комбинации, соответствующей данному сообщению, необходимо проследить путь перехода сообщения по строкам и столбцам таблицы. Для наглядности строится кодовое дерево. Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью направляются влево и им приписывается символ 1, с меньшей – 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до вероятности появления каждой буквы.

методика Хаффмена
Рис. 3.2. Кодовое дерево

Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию:

методика Хаффмена
методика Хаффмена.

Рассмотрев методики построения эффективных кодов, нетрудно убедиться в том, что эффект достигается благодаря присвоению более коротких кодовых комбинаций более вероятным буквам и более длинных менее вероятным буквам. http://peredacha-informacii.ru/ Таким образом, эффект связан с различием в числе символов кодовой комбинации.

А это приводит к трудности при декодировании.