2. Метод кодирования Хаффмана.

Этот метод всегда дает оптимальное кодирование в отличие от предыдущего, так как получаемая средняя длина кодового слова является минимальной.

Буквы алфавита сообщения располагают в порядке убывания вероятностей. Две последние буквы объединяют в один составной символ, которому приписывают суммарную вероятность. Далее заново переупорядочивают символы и снова объединяют пару с наименьшими вероятностями. Продолжают эту процедуру до тех пор, пока все значения не будут объединены. Это называется редукцией. Затем строится кодовое дерево из точки, соответствующей вероятности 1 (это корень дерева), причем ребрам с большей вероятностью присваивают 1,а с меньшей-0. Двигаясь по кодовому дереву от корня к оконечному узлу, можно записать кодовое слово для каждой буквы исходного алфавита.

Пример.

Буква xi	a	b	c	d	e	f
Вероятности pi	0,05	0,15	0,05	0,4	0,2	0,15
Кодовое слово	1001	110	1000	0	111	101
Длина кодового слова ni	4	3	4	1	3	3

0,4

0,2

0,15

0,05

0,15

0,35

0,05

0,1

0,6

1

0,25

0

1

1

0

0

1

1

0

1

0

= = (4*0,05 +3*0,15+4*0,05+0,4+3*0,2+3*0,15)= 2,3 бит

= - (0,4log₂ 0,4+0,2 log₂ 0,2+2* 0,15 log₂0,15 +2*0,05 log₂0,05)= - (0,52 + 0,46+ 2*0,4+2*0,2)= 2,18

= 1,05

Из рассмотренного примера видно, что чем больше разница между вероятностями букв исходного алфавита, тем больше выигрыш кода Хаффмана по сравнению с простым блоковым кодированием.

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

Недостатки кода:

1.Различные длины кодовых слов приводят к неравномерным задержкам кодирования.

2.Сжатие снижает избыточность, что соответственно повышает предрасположенность к распространению ошибок, т.е. один ошибочно принятый бит может привести к тому, что все последующие символы будут декодироваться неверно.

3.Предполагаются априорные знания вероятности букв, которые на практике не известны, а их оценки часто бывают затруднительны.

4.3.3. Арифметическое кодирование.

Алгоритм Хаффмана не может передавать на каждый символ сообщения , если не использовать блоковое кодирование, менее одного бита информации, хотя энтропия источника может быть меньше 1, особенно при существовании различных вероятностей символов.

Поэтому хотелось бы иметь такой алгоритм кодирования, который позволял бы кодировать символы менее чем 1 бит. Одним из таких алгоритмов является арифметическое кодирование, представленное в 70-х годах 20 века. При рассмотрении этого алгоритма будем исходить из того факта, что сумма вероятностей символов (и соответствующим им относительным частотам появления этих символов), всегда равна 1.Отсительные частоты появления могут определяться путем текущих статистических измерений исходного сообщения (это первый « проход» процедуры кодирования). Особенностью арифметического кодирования является то, что для отображения последовательности символов на интервале [0,1] используются относительные частоты их появления.

Пример определения частоты появления символов в сообщении

BANANANBAB.

Результатом такого отображения является сжатие символов или посимвольное сжатие в соответствии с их вероятностями, т.е. результатом арифметического сжатия будет некоторая дробь из интервала [0,1], который представляется двоичной записью (это второй «проход» процедуры кодирования). Заметим, что такой двухпроходный алгоритм может быть реализован в ранее рассмотренных кодах Шеннона – Фано и Хаффмана.

Принципиальное отличие арифметического кодирования от предыдущих методов заключается в том, что кодированию подвергается сообщения целиком (весь набор символов или файл), а не символы по отдельности или их блоки.

Эффективность арифметического кодирования растет с увеличением длины сжимаемого сообщения. Заметим, что в кодах Шеннона – Фано и Хаффмана такого не происходит.

Арифметическое кодирование заключается в построении отрезка , однозначно определяющего заданную последовательность символов в соответствии с их вероятностями. Объединение всех отрезков, пересекающихся только в граничных точках, для вероятностей каждого символа должно образовывать формальный интервал [0,1]. Для последнего полученного интервала, соответствующего последнему принятому символу сообщения, находит число, принадлежащее его внутренней части. Это число в двоичном представлении и будет кодом для рассматриваемой последовательности.

Пример. Пусть задан алфавит X={a ,b}, p(a) = , p(b) = . Необходимо закодировать сообщение {aba}.

Шаг кодирования	Поступающий символ	Интервал
0	нет	[ 0,1 ]
1	a	[ 1]
2	b	[ ]
3	a

1

0

1

.

b

a

1

2 .

b

a

1. ,

2. ,

3. 

3

.

b

a

1. ,

2. ,

3.

В таком алгоритме в конце сообщения должен стоять некий маркер, обозначающий конец сообщения.

Код сообщения {aba}=10000.

Декодирование арифметического кода производится по его значению и тем же интервалам до восстановления исходного сообщения. На практике часто используют адаптивный арифметический алгоритм, когда на начальном этапе относительные частоты появления символов задаются некоторыми отрезками, либо принимаются равновероятными. А в процессе кодирования значение этих частот уточняются.