Модели и структуры данных

       

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


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

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



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

А В А С С D А

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

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

СимволКод
A00
B01
C10
D11
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 - по третьему.

СимволКод
A0
B10
C110
D111

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

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

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

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

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

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



Содержание раздела