Код Хаффмана. Буквы алфавита сообщений выписывают в основной столбец таблицы кодирования в порядке убывания вероятностей

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

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

Пример:

Р(а₁)=0,1 Р(а₂)=0,15 Р(а₃)=0,15 Р(а₄)=0,1 Р(а₅)=0,05

Р(а₆)=0,05 Р(а₇)=0,2 Р(а₈)=0,07 Р(а₉)=0,09 Р(а₁₀)=0,04

а₁=001 а₂=110 а₃=101 а₄=000 а₅=1000 а₆=11101 а₇=01 а₈=1001 а₉=1111 а₁₀=11100

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