Применение расширяющихся деревьев для сжатия данных
Алгоритмы сжатия могут повышать эффективность хранения и передачи данных посредством сокращения количества их избыточности. Алгоритм сжатия берет в ка- честве входа текст источника и производит соответствующий ему сжатый текст, когда как разворачивающий алгоритм имеет на входе сжатый текст и получает из него на выходе первоначальный текст источника (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| .