Кодирование Хаффмена

Кодирование Хаффмена, пожалуй, — самый известный метод сжатия данных. Оно основано на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Действительно, наиболее общее представление — алфавит ASCII — использует 8 бит для каждого символа. При этом известно, что, например, в английском языке буква «e» явно будет чаще встречаться, чем буква «q», хотя мы используем для их представления одинаковое количество бит. Используя только 4 бита для «e» и 12 бит для «q», можно выиграть несколько бит.

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

Необходимость наличия таблицы вероятностей для каждого типа сжимаемых данных представляет собой самую большую сложность при использовании кодов Хаффмена. Это не составит проблемы, если вы знаете, что всегда будете сжимать английский текст. В общем же случае, когда вы не знаете вероятности символов для ваших входных данных, применение статических кодов Хаффмена нецелесообразно.

К счастью, динамическая версия сжатия Хаффмена может менять схему кодирования в зависимости от характера изменений входного потока.