Деревья Хаффмена (деревья минимального кодирования)

Пусть требуется закодировать длинное сообщение в виде строки битов: А В А С С D А кодом, минимизирующим длину закодированного сообщения.
1) назначим коды:

Символ	Код
A
B
C
D

Каждый символ тремя битами, получим строку:010 100 010 000 000 111 010.

А В А С С D А

7*3=21 всего 21 бит - неэффективно
2) Сделаем иначе: предположим, что каждому символу назначен 2-битовый код

Символ	Код
A
B
C
D

00 01 00 10 10 11 00А В А С С D А

Тогда кодировка требует лишь 14 бит.
3) Выберем коды, которые минимизируют длину сообщения по частоте вхождений символа в строку: много вхождений - код короткий, мало вхождений - код длинный.

А -3 раза, С -2 раза, В -1 раз, D -1 раз то-есть можно:

· 1. использовать коды переменной длины.

· 2. код одного символа не должен совпадать с кодом другого (раскодирование идет слева направо).

Если А имеет код 0 т.к часто встречается, то В, С, D - начинаются с 1, если дальше 0,то это С, следующий может быть 0 или 1: 1 - D, 0 - В; то-есть В и D различаются по последнему биту, А -по первому, С - по второму, B и D - по третьему.

Символ	Код
A
B
C
D

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

Частота появления группы символов равна сумме частот появления каждого символа.

Сообщение АВАССDА кодируется как 0110010101110 и требует лишь 13 бит.

В очень длинных сообщениях, которые содержат символы, встречающиеся очень редко - экономия существенна.

Рис.6.30 Дерево Хаффмена

Обычно коды создаются на основе частоты во всем множестве сообщений, а не только в одном.