Deja Vu #06 30 сентября 1998

Программирование

CODING - Алгоритмы сжатия информации.

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