Лекции по теории информации. Фурсов В.А. - 81 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

81
Эффект достигается за счет того, что при укрупнении блоков, группы
можно делить на более близкие по значениям суммарных вероятностей под-
группы. Вообще
lim ( )
ср
n
l H z

, где
n
– число символов в блоке.
9.4 Методика кодирования Хаффмана
Рассмотренная выше методика кодирования не всегда приводит к хороше-
му результату, вследствие отсутствия четких рекомендаций относительно того,
как делить множество кодируемых знаков на подгруппы. Рассмотрим методику
кодирования Хаффмана, которая свободна от этого недостатка.
Кодируемые знаки, также как при использовании метода Шеннона-Фано,
располагают в порядке убывания их вероятностей (таблица 9.3). Далее на каж-
дом этапе две последние позиции списка заменяются одной и ей приписывают
вероятность, равную сумме вероятностей заменяемых позиций. После этого
производится пересортировка списка по убыванию вероятностей, с сохранени-
ем информации о том, какие именно знаки объединялись на каждом этапе. Про-
цесс продолжается до тех пор, пока не останется единственная позиция с веро-
ятностью, равной 1.
Таблица 9.3
Вспомогательные столбцы
Знаки
i
1 2 3 4 5 6 7
1
z
0,22 0,22 0,22 0,26 0,32 0,42
0,58 0,1
2
z
0,2 0,2 0,2 0,22 0,26
0,32 0,42
3
z
0,16 0,16 0,16 0,2
0,22 0,26
4
z
0,16 0,16 0,16
0,16 0,2
5
z
0,1 0,1
0,16 0,16
6
z
0,1
0,1 0,1
7
z
0,04 0,06
8
z
0,02
После этого строится кодовое дерево. Корню дерева ставится в соответст-
вие узел с вероятностью, равной 1. Далее каждому узлу приписываются два по-
томка с вероятностями, которые участвовали в формировании значения вероят-

Страницы