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...