Составители:
99
вероятным символам присваиваются наиболее короткие кодовые слова, а
менее вероятным – длинные. Благодаря такой стратегии, код Хаффмана
дает минимальную среднюю длину кодовой последовательности,
приближающуюся к энтропии источника сообщения. Рассмотрим
построение кодовой таблицы на примере. Пусть кодируется 13 символов
упорядоченных по невозрастанию вероятности их появления: {А1, A2,…,
А13}. Пусть вероятности появления A
i
обозначаются
i
p и составляют {0,2;
0,18; 0,1; 0,1; 0,1; 0,06; 0,06; 0,04; 0,04; 0,04; 0,04; 0,03; 0,01}
соответственно. Алгоритм можно описать следующим образом.
Объединяются два символа с наименьшими вероятностями в узел
кодового дерева, этому узлу приписывается вероятность, равная сумме
вероятностей появления символов, составляющих узел. В примере
минимальную вероятность имеют символы А12 и А13, суммарная
вероятность которых равна 0,04. Далее объединяются символы или узлы с
минимальными
вероятностями, образуя следующий узел, которому
присваивается вероятность, равная сумме вероятностей составляющих.
Процесс повторяется до тех пор, пока не сойдется в один узел,
расположенный в вершине. После этого левые и правые ветви дерева
обозначаются «0» и «1» соответственно (или наоборот, «1» и «0»).
Значение кодового слова формируется в виде последовательности кодов
ветвей по пути от
вершины кодового дерева к узлу. Кодовое дерево для
приведенного примера представлено на рисунке 8.5. В результате
кодирования по методу Хаффмана получены коды, приведенные в таблице
8.4. В таблице 8.4
i
L
- длина кодового слова i-го символа (в количестве
разрядов). Код Хаффмана является префиксным кодом, то есть таким, что
ни одно кодовое слово не является префиксом (началом) другого кодового
слова. Префиксные коды декодируются однозначно, но обратное
утверждение не выполняется. Например, код {0, 01, 010, 0,0101, …,} не
является префиксным, хотя декодируется однозначно.
Таблица 8.4 Таблица кодов для
последовательности {A1,...,A13}
Имя Код
L
i
p
i
Имя Код
L
i
p
i
A 1 00 2 0,2 A8 10101 5 0,04
A2 100 3 0,18 A9 10110 5 0,04
A3 110 3 0,1 A10 10111 5 0,04
A4 010 3 0,1 A11 11110 5 0,04
A5 011 3 0,1 A12 111110 6 0,03
A6 1110 4 0,06 A13 111111 6 0,01
A7 10100 5 0,06
Средняя длина кода может быть получена в соответствии с формулой:
∑
=
=
N
i
ii
LpL
1
ср
. (8.2)
Для рассмотренной последовательности средняя длина кода составляет
3,42 разряда.
Страницы
- « первая
- ‹ предыдущая
- …
- 97
- 98
- 99
- 100
- 101
- …
- следующая ›
- последняя »
