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

Пусть требуется закодировать длинное сообщение в виде строки

битов: А В А С С D А кодом, минимизирующим длину закодированного

сообщения.

1) назначим коды:

┌──────┬───┐

│символ│код│ каждый символ тремя битами.

├──────┼───┤

│А │010│

│В │100│ получим строку :010 100 010 000

│С │000│ 000 111 010 А В А С С D А

│D │111│

└──────┴───┘

7*3=21 всего 21 бит - неэффективно

2) Сделаем иначе: предположим, что каждому символу назначен

2-битовый код

┌──────┬───┐

│символ│код│ 00 01 00 10 10 11 00

├──────┼───┤ А В А С С D А

│ А │00 │

│ В │01 │

│ С │10 │

│ D │11 │

└──────┴───┘

Тогда кодировка требует лишь 14 бит.

3) Выберем коды, которые минимизируют длину сообщения по

частоте вхождений символа в строку: много вхождений - код корот-

кий, мало вхождений - код длинный.

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

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

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

(раскодирование идет слева направо).

 

┌──────┬─────┐ Если А имеет код 0 т.к часто встречается, то

│символ│код │ В, С, D - начинаются с 1, если дальше 0,то это

├──────├─────┤ С, следующий может быть 0 или 1: 1 - D

│А │0 │ 0 - В

│С │10 │ то-есть В и D различаются по последнему биту

│В │110 │ А -по первому С - по второму

│D │111 │ B и D - по третьему.

└──────┴─────┘

Таким образом, если известны частоты появления символов в

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

Частота появления группы символов равна сумме частот появле-

ния каждого символа.

Сообщение АВАССDА кодируется как 0110010101110 и требует

лишь 13 бит.

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

чающиеся очень редко - экономия существенна.

 

А В С D ,7

0 / 1

A С В D ,4

0 / 1

C,1 B D ,2

1 / 1

B,1 D,1

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

Обычно коды создаются на основе частоты во всем множестве

сообщений, а не только в одном.