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

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

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

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

Пример 1 (ПЗ№8):

Знаки(буквы)	Вероятность	Редукция	Кодовое слово по кодовому дереву
x1	0,22	0,22	0,22	0,26	0,32	0,42	0,58
x2	0,20	0,20	0,20	0,22	0,26	0,32	0,42
x3	0,16	0,16	0,16	0,20	0,22	0,26
x4	0,16	0,16	0,16	0,16	0,20
x5	0,1	0,1	0,16	0,16
x6	0,1	0,1	0,1
x7	0,04	0,06
x8	0,02

корень

Пример №2:

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

II способ: Редукция по уровням.

xi	x1	x2	x3	x4	x5	x6	x7	x8
pi	0,22	0,20	0,16	0,16	0,1	0,1	0,04	0,02
код
ni
nipi	0,44	0,4	0,48	0,48	0,3	0,4	0,2	0,1
-pilog2pi

= =2,8

=

=

Заметим:

1) Во втором способе при построении кодового дерева для присвоения ребрам его значений 1 и 0 необходимо использовать тот же принцип: 1 – ребру с большей вероятностью, 0 – ребру с меньшей вероятностью

2) В случае, когда в процедуре редукции несколько знаков имеют одинаковые вероятности, необходимо выбрать для очередного объединения те два из них, которые до этого имели наименьшее число объединений. Этим достигается выравнивание длин кодовых слов.

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

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

При всей простоте коды Хаффмана обладают недостатками:

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

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

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