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