Алгоритм построения оптимального префиксного кода

Допустим, у нас есть следующая таблица частот: 15 7 6 6 5 А Б В Г Д

Этот процесс можно  представить как построение дерева, корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n0 потомков —  символы из предыдущего шага и  т. д.

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

Для данной таблицы символов коды Хаффмена будут выглядеть следующим образом. А Б В Г Д 0 100 101 110 111

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

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

2.2 Особенности кодирования Хаффмена

 

В создании алгоритма  адаптивного кодирования Хаффмена наибольшие сложности возникают  при разработке процедуры ОбновитьМодельСимволом(); можно было бы просто вставить внутрь этой процедуры полное построение дерева кодирования Хаффмена. В результате мы получили бы самый медленный в мире алгоритм сжатия, так как построение Н-дерева — это слишком большая работа и производить её при обработке каждого символа неразумно. К счастью, существует способ модифицировать уже существующее Н-дерево так, чтобы отобразить обработку нового символа. Обновление дерева при считывании очередного символа сообщения состоит из двух операций. Первая — увеличение веса узлов дерева. Вначале увеличиваем вес листа, соответствующего считанному символу, на единицу. Затем увеличиваем вес родителя, чтобы привести его в соответствие с новыми значениями веса у детей. Этот процесс продолжается до тех пор, пока мы не доберемся до корня дерева. Среднее число операций увеличения веса равно среднему количеству битов, необходимых для того, чтобы закодировать символ. Вторая операция — перестановка узлов дерева — требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности, то есть тогда, когда увеличенный вес узла стал больше, чем вес следующего по порядку узла. Если и дальше продолжать обрабатывать увеличение веса, двигаясь к корню дерева, то наше дерево перестанет быть деревом Хаффмена.

Чтобы сохранить упорядоченность  дерева кодирования, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W+1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдем последний узел с весом W. Переставим текущий и найденный узлы между собой в списке, восстанавливая таким образом порядок в дереве. (При этом родители каждого из узлов тоже изменятся.) На этом операция перестановки заканчивается. После перестановки операция увеличения веса узлов продолжается дальше. Следующий узел, вес которого будет увеличен алгоритмом, — это новый родитель узла, увеличение веса которого вызвало перестановку.

В процессе работы алгоритма  сжатия вес узлов в дереве кодирования  Хаффмена неуклонно растет. Первая проблема возникает тогда, когда  вес корня дерева начинает превосходить вместимость ячейки, в которой  он хранится. Как правило, это 16-битовое значение и, следовательно, не может быть больше, чем 65535. Вторая проблема, заслуживающая ещё большего внимания, может возникнуть значительно раньше, когда размер самого длинного кода Хаффмена превосходит вместимость ячейки, которая используется для того, чтобы передать его в выходной поток. Декодеру все равно, какой длины код он декодирует, поскольку он движется сверху вниз по дереву кодирования, выбирая из входного потока по одному биту. Кодер же должен начинать от листа дерева и двигаться вверх к корню, собирая биты, которые нужно передать. Обычно это происходит с переменной типа «целое», и, когда длина кода Хаффмена превосходит размер типа «целое» в битах, наступает переполнение. Можно доказать, что максимальную длину код Хаффмена для сообщений с одним и тем же входным алфавитом будет иметь, если частоты символов образует последовательность Фибоначчи. Сообщение с частотами символов, равными числам Фибоначчи до Fib (18), — это отличный способ протестировать работу программы сжатия по Хаффмену.

Принимая во внимание сказанное выше, алгоритм обновления дерева Хаффмена должен быть изменен  следующим образом: при увеличении веса нужно проверять его на достижение допустимого максимума. Если мы достигли максимума, то необходимо «масштабировать» вес, обычно разделив вес листьев на целое число, например, 2, а потом пересчитав вес всех остальных узлов. Однако при делении веса пополам возникает проблема, связанная с тем, что после выполнения этой операции дерево может изменить свою форму. Объясняется это тем, что мы делим целые числа и при делении отбрасываем дробную часть.

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

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

2.3 Применение кодирования Хаффмена

 

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

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

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

На практике используются его разновидности. Так, в некоторых  случаях резонно либо использовать постоянную таблицу, либо строить ее "адаптивно", т.е. в процессе архивации/разархивации. Эти приемы избавляют нас от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG и в некоторых других алгоритмах.

Применение кода Хаффмена гарантирует возможность декодирования. Таким образом, можно заключить, что существует метод построения оптимального неравномерного алфавитного кода.

 

Глава 3 Алгоритм построения оптимального префиксного кода

3.1 Характеристики алгоритма Хаффмена

 

Алгоритм Хаффмена — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

Рассмотрим  характеристики, применяемые  к алгоритму Хаффмена:

• худший, средний и лучший коэффициенты сжатия. То есть доля, на которую возрастет изображение, если исходные данные будут наихудшими; некий среднестатистический коэффициент для того класса изображений, на который ориентирован алгоритм; и, наконец, лучший коэффициент. Последний необходим лишь теоретически, поскольку показывает степень сжатия наилучшего (как правило, абсолютно черного) изображения, иногда фиксированного размера;
• класс изображений, на который ориентирован алгоритм. Иногда указано также, почему на других классах изображений получаются худшие результаты;
• симметричность. Отношение характеристики алгоритма кодирования к аналогичной характеристике при декодировании. Характеризует ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важной является симметричность по времени: отношение времени кодирования ко времени декодирования. Иногда нам потребуется симметричность по памяти;
• есть ли потери качества? И если есть, то за счет чего изменяется коэффициент архивации? Дело в том, что у большинства алгоритмов сжатия с потерей информации существует возможность изменения коэффициента сжатия;
• характерные особенности алгоритма и изображений, к которым его применяют. Здесь могут указываться наиболее важные для алгоритма свойства, которые могут стать определяющими при его выборе.

Согласно вышеуказанным представлениям характеристик разберем значения характеристик классического алгоритма Хаффмена:

• коэффициенты компрессии: 8, 1,5, 1 (лучший, средний, худший коэффициенты);
• класс изображений: практически не применяется к изображениям в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах;
• симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных);
• потери качества: без потерь;
• характерные особенности: единственный алгоритм, который не увеличивает размера исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).

3.2 Принцип работы алгоритма  Хаффмена

 

Кодирование – это  правило, описывающее отображение  одного набора знаков в другой набор  знаков. Тогда отображаемый набор  знаков называется исходным алфавитом, а набор знаков, который используется для отображения, – кодовым алфавитом, или алфавитом для кодирования. При этом кодированию подлежат как отдельные символы исходного алфавита, так и их комбинации. Аналогично для построения кода используются как отдельные символы кодового алфавита, так и их комбинации.

Проанализируем принцип работы алгоритма Хаффмена. Алгоритм Хаффмена  использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимися редко — цепочку большей длины. Сжимая файл по алгоритму Хаффмена первое, что мы должны сделать – это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.

После подсчета частоты  вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и  сформировать мнимую компоновку между  кодами по убыванию. То есть, не меняя местонахождение каждого символа из таблицы в памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней таблицы назовем «узлом». В дальнейшем (в дереве) мы будем позже размещать указатели, которые будут указывает на этот «узел». Для ясности давайте рассмотрим пример:

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

 

Таблица 3.1 – Вхождение  символов в файл

Символ	A	B	C	D	E	F
Число вхождений	10	20	30	5	25	10

 

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

 

Таблица 3.2 – Частота  вхождения символов

Символ	C	E	B	F	A	D
Число вхождений	30	25	20	10	10	5

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

Сформируем из узлов D и A новый узел, частота вхождения для которого будет равна сумме частот D и A: Рисунок 3.1 – Формирование нового узла