Сжатие Хаффмана

Алгоритм сжатия Хаффмана назван по имени его изобретателя, Дэвида Хаффмана, бывшего профессором Массачусетского технологического института.

Сжатие Хаффмана - алгоритм компрессии без потерь, которые идеален для сжатия текстов и программных файлов. Это объясняет его широкое распространение во многих многих программах архивации.

Как работает сжатие Хаффмана

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

Наглядный пример, который пояснит эти принципы: допустим, мы хотим сжать следующую последовательность данных:

ACDABA

Здесь 6 символов и это 6 байтов или 48 бит. При использовании сжатия Хаффмана, в файле ищется наиболее часто встречающася последовательность символов. (в данном случае буква 'A' встречается 3 раза) и строится кодовая последовательность, которая заменяет символы более короткими последовательностями битов. В этом примере алгоритм построит следующую последовательность: A=0, B=10, C=110, D=111. Сжатый файл тогда будет выглядеть так:

01101110100

Итак, от исходных 48 битов осталось 11, и коэффициент сжатия для этого файла составляет 4 к 1.

Сжатие Хаффмана может быть оптимизировано двумя различными путями:

• Адаптивный алгоритм Хаффмана динамически изменяет кодовые последовательности в соответствии и частотой появления символов.
• Расширенный алгоритм Хаффмана может кодировать группы символов вместо отдельных символов.

Достоинства и недостатки

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

Где используется сжатие Хаффмана

Сжатие Хаффмана широко используется в программах архивации, таких как pkZIP, lha, gz, zoo и arj. Также применяется в сжатиях JPEG и MPEG.