Кодирование Хаффмана

Зачем нужно кодирование Хаффмана

Кодирование Хаффмана — это алгоритм сжатия данных без потерь, который строит оптимальный префиксный код переменной длины. Идея в том, чтобы часто встречающимся символам давать короткие коды, а редким — длинные. Тогда общая длина закодированного сообщения будет минимальной.

В обычном равномерном кодировании все символы занимают одинаковое число бит. Хаффман отказывается от равномерности и за счёт этого экономит память.

Префиксное свойство

Префиксный код — это код, в котором ни одно кодовое слово не является началом другого. Благодаря этому закодированную строку можно однозначно разобрать без разделителей: как только прочитан код одного символа, дальше начинается следующий.

Как строится дерево

Алгоритм строит двоичное дерево по частотам символов:

1. для каждого символа создают узел с его частотой;
2. выбирают два узла с наименьшими частотами;
3. объединяют их в новый узел, частота которого равна сумме;
4. повторяют, пока не останется один корень;
5. левым рёбрам приписывают 0, правым — 1; код символа — путь от корня к листу.

Символ	Частота	Код (пример)
А	5	0
Б	2	10
В	1	110
Г	1	111

Разбор примера

Частоты: А — 5, Б — 2, В — 1, Г — 1. Объединяем самые редкие:

1) В(1)+Г(1) -> узел (2) 2) Б(2)+узел(2) -> узел (4) 3) А(5)+узел(4) -> корень (9) Коды: А=0, Б=10, В=110, Г=111

Частый символ А получил код длиной 1 бит, редкие В и Г — по 3 бита. При равномерном коде каждому символу понадобилось бы 2 бита, а здесь средняя длина меньше.

Подсчёт выигрыша

Оценим экономию для нашего примера. Всего символов 5+2+1+1 = 9. При равномерном двухбитном коде сообщение заняло бы 9 · 2 = 18 бит. С кодом Хаффмана длина равна 5·1 + 2·2 + 1·3 + 1·3 = 15 бит. Выигрыш — 3 бита, то есть около шестой части. Чем сильнее различаются частоты символов, тем больше выгода: для текстов, где одни буквы встречаются гораздо чаще других, сжатие заметно.

Где применяют

Кодирование Хаффмана входит как составная часть во многие форматы сжатия данных и изображений. Обычно сначала текст преобразуют другими методами, а на последнем шаге применяют код Хаффмана, чтобы дожать результат. Поскольку это сжатие без потерь, исходные данные восстанавливаются полностью, бит в бит, — это обязательное требование для текста и программ, в отличие от сжатия с потерями для звука и фотографий.

Частые ошибки. Нарушают префиксное свойство и не могут однозначно раскодировать. Дают короткие коды редким символам вместо частых. Забывают, что для раскодирования нужно сохранить само дерево или таблицу кодов.

Кратко о главном

• Кодирование Хаффмана сжимает данные без потерь.
• Частым символам даются короткие коды, редким — длинные.
• Код префиксный: ни одно слово не является началом другого.
• Дерево строят, объединяя два самых редких узла, пока не останется корень.
• Для раскодирования нужно сохранить таблицу кодов или дерево.