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



Глава 6.2.8 деревья хаффмена (деревья минимального кодирования)



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

Пусть требуется закодировать длинное сообщение в виде строки битов: А В А С С 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 бит.

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









Содержание    Назад    Вперед