Базовая идея алгоритма кодирования Хаффмена для двоичных кодов заключается в том, чтобы начинать с малого количества символов и переходить к большим количествам символов.
Легко закодировать источник с помощью двух символов, независимо от того, каковы их соответствующие вероятности: два кодовых слова должны быть просто 0 и 1, обеспечивая среднюю длину 1. Лучшего кода не существует!.
Усложним задачу. Пусть источник кодируется тремя символами, у каждого из которых есть своя вероятность.
В этом случае процесс кодирования по алгоритму Хаффмена будет состоять из нескольких шагов:
– (этап сокращения) временно объединим два символа с самыми низкими вероятностями в один сложный символ с вероятностью, равной сумме вероятностей отдельных символов.
В результате вместо трёх символов останется только два (один сложный, полученный на первом шаге, со своей вероятностью и последний оставшийся из начального набора). Двух символьный источник легко кодируется символами 0 и 1.
– (этап разделения) сложный символ разделяется на свои компоненты, которым присваиваются коды, имеющие общий префикс, соответствующий коду сложного символа, закреплённого за ним на первом шаге.
Проиллюстрируем эту задачу: Построим кодовое дерево.
Символ
Вероятность
Кодовое
слово
Вероятность
Кодовое
слово
S1
0.5
0.5
0
S2
0.3
10
0.5
1
S3
0.2
S3
Посчитаем среднюю длину слов созданного кода
S2
S1
L =(0,5х2)+(0,3х2)+(0,2х2)=2.
Посчитаем энтропию данного источника
H =0,5 х log 0,5 +0,3 х log 0,3+0,2 х log 0,2=1,49.
Проверим свойство созданного кода
H<=L<H +1 => 1,49<=2<2,49,
что согласуется с утверждением о пределах средней длины слов кода:
«источник с энтропией H может кодироваться с помощью моментального двоичного кода средней длины L, удовлетворяющего H<=L<H +1».
lektsii.net - Лекции.Нет - 2014-2025 год. (0.006 сек.)
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
0.3
10
0.5
слово