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

На этом алгоритме построена процедура построения оптимальною кода, предложенная в 1952 году Хаффменом:

1) буквы первичного алфавита выписываются в основной столбец в порядке убывания вероятностей;

2) две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность;

3) вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние объединяются;

3) процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице.

Методика поясняется примером.

Таблица 4.6

Для составления кодовой комбинации, соответствующей конкретному символу, следует проследить путь перехода вероятности символа по строкам и столбцам таблицы.

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

Рис.4.3

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

Z1	Z2	Z3	Z4	Z5	Z6	Z7	Z8

Таблица 4.7

Дата добавления: 2014-01-04