Алгоритм Хаффмана

Слабое место метода упаковки заключается в том, что символы кодируются битовыми последовательностями одинаковой длины. Например, любой текст, состоящий только из двух букв «А» и «В», сжимается методом упаковки в восемь раз. Однако если к такому тексту добавить всего лишь одну букву, например «С», то степень сжатия сразу уменьшится вдвое, причем независимо от длины текста и количества добавленных символов «С»!

Улучшения степени сжатия можно достичь, кодируя часто встречающиеся символы короткими кодами, а редко встречающиеся — более длинными. Именно такова идея метода, опубликованного Д. Хаффманом (Huffman) в 1952 г.

Идея кодирования символов кодами переменной длины была высказана и теоретически проработана амери­канскими учеными К. Шенноном и Р. М. Фано. Ими был предложен алгоритм построения эффективных сжимающих кодов переменной длины (алгоритм Шеннона—Фано), однако он в некоторых случаях строил неоптимальные коды. Алгоритм Хаффмана оказался простым, быстрым и оптимальным: среди алгоритмов, кодирующих каждый символ по отдельности и целым количеством бит, он обеспечивает наилучшее сжатие.

Алгоритм Хаффмана сжимает данные за два прохода: на первом проходе читаются все входные данные и подсчитываются частоты встречаемости всех символов. Затем по этим данным строится дерево кодирования Хаффмана, а по нему — коды символов. После этого, на втором проходе, входные данные читаются еще раз и при этом генерируется выходной массив данных.

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