SoundTrack: RELIZ BY D.J.DARKMAN/SMG 1998
__________________________________________
(C) Diver/CRG
(C) Елена Гладкова/CRG
__________________________________________
Алгоритмы сжатия информации
Часть 1.
Сжатие по Хаффмену
Введение
------------------------------------------
Эта серия статей посвящена системати-
ческому изложению алгоритмов сжатия инфор-
мации. Почему это может быть интересным
для Вас?
Вы хотите знать, как работают програм-
мы сжатия информации? Те алгоритмы сжатия,
которыми они пользуются, будут описаны
подробно и систематично, возможно, если
будут пожелания читателей, в следующий раз
будут включены исходные тексты программ,
иллюстрирующих работу этих алгоритмов. :-)
Вы хотите использовать сжатие информа-
ции в программах, которые Вы пишете, или
собираетесь написать 'самый крутой' упа-
ковщик на Speccy? Вас интересует научная
сторона вопросов сжатия информации? Систе-
матичность изложения и короткие математи-
ческие выкладки помогут Вам получить дос-
таточно основательные знания по этой проб-
леме.
Магическая формула:
СЖАТИЕ=МОДЕЛИРОВАНИЕ+КОДИРОВАНИЕ
------------------------------------------
Сжатие информации - это процесс сокращения
количества битов, необходимых для хранения
некоторого объема информации.
Сжатие без потерь - информация, восстанов-
ленная из сжатого состояния, в точности
соответствует исходной (до начала сжатия).
Сжатие с потерями - информация, восстанов-
ленная после сжатия, только частично соот-
ветствует исходной (применяется при обра-
ботке изображений и звука).
Вообще говоря, сжатие информации пред-
ставляет собой процесс обработки символов
некоторого сообщения и перевода этих сим-
волов в некоторые коды. Если этот процесс
организован эффективно, то получающееся в
результате закодированное сообщение зани-
мает меньше места, чем исходное.
При просмотре обрабатываемого сообще-
ния алгоритм сжатия реализует два почти
независимых друг от друга процесса:
- поддерживает МОДЕЛЬ обрабатываемого со-
общения;
- на основании модели КОДИРУЕТ очередной
фрагмент сообщения.
Обычно весь процесс сжатия ошибочно
отождествляется только с процессом КОДИРО-
ВАНИЯ,в то время как КОДИРОВАНИЕ представ-
ляет собой только часть процесса сжатия,
взаимодействующую с моделью данных. При
этом результат сжатия будет отличаться для
различных методов моделирования.
Так что,если Вы когда-либо услышите за-
явление типа: "Кодирование Хаффмена дает
оптимальные результаты, это доказано мате-
матически", - или наоборот: "Кодирование
Хаффмана вообще не дает хороших результа-
тов", - отнеситесь к этому спокойно. И то
и другое, по крайней мере, - некорректные
утверждения. В каждом случае общие ре-
зультаты работы алгоритма сжатия зависят и
от метода моделирования и от метода коди-
рования.
Кодирование Хаффмена
------------------------------------------
Граф - совокупность множества узлов и мно-
жества дуг, напрвленны от одного узла к
другому.
Дерево - граф, обладающий следующими свой-
ствами:
а) ни в один из узлов не входит более од-
ной дуги (то есть отсутствуют циклы);
б) только в один узел не входит ни одной
дуги, он называется корнем дерева;
в) перемещаясь по дугам от корня, можно
попасть в любой узел.
Лист дерева - узел,из которого не выхо-
дит ни одной дуги. В паре узлов дерева,со-
единенных между собой дугой, тот, из кото-
рого она выходит, называется родителем,
другой же - ребенком. Два узла называются
братьями,если имеют одного и того же роди-
теля.
Двоичное дерево - дерево, у которого из
всех узлов, кроме листьев, выходит по две
дуги.
Дерево кодирования Хаффмена(далее H-де-
рево) - двоичное дерево, у которого каждый
узел имеет вес, и вес родителя равен сум-
марному весу его детей.
Входной алфавит - множество символов,
входящих в сообщение.
В конце сороковых годов, на заре разви-
тия теории информации, идеи разработки но-
вых эффективных способов кодирования ин-
формации носились в воздухе. Исследовате-
ли занимались вопросами энтропии, содержи-
мого информации и избыточности. Интересно,
что эти первоначальные работы в области
сжатия информации велись до появления сов-
ременного цифрового компьютера. Сегодня
теория информации развивается параллельно
с программированием, но в то время идея
разработки алгоритмов, использующих двоич-
ную арифметику для кодирования символов,
была значительным шагом в перед.
Один из первых алгоритмов эффективного
кодирования информации был предложен Д.А.
Хаффменом в 1952 году. Идея алгоритма сос-
тоит в следующем: зная вероятности вхожде-
ния символов в сообщение, можно описать
процедуру построения кодов переменной дли-
ны, состоящей из целого количества битов.
Символам с большей вероятностью присваива-
ются более короткие коды. Коды Хаффмена
имеют уникальный префикс, что и позволяет
однозначно их декодировать, несмотря на их
переменную длину.
Классический алгоритм Хаффмена на вхо-
де получает таблицу частот встречаемости
символов в сообщении. Далее на основании
этой таблицы строится дерево кодирования
Хаффмена (H-дерево). Алгоритм построения
H-дерева прост и элегантен.
1. Символы входного алфавита образуют
список свободных узлов. Каждый лист имеет
вес, который может быть равен либо вероят-
ности, либо количеству вхождений символа в
сжимаемое сообщение.
2. Выбираются два свободных узла дере-
ва с наименьшими весами.
3. Создается их родитель с весом, рав-
ным их суммарному весу.
4. Родитель добавляется в список сво-
бодных узлов,а двое его детей удаляются из
этого списка.
5. Одной дуге, выходящей из родителя,
ставится в соответствие бит 1, другой -
- бит 0.
6. Шаги, начиная со второго, повторяют-
ся до тех пор, пока в списке свободных уз-
лов не останется только один свободный
узел. Он и будет считаться корнем дерева.
Допустим, у нас есть следующая таблица
частот:
15 7 6 6 5
А Б В Г Д
На первом шаге из листьев дерева выби-
раются два с наименьшими весами - Г и Д.
Они присоединяются к новому узлу-родителю,
вес которого устанавливается в 5+6=11. За-
тем узлы Г и Д удаляются из списка свобод-
ных. Узел Г соответствует ветви 0 родите-
ля, узел Д - ветви 1.
На следующем шаге то же происходит с
узлами Б и В,так как теперь эта пара имеет
самый меньший вес в дереве. Создается но-
вый узел с весом 13, а узлы Б и В удаляют-
ся из списка свободных. После всего этого
дерево кодирования выглядит так, как пока-
зано на рис.1.
0 ┌────┐ 1 0 ┌────┐ 1
┌──┤ 13 ├──┐ ┌──┤ 11 ├──┐
│ └────┘ │ │ └────┘ │
┌───┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│15 │ │ 7 │ │ 6 │ │ 6 │ │ 5 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤
│ А │ │ Б │ │ В │ │ Г │ │ Д │
└───┘ └───┘ └───┘ └───┘ └───┘
Рис.1. Дерево кодирования Хаффмена пос-
ле второго шага.
На следующем шаге "наилегчайшей" парой
оказываются узлы Б/В и Г/Д. Для них еще
раз создается родитель, теперь уже с ве-
сом 24. Узел Б/В соответствует ветви 0 ро-
дителя, Г/Д - ветви 1.
На последнем шаге в списке свободных
осталось только два узла - это узел А и
узел (Б/В)/(Г/Д). В очередной раз создает-
ся родитель с весом 39 и бывшие свободны-
ми узлы присоединяются к разным его вет-
вям.
Поскольку свободным остался только один
узел, то алгоритм построения дерева коди-
рования Хаффмена завершается. H - дерево
представлено на рис.2.
0 ┌────┐ 1
┌────┤ 39 ├──────────────────┐
│ └────┘ │
│ 0 ┌─┴──┐ 1
│ ┌────────┤ 24 ├─────────┐
│ │ └────┘ │
│ 0 ┌──┴─┐ 1 0 ┌─┴──┐ 1
│ ┌──┤ 13 ├──┐ ┌──┤ 11 ├──┐
│ │ └────┘ │ │ └────┘ │
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│15 │ │ 7 │ │ 6 │ │ 6 │ │ 5 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤
│ А │ │ Б │ │ В │ │ Г │ │ Д │
└───┘ └───┘ └───┘ └───┘ └───┘
Рис.2. Окончательное дерево кодирования
Хаффмена.
Чтобы определить код для каждого из
символов, входящих в сообщение, мы должны
пройти путь от листа дерева, соответствую-
щего этому символу, до корня дерева, на-
капливая биты при перемещении по ветвям
дерева. Полученная таким образом последо-
вательность битов является кодом данного
символа, записанным в обратном порядке.
Для данной таблицы символов коды Хаф-
фмена будут выглядеть следующим образом.
А 0
Б 100
В 101
Г 110
Д 111
Поскольку ни один из полученных кодов
не совпадает с префиксом другого, они мо-
гут быть однозначно декодированы при чте-
нии их из потока. Кроме того,наиболее час-
тый символ сообщения А закодирован наи-
меньшим количством битов, а наиболее ред-
кий символ Д - наибольшим.
Классический алгоритм Хаффмена имеет
существенный недостаток. Для восстановле-
ния содержимого сжатого сообщения декодер
должен знать таблицу частот, которой поль-
зовался кодер. Следовательно,длина сжатого
сообщения увеличивается на длину таблицы
частот, которая должна поступать впереди
данных, что может свести на нет все усилия
по сжатию сообщения. Кроме того, необходи-
мость наличия полной частотной статистики
перед началом, собственно,кодирования тре-
бует двух проходов по сообщению:одного для
построения модели сообщения (таблицы час-
тот и H-дерева), другого для, собственно,
кодирования.
Адаптивное сжатие
------------------------------------------
Адаптивное сжатие позволяет не переда-
вать модель сообщения вместе с ним самим и
ограничится одним проходом по сообщению
как при кодировании, так и при декодирова-
нии.
Практически любая форма кодирования мо-
жет быть конвертирована в адаптивную. В
общем случае программа, реализующая адап-
тивное сжатие, может быть выражена в сле-
дующей форме:
ИнициализироватьМодель();
Пока не конец сообщения
Символ=ВзятьСледующийСимвол();
Закодировать(Символ);
Обновить модельСимволом(Символ);
Конец Пока
Декодер в адаптивной схеме работает
аналогичным образом:
ИнициализироватьМодель();
Пока не конец сжатой информации
Символ=РаскодироватьСледующийСимвол();
ВыдатьСимвол(Символ);
ОбновитьМодельСимволом(Символ);
Конец Пока
Схема адаптивного кодирования/декодиро-
вания работает благодаря тому, что и при
кодировании, и при декодировании использу-
ются одни и те же процедуры "Инициализиро-
вать модель" и "ОбновитьМодельСимволом". И
компрессор,и декомпрессор начинают с "пус-
той" модели не содержащей информации о
сообщении) и с каждым просмотренным симво-
лом обновляют ее одинаковым образом.
Адаптивное кодирование Хаффмена
------------------------------------------
Следующим шагом в развитии алгоритма
Хаффмена стала его адаптивная версия. Ей в
основном и посвящена эта статья.
В создании алгоритма адаптивного коди-
рования Хаффмена наибольшие сложности воз-
никают при разработке процедуры Обновить
МодельСимволом(); можно было бы просто
вставить внутрь этой процедуры полное пос-
троение дерева кодирования Хаффмена. В ре-
зультате мы получили бы самый медленный
в мире алгоритм сжатия, так как построение
H-дерева - это слишком большая работа и
производить ее при обработке каждого сим-
вола неразумно. К счастью, существует спо-
соб модифицировать уже существующее H-де-
рево так, чтобы отобразить обработку ново-
го символа.
Упорядоченное дерево
------------------------------------------
Будем говорить, что дерево обладает
свойством упорядоченности, если его узлы
могут быть перечислены в порядке возраста-
ния веса и в этом перечислении,каждый узел
находится рядом со своим братом. Пример
упорядоченного дерева приведен на рис.3.
Здесь W - вес узла, N - порядковый номер в
списке узлов.
╔════╗
║W=17║
┌─────────────╟────╢───────────────┐
│ ║N=9 ║ │
╔══╧═╗ ╚════╝ ╔══╧═╗
║W=7 ║ ║ Д ║
┌───────╟────╢──────────────┐ ╟────╢
│ ║N=7 ║ │ ║W=10║
╔══╧═╗ ╚════╝ ╔══╧═╗ ╟────╢
║W=3 ║ ║W=4 ║ ║N=8 ║
┌──────╟────╢───────┐ ┌──────╟────╢───────┐ ╚════╝
│ ║N=5 ║ │ │ ║N=6 ║ │
╔══╧═╗ ╚════╝ ╔══╧═╗ ╔══╧═╗ ╚════╝ ╔══╧═╗
║ А ║ ║ Б ║ ║ В ║ ║ Г ║
╟────╢ ╟────╢ ╟────╢ ╟────╢
║W=1 ║ ║W=2 ║ ║W=2 ║ ║W=2 ║
╟────╢ ╟────╢ ╟────╢ ╟────╢
║N=1 ║ ║N=2 ║ ║N=3 ║ ║N=4 ║
╚════╝ ╚════╝ ╚════╝ ╚════╝
Рис.3. Свойство упорядоченности дерева
кодирования Хаффмена.
Примем без доказательства утверждение о
том, что двоичное дерево является деревом
кодирования Хаффмена тогда и только тогда,
когда оно удовлетворяет свойству упорядо-
ченности.
Сохранение свойства упорядоченности в
процессе обновления дерева позволяет нам
быть уверенными в том, что двоичное дере-
во, с которым мы работаем, - это H-дерево
и до, и после обновления веса у листьев
дерева.
Обновление дерева при считывании оче-
редного символа сообщения состоит из двух
операций.
Первая - увеличение веса узлов дерева -
представлена на рис.4. Вначале увеличи-
ваем вес листа, соответствующего считанно-
му символу, на единицу. Затем увеличиваем
вес родителя, чтобы привести его в соот-
ветствие с новыми значениями веса у детей.
Этот процесс продолжается до тех пор, по-
ка мы не доберемся до корня дерева. Сред-
нее число операций увеличения веса равно
среднему количеству битов, необходимых для
того, чтобы закодировать символ. Вторая
операция - перестановка узлов дерева -тре-
буется тогда, когда увеличение веса узла
приводит к нарушению свойства упорядочен-
ности, то есть тогда,когда увеличенный вес
узла стал больше,чем вес следующего по по-
рядку узла (рис. 5). Если и дальше продол-
жать обрабатывать увеличение веса,двигаясь
к корню дерева, то наше дерево перестанет
быть деревом Хаффмена.
шаг4 ╔════╗
║W=18║
┌─────────────╟────╢───────────────┐
│ ║N=9 ║ │
шаг3 ╔══╧═╗ ╚════╝ ╔══╧═╗
║W=8 ║ ║ Д ║
┌───────╟────╢──────────────┐ ╟────╢
│ ║N=7 ║ │ ║W=10║
шаг2 ╔══╧═╗ ╚════╝ ╔══╧═╗ ╟────╢
║W=4 ║ ║W=4 ║ ║N=8 ║
┌──────╟────╢───────┐ ┌──────╟────╢───────┐ ╚════╝
шаг1│ ║N=5 ║ │ │ ║N=6 ║ │
╔══╧═╗ ╚════╝ ╔══╧═╗ ╔══╧═╗ ╚════╝ ╔══╧═╗
║ А ║ ║ Б ║ ║ В ║ ║ Г ║
╟────╢ ╟────╢ ╟────╢ ╟────╢
║W=2 ║ ║W=2 ║ ║W=2 ║ ║W=2 ║
╟────╢ ╟────╢ ╟────╢ ╟────╢
║N=1 ║ ║N=2 ║ ║N=3 ║ ║N=4 ║
╚════╝ ╚════╝ ╚════╝ ╚════╝
Рис.4. Процедура обновления дерева кодиро-
вания при увеличении веса листа А.
╔════╗
║W=18║
┌─────────────╟────╢───────────────┐
│ ║N=9 ║ │
╔══╧═╗ ╚════╝ ╔══╧═╗
║W=8 ║ ║ Д ║
┌───────╟────╢──────────────┐ ╟────╢
│ ║N=7 ║ │ ║W=10║
╔══╧═╗ ╚════╝ ╔══╧═╗ ╟────╢
║W=4 ║ ║W=4 ║ ║N=8 ║
┌──────╟────╢───────┐ ┌──────╟────╢───────┐ ╚════╝
│ ║N=5 ║ │ │ ║N=6 ║ │
╔══╧═╗ ╚════╝ ╔══╧═╗ ╔══╧═╗ ╚════╝ ╔══╧═╗
║ А ║ ║ Б ║ ║ В ║ ║ Г ║
╟────╢ ╟────╢ ╟────╢ ╟────╢
║W=3 ║ ║W=2 ║ ║W=2 ║ ║W=2 ║
╟────╢ ╟────╢ ╟────╢ ╟────╢
║N=1 ║ ║N=2 ║ ║N=3 ║ ║N=4 ║
╚════╝ ╚════╝ ╚════╝ ╚════╝
Рис.5. При увеличении веса листа А наруша-
ется свойство упорядоченности.
Чтобы сохранить упорядоченность дерева
кодирования, алгоритм работает следующим
образом. Пусть новый увеличенный вес узла
равен W+1. Тогда начинаем двигаться по
списку в сторону увеличения веса, пока не
найдем последний узел с весом W. Переста-
вим текущий и найденный узлы между собой в
списке (рис.6), восстанавливая таким обра-
зом порядок в дереве. (При этом родители
каждого из узлов тоже изменятся.) На этом
операция перестановки заканчивается.
╔════╗
║W=18║
┌─────────────╟────╢───────────────┐
│ ║N=9 ║ │
╔══╧═╗ ╚════╝ ╔══╧═╗
║W=8 ║ ║ Д ║
┌───────╟────╢──────────────┐ ╟────╢
│ ║N=7 ║ │ ║W=10║
╔══╧═╗ ╚════╝ ╔══╧═╗ ╟────╢
║W=4 ║ ║W=4 ║ ║N=8 ║
┌──────╟────╢───────┐ ┌──────╟────╢───────┐ ╚════╝
│ ║N=5 ║ │ │ ║N=6 ║ │
╔══╧═╗ ╚════╝ ╔══╧═╗ ╔══╧═╗ ╚════╝ ╔══╧═╗
║ Г ║ ║ Б ║ ║ В ║ ║ А ║
╟────╢ ╟────╢ ╟────╢ ╟────╢
║W=2 ║ ║W=2 ║ ║W=2 ║ ║W=3 ║
╟────╢ ╟────╢ ╟────╢ ╟────╢
║N=1 ║ ║N=2 ║ ║N=3 ║ ║N=4 ║
╚════╝ ╚════╝ ╚════╝ ╚════╝
Рис.6. Дерево кодирования после первой пе-
рестановки узлов Г и А.
После перестановки операция увеличения
веса узлов продолжается дальше. Следующий
узел, вес которого будет увеличен алгорит-
мом, - это новый родитель узла, увеличение
веса которого вызвало перестановку.
Предположим, что символ А встретился в
сообщении еще два раза вподряд. Дерево ко-
дирования после двукратного вызова проце-
дуры обновления показано на рис.7.
╔════╗
║W=21║
┌──────╫────╫──────┐
╔══╧═╗ ║N=9 ║ ╔═╧══╗
║ Д ║ ╚════╝ ║W=11║
╟────╢ ┌──────╟────╢──────┐
║W=10║ │ ║N=8 ║ │
╟────╢ ╔══╧═╗ ╚════╝ ╔═╧══╗
║N=7 ║ ║ А ║ ║W=6 ║
╚════╝ ╟────╢ ┌─────╫────╢────────┐
║W=5 ║ │ ║N=6 ║ │
╟────╢ │ ╚════╝ ╔═╧══╗
║N=5 ║ ╔══╧═╗ ║W=4 ║
╚════╝ ║ В ║ ┌─────╫────╢────────┐
╟────╢ │ ║N=4 ║ │
║W=2 ║ │ ╚════╝ │
╟────╢ │ │
║N=3 ║ ╔══╧═╗ ╔══╧═╗
╚════╝ ║ Г ║ ║ Б ║
╟────╢ ╟────╢
║W=2 ║ ║W=2 ║
╟────╢ ╟────╢
║N=1 ║ ║N=2 ║
╚════╝ ╚════╝
Рис.7. Дерево после завершения процедуры
обновления.
Обратите внимание, как обновление дере-
ва кодирования отражается на длине кодов
Хаффмена для входящих в данное сообщение
символов.
В целом алгоритм обновления дерева мо-
жет быть записан следующим образом:
ОбновитьМодельСимволом(Символ)
{
ТекущийУзел=ЛистСоответствующий(Символ)
Всегда
УвеличитьВес(ТекущийУзел)
Если (ТекущийУзел=КореньДерева) Выход;
Если (Вес(ТекущийУзел)>
Вес(СледующийЗа(ТекущийУзел)))
Перестановка();
ТекущийУзел=Родитель(ТекущийУзел);
Конец Всегда
}
Проблемы адаптивного кодирования
------------------------------------------
Инициализация
Хорошо было бы, чтобы кодер не тратил
зря кодовое пространство на символы, кото-
рые не встречаются в сообщении.
Если речь идет о классическом алгорит-
ме Хаффмена, то символы, которые не встре-
чаются в сообщении, уже известны до нача-
ла кодирования, так как известна таблица
частот и символы, у которых частота встре-
чаемости равна 0. В адаптивной версии ал-
горитма мы не можем заранее знать, какие
символы появятся в сообщении. Можно прои-
нициализировать дерево Хаффмена так, что-
бы оно имело все 256 символов алфавита
(для 8-битовых кодов) с частотой,равной 1.
В начале кодирования каждый код будет
иметь длину 8 битов. По мере адаптации мо-
дели наиболее часто встречающиеся символы
будут кодироваться все меньшим и меньшим
количеством битов. Такой подход работоспо-
собен, но он значительно снижает степень
сжатия, особенно на коротких сообщениях.
Лучше начинать моделирование с пустого
дерева и добавлять в него символы только
по мере их появления в сжимаемом сообще-
нии. Но это приводит к очевидному противо-
речию: когда символ появляется в сообще-
нии в первый раз, он не может быть закоди-
рован, так как его еще нет в дереве коди-
рования.
Чтобы разрешить это противоречие, вве-
дем специальный ESCAPE код,который для де-
кодера будет означать, что следующий сим-
вол закодирован вне контекста модели сооб-
щения. Например, его можно передать в по-
ток сжатой информации как есть, не кодируя
вообще. Метод "ЗакодироватьСимвол" в алго-
ритме адаптивного кодирования Хаффмена
можно записать следующим образом.
ЗакодироватьСимвол(Символ)
{
Если СимволУжеЕстьВТаблице(Символ)
ВыдатьКодХаффменаДляСимвола(Символ)
Иначе
{
ВыдатьКодХаффменаДляСимвола(ESCAPE)
ВыдатьСимвол(Символ)
}
}
Использование специального символа ES-
CAPE подразумевает определенную инициали-
зацию дерева до начала кодирования и деко-
дирования: в него помещаются 2 специальных
символа: ESCAPE и EOF (конец файла), с ве-
сом, равным 1 (рис.8). Поскольку процесс
обновления дерева не коснется их веса, то
по ходу кодирования они будут перемещаться
на самые удаленные ветви дерева и иметь
самые длинные коды.
ROOT
┌───┐
┌────────┤ 2 ├──────────┐
┌──┴──┐ └───┘ ┌──┴──┐
│ EOF │ │ ESC │
├─────┤ ├─────┤
│ 1 │ │ 1 │
└─────┘ └─────┘
Рис.8. Дерево кодирования после инициали-
зации
Переполнение
В процессе работы алгоритма сжатия вес
узлов в дереве кодирования Хаффмена неук-
лонно растет. Первая проблема возникает
тогда, когда вес корня дерева начинает
превосходить вместимость ячейки, в кото-
рой он хранится. Как правило, это 16-бито-
вое значение и, следовательно, не может
быть больше, чем 65535. Вторая проблема,
заслуживающая еще большего внимания, мо-
жет возникнуть значительно раньше, когда
размер самого длинного кода Хаффмена пре-
восходит вместимость ячейки, которая ис-
пользуется для того, чтобы передать его в
выходной поток. Декодеру все равно, какой
длины код он декодирует, поскольку он дви-
жется сверху вниз по дереву кодирования,
выбирая из входного потока по одному биту.
Кодер же должен начинать от листа дерева и
двигаться вверх к корню, собирая биты, ко-
торые нужно передать. Обычно это происхо-
дит с переменной типа "целое", и, когда
длина кода Хаффмена превосходит размер ти-
па "целое" в битах,наступает переполнение.
SoundTrack: NIK-O: -=CrAzY NOSTALGIE=- ...
__________________________________________
Можно доказать, что максимальную длину
код Хаффмена для сообщений с одни и тем же
входным алфавитом будет иметь, если часто-
ты символов образуют последовательность
Фибоначчи (рис.9).
┌────┐
┌────────┤W=13├─┐
┌─┴──┐ └────┘ │
┌───────┤W=8 ├─┐ │
┌──┴─┐ └────┘ │ │
┌───────┤W=5 ├─┐ │ │
┌──┴─┐ └────┘ │ │ │
┌───────│W=3 ├──┐ │ │ │
┌──┴─┐ └────┘ │ │ │ │
┌──┤W=2 ├─┐ │ │ │ │
│ └────┘ │ │ │ │ │
│ │ │ │ │ │
┌─┴──┐ ┌─┴──┐ ┌──┴─┐ ┌─┴──┐ ┌─┴──┐ ┌─┴──┐
│W=1 │ │W=1 │ │W=1 │ │W=2 │ │W=3 │ │W=5 │
├────┤ ├────┤ ├────┤ ├────┤ ├────┤ ├────┤
│ А │ │ Б │ │ В │ │ Г │ │ Д │ │ Е │
└────┘ └────┘ └────┘ └────┘ └────┘ └────┘
Рис.9. Дерево Хаффмена на числах Фибоначчи
Функция Фибоначчи определяется следую-
щим образом.
int Fib(int n)
{
if (n<=1) return 1;
else return (Fib(n-1)+Fib(n-2));
}
Функция написана на языке C, но, надеюсь,
смысл понятен. Например:
Fib(5)=Fib(4)+Fib(3)=Fib(3)+Fib(2) +
Fib(2)+Fib(1)=Fib(2)+Fib(1)+Fib(1)+Fib(0)+
Fib(1)+Fib(0)+1=Fib(1)+Fib(0)+6=8.
Если вес корневого узла в дереве Хаф-
фмена равен Fib(i), то наиболее длинный
код, возможный для этого дерева,имеет дли-
ну i-1.
Это означает, что если "целые", исполь-
зуемые для представления весов в дереве
Хаффмена, имеют длину 16 битов,то вес кор-
ня, равный 4181 (Fib(18)), может привести
к переполнению. (Вообще говоря, сообщение
с частотами символов, равными числам Фибо-
наччи до Fib(18),-это отличный способ про-
тестировать работу программы сжатия по
Хаффмену.)
Масштабирование весов узлов H-дерева
------------------------------------------
Принимая во внимание сказанное выше,
алгоритм обновления дерева Хаффмена дол-
жен быть изменен следующим образом: при
увеличении веса нужно проверять его на
достижение допустимого максимума. Если мы
достигли максимума, то необходимо "масшта-
бировать" вес, обычно разделив вес лис-
тьев на целое число, например, 2, а потом
пересчитав вес остальных всех узлов.
Однако при делении веса попалам возни-
кает проблема, связанная с тем, что после
выполнения этой операции дерево может из-
менить свою форму. Объясняется это тем,
что мы делим целые числа и при делении от-
брасываем дробную часть.
Правильно организованное дерево Хаффме-
на после масштабирования может иметь фор-
му, значительно отличающуюся от исходной.
Это происходит потому, что масштабирова-
ние приводит к потере точности нашей ста-
тистики. Но со сбором новой статистики
последствия этих "ошибок" практически схо-
дят на нет. Масштабирование веса - доволь-
но дорогостоящая операция,так как она при-
водит к необходимости заново строить все
дерево кодирования. Но, так как необходи-
мость в ней возникает относительно редко,
то с этим можно смириться.
Выигрыш от масштабирования
------------------------------------------
Масштабирование веса узлов дерева че-
рез определенные интервалы дает неожидан-
ный результат. Несмотря на то,что при мас-
штабировании происходит потеря точности
статистики, тесты показывают, что оно при-
водит к лучшим показателям сжатия, чем ес-
ли бы масштабирование откладывалось. Это
можно объяснить тем, что текущие символы
сжимаемого потока больше "похожи" на своих
близких предшественников, чем на тех, ко-
торые встречались намного раньше. Масшта-
бирование приводит к уменьшению влияния
"давних" символов на статистику и к увели-
чению влияния на нее "недавних" символов.
Это очень сложно измерить количественно,
но, в принципе, масштабирование оказывает
положительное влияние на степень сжатия
информации. Эксперименты с масштабирова-
нием в различных точках процесса сжатия
показывают, что степень сжатия сильно за-
висит от момента масштабирования веса, но
не существует правила выбора оптимального
момента масштабирования для программы,
ориентированной на сжатие любых типов ин-
формации.
Заключение
------------------------------------------
С тех пор, как Д.А.Хаффмен опубликовал
в 1952 году свою работу "Метод построения
кодов с минимальной избыточностью",его ал-
горитм кодирования стал базой для огромно-
го количества дальнейших исследований в
этой области. По сей день в компьютерных
журналах можно найти большое количество
публикаций, посвященных как различным реа-
лизациям алгоритма Хаффмена, так и поис-
кам его лучшего применения. Кодирование
Хаффмена используется в коммерческих прог-
раммах сжатия, встроено в некоторые теле-
факсы и даже используется в алгоритме JPEG
сжатия графических изображений с потерями.
THE END.
Содержание последующих статей:
- Арифмитическое кодирование
- Алгоритмы группы LZ(Lempel-Ziv)
- Алгоритм LZW(Lempel-Ziv-Welch)
- Пишем свой упаковщик или
Комбинированные схемы сжатия
- etc...
