Пусть требуется закодировать длинное сообщение в виде строки
битов: А В А С С 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 Дерево Хаффмена
Обычно коды создаются на основе частоты во всем множестве
сообщений, а не только в одном.