16. Код Хаффмана

Методика построения кода:

1. Буквы алфавита распол. в порядке убывания вероятностей.

2. Две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность. В нашем примере: z6+z5. Pz5,6=0,17. Она бы, соответственно поднялась вверх по столбу вероятностей.

3. Вероятности букв, не участвующие в объединении и полученные суммарные вероятности снова располагаются в порядке убывания. Пункты 2-3 повторяются до тех пор, пока не будет получена единственная вспомогательная буква с вероятностью равной 1.

4. На втором этапе построения кода строится кодовое дерево. Для составления кодовой комбинации необходимо проследить путь перехода по строкам и столбцам таблицы. Из точки, соответствующей вероятности 1 выходят две ветви, ветвь с большей вероятностью, которой присваивается символ 1, а ветвь с меньшей – символ 0. На 3-ем этапе по кодовому дереву составляется кодовая комбинация для каждой буквы. Двигаясь по кодовому дереву от единицы, можно записать для каждой буквы соответствующую ей кодовую комбинацию.

Методы кодирования, когда кодируются сочленения букв, позволяют достигнуть максимального сжатия букв.

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