double arrow

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


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

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

Пример:

Р(а1)=0,1 Р(а2)=0,15 Р(а3)=0,15 Р(а4)=0,1 Р(а5)=0,05

Р(а6)=0,05 Р(а7)=0,2 Р(а8)=0,07 Р(а9)=0,09 Р(а10)=0,04

а1=001 а2=110 а3=101 а4=000 а5=1000 а6=11101 а7=01 а8=1001 а9=1111 а10=11100

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


Сейчас читают про: