Кодирование по Хаффмену. Дерево Хаффмена

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

Один из первых алгоритмов эффективного кодиро­вания информации был предложен Д. А.Хаффменом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, мож­но описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Сим­волам с большей вероятностью присваиваются более короткие коды. Коды Хаффмена имеют уникальный префикс, что и позволяет однозначно их декодиро­вать, несмотря на их переменную длину.

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

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

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

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

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

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

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

Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавлива­ется в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви I.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дере­во кодирования выглядит так, как показано на рис. 1,

Рис. Дерево кодирования Хаффмена после второго шага

На следующем шаге «наилегчайшей» парой оказы­ваются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответст­вует ветви 0 родителя, Г/Д — ветви 1.

На последнем шаге в списке свободных осталось толь­ко два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмена завершается. Н-дерево представлено на следующем рисунке

0

Рис. Окончательное дерево кодирования Хаффмена

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

Для данной таблицы символов коды Хаффмена бу­дут выглядеть следующим образом.

Поскольку ни один из полученных кодов не являет­ся префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством битов, а наиболее редкий символ Д — наибольшим.

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

$ 1.6. Арифметическое кодирование.

Кодирование Хаффмена при сжатии информации коди­рует каждый символ сжимаемого сообщения це­лым количеством битов. Если частота встречае­мости некоторого символа в сообщении очень ве­лика, например 90 из 100, то было бы в принципе возможно поставить в соответствие этому симво­лу код длиной 0,15 бита. Однако схема кодирова­ния Хаффмена может в лучшем случае закоди­ровать такой символ в 1 бит, что в 6 раз менее эффективно.

В 70-е годы у алгоритма Хаффмена появился достойный конкурент — арифметическое кодиро­вание. Этот метод основан на идее преобразования входного потока в одно число с плавающей запя­той. Естественно, что чем длиннее сообщение, тем длиннее получающееся в результате кодирования число. Итак, на выходе арифметического компрес­сора получается число, меньшее 1 и большее либо равное 0. Из этого числа можно однозначно восста­новить последовательность символов, из которых

оно было построено.

Рассмотрим работу арифметического компрессора на при­мере сообщения «BILL GATES».

Поставим в соответ­ствие каждому симво­лу сообщения вероят­ность его появления в сообщении. Затем присвоим каждому символу ин­тервал вероятности в промежутке от 0 до 1. Длина интервала для сим­вола равна вероятности его появления в сообще­нии. Положение интервала вероятности каждого символа не имеет значения. Важно только то, чтобы и кодер, и декодер располагали символы по одинаковым правилам. Интервалы вероятности для символов нашего сообщения приведены в следующей таблице.

В общем виде алгоритм арифметического коди­рования может быть описан следующим образом:

Нижняя граница=0.0;

Верхняя граница=1.0;

Пока (Очередной символ = Дай Очередной символ ())

Интервал =ВерхняяГраница – НижняяГраница;

ВерхняяГраница = НижняяГраница + Интервал * ВерхняяГраницаИнтервалаДля (ОчереднойСимвол);

НижняяГраница = НижняяГраница + Интервал * НижняяГраницаИнтервалаДля(ОчереднойСимвол);

Конец Пока

Выдать (Нижняя граница)

Для нашего случая алгоритм кодирования будет работать следующим образом:

Протокол кодирования:

Алгоритм арифметического декодирования может быть описан следующим образом:

Число = ПрочитатьЧисло ();

Всегда

Символ = НайтиСимволВинтервалКоторогоПопадаетЧисло (Число)

Выдать (Символ)

Интервал = ВерхняяГраницаИнтервалаДля(символ) - НижняяГраницаИнтервалаДля(Символ);

Число = Число – НижняяГраницаИнтервалаДля(Символ);

Число= Число / Интервал;

КонецВсегда

Для нашего примера декодер будет работать следу­ющим образом:

Протокол декодирования

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

Замечание.

Из всего сказанного не видно, в чем преимущество арифметического кодирования перёд кодированием Хаффмена. Разница становится заметна тогда, когда частота встречаемости символов во входном сообще­нии сильно отличается друг от друга.

Пусть заранее известна вероятность появления символа 'Ш' в некотором сообщении, и она равна 0.9.

В следующей таблице показано то, как алгоритм арифметиче­ского кодирования обработает сообщение «ШШШШШШШ!».

Арифметическое кодирование сообщения «ШШШШШШШ!»

Очевидно, что число 0.4375 (в двоичном виде 0.0111) может однозначно закодировать это сообще­ние. Это значит, что мы закодировали сообщение дли­ной 8 символов в 4 бита. Оптимальное кодирование Хаффмена могло бы дать минимум 8 битов.

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

Поиск по сайту: