Алгоритм Хаффмана — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.
В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами.
Этот метод кодирования состоит из двух основных этапов:
- Построение оптимального кодового дерева.
- Построение отображения код-символ на основе построенного дерева.
Кодирование Хаффмана
Один из первых алгоритмов эффективного кодирования информации был
предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в
следующем: зная вероятности вхождения символов в сообщение, можно
описать процедуру построения кодов переменной длины, состоящих из целого
количества битов. Символам с большей вероятностью присваиваются более
короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет
однозначно их декодировать, несмотря на их переменную длину.
Классический алгоритм Хаффмана
на входе получает таблицу частот встречаемости символов в сообщении.
Далее на основании этой таблицы строится дерево кодирования Хаффмана
(Н-дерево). [1]
- Символы входного алфавита образуют список свободных узлов. Каждый
лист имеет вес, который может быть равен либо вероятности, либо
количеству вхождений символа в сжимаемое сообщение.
- Выбираются два свободных узла дерева с наименьшими весами.
- Создается их родитель с весом, равным их суммарному весу.
- Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
- Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
- Шаги, начиная со второго, повторяются до тех пор, пока в списке
свободных узлов не останется только один свободный узел. Он и будет
считаться корнем дерева.
Допустим, у нас есть следующая таблица частот:
| 
