Sources
Delphi Russian Knowledge Base
DRKB - это самая большая и удобная в использовании база знаний по Дельфи в рунете, составленная Виталием Невзоровым

Применение расширяющихся деревьев для сжатия данных

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

Алгоритмы сжатия могут повышать эффективность хранения и передачи данных посредством сокращения количества их избыточности. Алгоритм сжатия берет в ка- честве входа текст источника и производит соответствующий ему сжатый текст, когда как разворачивающий алгоритм имеет на входе сжатый текст и получает из него на выходе первоначальный текст источника (1). Большинство алгоритмов сжа- тия рассматривают исходный текст как набор строк, состоящих из букв алфавита исходного текста.

Избыточность в представлении строки S есть L(S) - H(S), где L(S) есть дли- на представления в битах, а H(S) - энтропия - мера содержания информации, так- же выраженная в битах. Алгоритмов, которые могли бы без потери информации сжать строку к меньшему числу бит, чем составляет ее энтропия, не существует. Если из исходного текста извлекать по одной букве некоторого случайного набо- pа, использующего алфавит А, то энтропия находится по формуле:

                   --+           1

        H(S) = C(S)    p(c) log ---- ,

                   c A          p(c)

где C(S) есть количество букв в строке, p(c) есть статическая вероятность по- явления некоторой буквы C. Если для оценки p(c) использована частота появления каждой буквы c в строке S, то H(C) называется самоэнтропией строки S. В этой статье H (S) будет использоваться для обозначения самоэнтропии строки, взятой из статичного источника.

Модели, основанные на применении статичной вероятности, не позволяют хоро- шо характеризовать многие источники. Например, в английском тексте, буква U менее распространена чем E, поэтому модель статичной вероятности будет непра- вильно предсказывать, что QE должно быть более растространенным сочетанием, чем QU. Хорошо описывать такие источники позволяют вероятностные модели Марко- ва. Источники Маркова имеют множество состояний, смена которых происходит при появлении очередной буквы. Каждое состояние связывается с распределением веро- ятности, определяющим следующее состояние модели и следующую производимую бук- ву. Когда марковский источник, представляющий собой текст, подобный английско- му, выдает букву Q, он установливает состояние, в котором U есть более вероят- ный вывод. Дальнейшее изучение вопросов, связанных с энтропией, статичными ис- точниками и источниками Маркова может быть продолжено в большинстве книг по теории информации [2].

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

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

КОДЫ ПРЕФИКСОВ.

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

Коды префикса могут быть найдены посредством дерева, в котором каждый лист соответствует одной букве алфавита источника. Hа pисунке 1 показано дерево ко- да префикса для алфавита из 4 букв. Код префикса для буквы может быть прочитан при обходе деpева от корня к этой букве, где 0 соответствует выбору левой его ветви, а 1 - правой. Дерево кода Хаффмана есть дерево с выравненным весом, где каждый лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно.

     0           0            0

A ---------- o ---------- o ---------- o

           |            |            |          A = 000

           |1           |1           |1         B = 001

           |            |            |          C = 01

           B            C            D          D = 1

Рисунок 1. Дерево представления кода префикса.

Обычные коды Хаффмана требуют предварительной информации о частоте встре- чаемости букв в исходном тексте, что ведет к необходимости его двойного про- смотра - один для получения значений частот букв, другой для проведения самого сжатия. В последующем, значения этих частот нужно объединять с самим сжатым текстом, чтобы в дальнейшем сделать возможным его развертывание. Адаптивное сжатие выполняется за один шаг, т.к. код, используемый для каждой буквы исход- ного текста, основан на частотах всех остальных кpоме нее букв алфавита. Осно- вы для эффективной реализации адаптивного кода Хаффмана были заложены Галлаге- ром[3], Кнут опубликовал практическую версию такого алгоритма[5], а Уиттер его pазвил[10].

Оптимальный адаптированный код Уиттера всегда лежит в пределах одного би- та на букву источника по отношению к оптимальному статичному коду Хаффмана, что обычно составляет несколько процентов от H . К тому же, статичные коды Хаффмана всегда лежат в пределах одного бита на букву исходного текста от H ( они достигают этот предел только когда для всех букв p(C) = 2 ). Такие же ограничения могут быть отнесены к источникам Маркова, если статичное или адап- тированное дерево Хаффмана используется для каждого состояния источника, выве- деного из его исходного текста. Существуют алгоритмы сжатия которые могут пре- одолевать эти ограничения. Алгоритм Зива-Лемпелла, например, присваивает слова из аpхива фиксированной длины строкам исходного текста пеpеменной длины[11], а арифметическое сжатие может использовать для кодирования букв источника даже доли бита[12].

Применение расширения к кодам префикса.

Расширяющиеся деревья были впервые описаны в 1983 году[8] и более подpобно рассмотрены в 1985[9]. Первоначально они понимались как вид самосбалансиpован- ных деpевьев двоичного поиска, и было также показано, что они позволяют осуще- ствить самую быструю реализацию приоритетных очередей[4]. Если узел расширяю- щегося дерева доступен, то оно является расширенным. Это значит, что доступный узел становится корнем, все узлы слева от него образуют новое левое поддерево, узлы справа - новое правое поддерево. Расширение достигается при обходе дере- ва от старого корня к целевому узлу и совершении пpи этом локальных изменений, поэтому цена расширения пропорциональна длине пройденного пути.

Тарьян и Слейтон[9] показали, что расширяющиеся деревья статично оптималь- ны. Другими словами, если коды доступных узлов взяты согласно статичному рас- пределению вероятности, то скорости доступа к расширяющемуся дереву и статич- но сбалансированному, оптимизированному этим распределением, будут отличаться друг от друга на постоянный коэффициент, заметный при достаточно длинных сери- ях доступов. Поскольку дерево Хаффмана представляет собой пример статично сба- лансированного дерева, то пpи использовании расширения для сжатия данных, pаз- мер сжатого текста будет лежать в пределах некоторого коэффициента от размера архива, полученного при использовании кода Хаффмана.

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

В случае зигзагообразного обхода лексикографического дерева, проведение как расширения, так и полурасширения усложняется, в отличие от прямого маршру- та по левому или правому краю дерева к целевому узлу ( случаи зигзага рассмот- рены в [8], [9] ). Этот простой случай показан на рисунке 2. Воздействие полу- расширения на маршруте от корня ( узел w ) до листа узла A заключается в пере- мене местами каждой пары внутренних следующих друг за другом узлов, в резуль- тате чего длина пути от корня до узла-листа сокращается в 2 раза. В процессе полурасширения узлы каждой пары, более далекие от корня, включаются в новый путь ( узлы x и z ), а более близкие из него исключаются ( узлы w и y ).

    0          0         0         0       .        0             0

A ------ --o---------o-- ---- --o---------o  . A ----------o-------------o

        z|        y|         x|        w|  .            z|            x|

         |1        |1         |1        |1 .             |1            |1

         |         |          |         |  .       0     |        0    |

         B         C          D         E  . B ----------o  D ---------o

                                           .            y|            w|

                                |          .             |1            |1

                                +=======>  .             |             |

                                           .             C             E

Рисунок 2. Полурасширение вокруг самого левого листа дерева кодов.

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

Hенужность поддержки лексикографического порядка значительно упрощает про- ведение операции полурасширения за счет исключения случая зигзага. Это может быть сделано проверкой узлов на пути от корня к целевому листу и переменой ме- стами правых наследников с их братьями. Назовем это ПОВОРОТОМ дерева. Тепеpь новый код префикса для целевого листа будет состоять из одних нулей, поскольку он стал самым левым листом. На рисунке 3 дерево было повернуто вокруг листа C. Эта операция не нарушает никаких ограничений представления полурасширения. До- казательство этого просто выводится из потенциальной функции, приведенной в [9] для доказательства независимости ограничений представления от порядка сле- дования поддеревьев узла.

     0          0         .         0          0          0          0

A ----------o----------o    .  C ----------o----------o----------o----------o

         x|         w|    .             z|         y|         x|         w|

          |1         |1   .              |1         |1         |1         |1

     0    |          |    .              |          |          |          |

B ----------o          E    .              D          B          A          E

         y|             =====>

          |1              .

     0    |               .

C ----------o               .

         z|               .