Сжатие по методу Хаффмана

Для текстовых файлов чаще других употребляется кодировка Хаффмана,

заключающаяся в том, что символы текста заменяются цепочками бит разной длины. Методика Хаффмана гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву [4].

Применительно к сжатию изображений в основе такого метода лежит

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

сопоставляется код меньшей длины, а встречающимся редко - код большей

длины (т.е. формируется префиксный код переменной длины). Для сбора

статистики требуется два прохода по файлу - один для просмотра и сбора

статистической информации, второй - для кодирования [3]. Коэффициенты сжатия: 1/8, 2/3, 1.

При использовании такого метода требуется запись в файл и таблицы

соответствия кодируемых пикселов и кодирующих цепочек. Такое кодирование

применяется в качестве последнего этапа архивации в JPEG. Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество.

Основным недостатком данного метода является зависимость степени

сжатия от близости вероятностей символов к величине 2-м, поскольку каждый символ кодируется целым числом бит. Так, при кодировании данных с двухсимвольным алфавитом сжатие всегда отсутствует, т.к. несмотря на различные вероятности появления символов во входном потоке алгоритм фактически сводит их до 1/2. Такой алгоритм реализован в формате TIFF.