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

Алгоритм Хаффмана гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов кода на символ сообщения. На первом шаге подсчитываются частоты всех символов в исходных данных. На втором шаге строятся новые коды (битовые последовательности) для каждого символа, так, чтобы никакие две разные последовательности не имели общего начала, например, три последовательности 0, 10, 110. удовлетворяют этому требованию. Хаффман предложил строить двоичное дерево символов, в корне которого находится наиболее частый символ, на расстоянии 1 от корня – следующие по частоте символы, и так далее. На основе такого дерева коды для символов получаются путем выполнения простой процедуры обхода дерева. Код представляет собой путь от корня до символа, в котором 1 означает переход по левой ветви, а 0 – по правой. Такой способ построения гарантирует нужное свойство кодов. Наконец, на последнем шаге в выходные данные записывается построенное дерево, а за ним следуют закодированные данные.

Алгоритм Хаффмана обеспечивает высокую скорость упаковки и распаковки, но степень сжатия, достигаемая при его использовании, довольно невелика. Одним из недостатков этого алгоритма является необходимость двух проходов по данным – на первом проходе подсчитываются частоты, строится дерево и формируются коды, а на втором выполняется собственно кодирование. Этого недостатка лишен адаптивный алгоритма Хаффмана, пересчитывающий частоты символов (и, соответственно, изменяющий коды) по мере поступления данных.