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