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

Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный объем файла уменьшится.

Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Пример:

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее:

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

Мы возьмем из последней таблицы 2 символа с наименьшей частотой. В нашем случае это Н (5) и какой либо символ из К или Т (10), можно взять любой из них например К.

Сформируем из " узлов" Н и К новый " узел", частота вхождения для которого будет равна сумме частот Н и К:

Номер в рамке - сумма частот символов Н и К. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра Н и К и рассматривая вместо них новый " узел" с суммарной частотой вхождения. Самая низкая частота теперь у Т и нового " узла". Снова сделаем операцию слияния узлов:

Рассматриваем таблицу снова для следующих двух символов (Л и О).

Мы продолжаем в этот режим пока все " дерево" не сформировано, т.е. пока все не сведется к одному узлу.

Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня (Root). Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Выполнив выше сказанное для всех символов получим

М = 00 (2 бита)

К = 0100 (4 бита)

Н = 0101 (4 бита)

Т = 011 (3 бита)

Л = 10 (2 бита)

О = 11 (2 бита)

При кодировании заменяем символы на данные последовательности.

Код Хаффмана является префиксным, то есть код никакого символа не является началом кода какого-либо другого символа. Из этого следует, что код Хаффмана однозначно восстановим получателем, даже если не сообщается длина кода каждого переданного символа.

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

К маленькому файлу прикладывать таблицу кодировки не выгодно, т.к. она займет места больше, чем сам файл. Чем длиннее файл, тем выгоднее этот метод. Метод Хаффмана эффективен для упаковки текстов.

Разархивируйте следующую последовательность: 00111011011110100.

Заархивируйте слово КОЛОКОЛ (010011101101001110).

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

Сжатие данных по Хаффману применяется при сжатии фото- и видеоизображений (JPEG, стандарты сжатия MPEG), в архиваторах (PKZIP, LZH и др.), в протоколах передачи данных MNP5 и MNP7.