Menu:

 
Популярные записи:

Похожие записи:

 

Алгоритм Расширяющихся Деревьев

Douglas W. Jones - Application Of Splay Trees To Data Compression Communication of the ACM. 31, 8 (August 1988), 996-1007.  Алгоритм расширяющегося префикса является одним из самых простых и быстрых адаптивных алгоритмов сжатия данных, основанных на использовании префиксного кода. Используемые в нем структуры данных могут быть также могут быть также применены для арифметического сжатия. Здесь предлагается использование этих алгоритмов для кодирования и схожих процессов. Применение Расширяющихся Деревьев для сжатия данных. Алгоритмы сжатия могут повышать эффективность хранения и передачи данных посредством сокращения количества их избыточности. Алгоритм сжатия берет в качестве входа текст источника и производит соответствующий ему сжатый текст, когда как разворачивающий алгоритм имеет на входе сжатый текст и получает из него на выходе первоначальный текст источника (1). Большинство алгоритмов сжатия рассматривают исходный текст как набор строк, состоящих из букв алфавита исходного текста. Избыточность в представлении строки S есть L(S) - H(S), где L(S) есть длина представления в битах, а H(S) - энтропия - мера содержания информации, также выраженная в битах. Алгоритмов, которые могли бы без потери информации сжать строку к меньшему числу бит, чем составляет ее энтропия, не существует. Если из исходного текста извлекать по одной букве некоторого случайного набора, использующего алфавит А, то энтропия находится по формуле: ---¬ 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 подходов к сжатию, например, кодирование длин тиражей, существуют также и систематические подходы. Коды Хаффмана являются среди них одними из старейших. Адаптированный алгоритм сжатия Хаффмана требует использования схем балансировки дерева, которые можно также применять к структурам данным, необходимым адаптивному алгоритму арифметического сжатия. Применение в обоих этих областях расширяющихся деревьев оправдано значительным сходством в них целей балансировки. Расширяющиеся деревья обычно описывают формы лексикографической упорядоченности деревьев двоичного поиска, но деревья, используемые при сжатии данных могут не иметь постоянной упорядоченности. Устранение упорядоченности приводит к значительному упрощению основных операций расширения. Полученные в итоге алгоритмы предельно быстры и компактны. В случае применения кодов Хаффмана, расширение приводит к локально адаптированному алгоритму сжатия, который замечательно прост и быстр, хотя и не позволяет достигнуть оптимального сжатия. Когда он применяется к арифметическим кодам, то результат сжатия близок к оптимальному и приблизительно оптимален по времени. Коды префиксов. Большинство широко изучаемых алгоритмов сжатия данных основаны на кодах Хаффмана. В коде Хаффмана каждая буква исходного текста представляется в архиве кодом переменной длины. Более частые буквы представляются короткими кодами, менее частые - длинными. Коды, используемые в сжатом тексте должны подчиняться свойствам префикса, а именно: код, использованный в сжатом тексте не может быть префиксом любого другого кода. Коды префикса могут быть найдены посредством дерева, в котором каждый лист соответствует одной букве алфавита источника. Hа рисунке 1 показано дерево кода префикса для алфавита из 4 букв. Код префикса для буквы может быть прочитан при обходе дерева от корня к этой букве, где 0 соответствует выбору левой его ветви, а 1 - правой. Дерево кода Хаффмана есть дерево с выровненным весом, где каждый лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно. Рисунок 1. Дерево представления кода префикса. Обычные коды Хаффмана требуют предварительной информации о частоте встречаемости букв в исходном тексте, что ведет к необходимости его двойного просмотра - один для получения значений частот букв, другой для проведения самого сжатия. В последующем, значения этих частот нужно объединять с самим сжатым текстом, чтобы в дальнейшем сделать возможным его развертывание. Адаптивное сжатие выполняется за один шаг, т.к. код, используемый для каждой буквы исходного текста, основан на частотах всех остальных кроме нее букв алфавита. Основы для эффективной реализации адаптивного кода Хаффмана были заложены Галлагером [3], Кнут опубликовал практическую версию такого алгоритма 5], а Уиттер его развил [10]. Оптимальный адаптированный код Уиттера всегда лежит в пределах одного бита на букву источника по отношению к оптимальному статичному коду Хаффмана, что обычно составляет несколько процентов от H . К тому же, статичные коды Хаффмана всегда лежат в пределах одного бита на букву исходного текста от H (они достигают этот предел только когда для всех букв p(C) = 2). Такие же ограничения могут быть отнесены к источникам Маркова, если статичное или адаптированное дерево Хаффмана используется для каждого состояния источника, выведенного из его исходного текста. Существуют алгоритмы сжатия которые могут преодолевать эти ограничения. Алгоритм Зива-Лемпелла, например, присваивает слова из архива фиксированной длины строкам исходного текста переменной длины [11], а арифметическое сжатие может использовать для кодирования букв источника даже доли бита [12]. Применение расширения к кодам префикса. Расширяющиеся деревья были впервые описаны в 1983 году [8] и более подробно рассмотрены в 1985 [9]. Первоначально они понимались как вид самосбалансиpованных деревьев двоичного поиска, и было также показано, что они позволяют осуществить самую быструю реализацию приоритетных очередей [4]. Если узел расширяющегося дерева доступен, то оно является расширенным. Это значит, что доступный узел становится корнем, все узлы слева от него образуют новое левое поддерево, узлы справа - новое правое поддерево. Расширение достигается при обходе дерева от старого корня к целевому узлу и совершении при этом локальных изменений, поэтому цена расширения пропорциональна длине пройденного пути. Тарьян и Слейтон [9] показали, что расширяющиеся деревья статично оптимальны. Другими словами, если коды доступных узлов взяты согласно статичному распределению вероятности, то скорости доступа к расширяющемуся дереву и статично сбалансированному, оптимизированному этим распределением, будут отличаться друг от друга на постоянный коэффициент, заметный при достаточно длинных сериях доступов. Поскольку дерево Хаффмана представляет собой пример статично сбалансированного дерева, то при использовании расширения для сжатия данных, размер сжатого текста будет лежать в пределах некоторого коэффициента от размера архива, полученного при использовании кода Хаффмана. Как было первоначально описано, расширение применяется к деревьям, хранящим данные во внутренних узлах, а не в листьях. Деревья же кодов префикса несут все свои данные только в листьях. Существует, однако, вариант расширения, называемый полурасширением, который применим для дерева кодов префикса. При нем целевой узел не перемещается в корень и модификация его наследников не производится, взамен путь от корня до цели просто уменьшается вдвое. Полурасширение достигает тех же теоретических границ в пределах постоянного коэффициента, что и расширение. В случае зигзагообразного обхода лексикографического дерева, проведение как расширения, так и полурасширения усложняется, в отличие от прямого маршрута по левому или правому краю дерева к целевому узлу (случаи зигзага рассмотрены в [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енужность поддержки лексикографического порядка значительно упрощает проведение операции полурасширения за счет исключения случая зигзага. Это может быть сделано проверкой узлов на пути от корня к целевому листу и переменой местами правых наследников с их братьями. Назовем это ПОВОРОТОМ дерева. Теперь новый код префикса для целевого листа будет состоять из одних нулей, поскольку он стал самым левым листом. На рисунке 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| . |1 . | . D

Похожие статьи:

 

Сайт управляется системой uCoz