Сжатие и индексация дерева

Ключевые слова и синонимы

XML-сжатие и индексация

Постановка задачи

Деревья – одна из базовых структур любых вычислений. Они используются практически в любых аспектах моделирования и представления таких вычислительных процессов, как поиск ключей, ведение каталогов и представление трассировки разбора или выполнения – и это лишь малая часть примеров. Один из новейших способов использования деревьев – XML, формат номер один для хранения и интеграции данных и обмена ими через Интернет (см. http://www.w3.org/XML/). Явное хранение деревьев, под одному указателю на потомка плюс указатели на некоторую дополнительную информацию (например, метки) нередко рассматривается как данность; однако хранение в таком виде может потребовать значительных расходов на память. Чтобы получить представление об их размерах, вспомним, что при простом кодировании дерева необходимо по меньшей мере 16 байт на вершину дерева: один указатель на дополнительную информацию (например, метку вершины) плюс три указателя – на родителя, первого ребенка и следующего брата. Подобные требования к объему памяти могут стать препятствием для обработки даже деревьев среднего размера – например, XML-документов. Далее будут рассмотрены лучшие решения для хранения непомеченных и помеченных деревьев, эффективные по объему занимаемой памяти и поддерживающие быстрые операции навигации и поиска над структурой дерева. В литературе такие решения носят название решений для индексации сокращенных или сжатых деревьев.

Нотация и основные факты

С точки зрения теории информации стоимость хранения любого элемента совокупности U можно вычислить при помощи простого механизма подсчета: для различения любых двух элементов U необходимо не менее |U| бит. Будем считать, что [math]\displaystyle{ \mathcal{T} }[/math] – корневое дерево произвольных формы и размера. (Далее будем считать, что основание всех логарифмов равно 2 и что 0 log 0 = 0).

Рассмотрим три основных класса деревьев:

Ординальные деревья. [math]\displaystyle{ \mathcal{T} }[/math] – непомеченное дерево, его потомки упорядочены слева направо. Количество ординальных деревьев на t вершинах составляет [math]\displaystyle{ C_t = \binom{c2t}{t} / (t + 1) \; }[/math], что порождает нижнюю границу памяти в [math]\displaystyle{ 2t - \Theta (log \; t) }[/math] бит.

Кардинальные k-арные деревья. Дерево [math]\displaystyle{ \mathcal{T} }[/math] помечено: его ребра снабжены символами из алфавита [math]\displaystyle{ \Sigma = \{ 1, ..., k \} \; }[/math]. Любая вершина имеет степень не более k, поскольку ребра, выходящие из одной вершины, имеют различные метки. Типичными примерами кардинальных деревьев являются бинарные деревья (k = 2), несжатые деревья и Patricia-деревья, или сжатые радиксные деревья. Количество k-арных кардинальных деревьев на t вершинах составляет [math]\displaystyle{ C^k_t = \binom{kt + 1}{t} / (kt + 1) \; }[/math], что дает нижнюю границу памяти t(log k + log e) бит, где k – медленно растущая функция от t.

Помеченные деревья и деревья с множественными метками. [math]\displaystyle{ \mathcal{T} }[/math] – ординальное дерево, вершины которого помечены символами из алфавита [math]\displaystyle{ \Sigma \; }[/math]. В случае дерева с множественными метками каждая вершина помечена хотя бы одним символом. Вершины-братья могут иметь одинаковые символы в качестве меток, так что степень каждой вершины не ограничена; подпути с одними и теми же метками могут встречаться в дереве [math]\displaystyle{ \mathcal{T} }[/math] неоднократно и начинаться в каких угодно местах. Теоретико-информационную нижнюю границу объема памяти данного класса деревьев на t вершинах легко вычислить посредством отдельного рассмотрения структуры дерева и памяти для хранения меток. Для помеченных деревьев она составляет [math]\displaystyle{ log \; C_t + t \; log \; | \Sigma | = t (log \; | \Sigma | + 2 ) - \Theta (log \; t) }[/math] бит.

Над деревом [math]\displaystyle{ \mathcal{T} }[/math] должны поддерживаться следующие операции запроса:

Базовые навигационные запросы: предок вершины u, i-й потомок вершины u, степень вершины u. Если дерево [math]\displaystyle{ \mathcal{T} }[/math] является помеченным, эти операции могут быть ограничены получением некоторой метки [math]\displaystyle{ c \in \Sigma \; }[/math].

Усложненные навигационные запросы: потомок вершины u j-го уровня, глубина вершины u, размер поддерева u, самый низкий общий предок пары вершин, i-я вершина согласно некоторому упорядочению вершин над деревом [math]\displaystyle{ \mathcal{T} }[/math]. Если [math]\displaystyle{ \mathcal{T} }[/math] является помеченным, эти операции могут быть ограничены получением некоторой метки [math]\displaystyle{ c \in \Sigma \; }[/math]. Примеры других операций см. в [2, 11].

Запросы о подпути: пусть дан помеченный подпуть [math]\displaystyle{ \Pi \; }[/math], запрос ищет количество occ вершин дерева [math]\displaystyle{ \mathcal{T} }[/math], являющихся непосредственными потомками [math]\displaystyle{ \Pi \; }[/math]. Каждое вхождение подпути может встречаться в дереве где угодно (т.е. он необязательно должен начинаться от корня).

Элементарное решение задачи индексации дерева заключается в кодировании дерева [math]\displaystyle{ \mathcal{T} }[/math] при помощи указателей и массивов, на которое требуется в сумме O(t log t) бит. Такое кодирование поддерживает ответ на базовые навигационные запросы за константное время, однако не является эффективным по объему памяти и требует полного обхода дерева для выполнения запроса о подпути или усложненных навигационных запросов. Задача заключается в разработке схем хранения деревьев, являющихся либо сжатыми, точнее говоря, «близкими к теоретико-информационной нижней границе», упоминавшейся выше, либо сжатыми в том смысле, что они обеспечивают хранение, «ограниченное рамками энтропии». Кроме того, такие схемы не должны требовать полного обхода дерева при выполнении большинства навигационных операций. Таким образом, решения для индексации сокращенного или сжатого дерева отличаются от простого сжатия входного дерева и последующей его декомпрессии в момент выполнения запроса.

Далее будет предполагаться, что t > \S\, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти (RAM) с размером слова @(lg t). В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время.

Основные результаты

Понятие сокращенных структур данных было введено Джейкобсоном в его важнейшей работе [10]. Он предложил схему хранения ординальных деревьев при помощи 2t + o(t) бит, поддерживающую базовые навигационные запросы за время O(log log t) (т.е. запросы о нахождении предка, первого потомка и следующего брата данной вершины). Позднее Манро и Раман [13] закрыли тему ординальных деревьев, предложив алгоритм выполнения базовых навигационных запросов и запроса о размере поддерева за константное время, требующий 2t + o(t) бит на хранение дерева. Эта схема хранения носит название сбалансированной скобочной записи дерева (Balanced Parenthesis, BP)2. Впоследствии Бенуа и др. [3] предложили схему хранения под названием «последовательность унарной степени с обходом в ширину» (Depth-First Unary Degree Sequence, DFUDS), также использующую 2t + o(t) бит памяти, но выполняющую за константное время большее количество запросов – таких как поиск i-го потомка, ранга потомка и степени вершины. Гири и др. [8] предложили еще одно представление, также требующее оптимального объема памяти и расширяющее список операций DFUDS запросом уровня предка.

Хотя все эти три представления обеспечивают оптимальное использование памяти, ни одно из них не поддерживает выполнение всех имеющихся операций за константное время: так, BP не поддерживает поиск i-го потомка и ранга потомка, а DFUDS и представление Гири не поддерживают поиск самого низкого общего предка. Недавно Дженссон и др. [11] расширили схему DFUDS по двум направлениям: (1) они показали, как реализовать все вышеупомянутые навигационные запросы за константное время 3, и (2) показали, как сжать новую схему хранения дерева до H*(T), что обозначает энтропию распределения степеней вершин дерева [math]\displaystyle{ \mathcal{T} }[/math].

Теорема 1 (Дженссон и др. [2007]. Для любого корневого дерева [math]\displaystyle{ \mathcal{T} }[/math] с t вершинами существует схема индексации, использующая tH*(T) + O(t(loglog t)2/log t) бит памяти и выполняющая все навигационные запросы за константное время.

Этот подход заметно лучше стандартного представления при помощи указателей, поскольку он требует не более H*(T) бит на одну вершину и не снижает эффективности усложненных навигационных запросов. В силу соотношения H*(T) < 2 это решение ни в каком случае не уступает BP и DFUDS, а его преимущества могут быть значительными. Этот результат может быть расширен для получения последовательности DFUDS с энтропией k-го порядка за счет применения любой схемы хранения строк со сжатием (см, например, [7] и ссылки в этой работе).

Бенуа и др. [3] расширили использование алгоритма DFUDS на кардинальные деревья и предложили схему индексации с объемом памяти, близким к теоретико-информационной нижней границе, выполняющую различные навигационные запросы за константное время. Раман и др. [15] улучшили показатели использования памяти при помощи альтернативного подхода, основанного на хранении дерева в виде множества ребер, доказав теорему:

Теорема 2 (Раман и др. [2002]). Для любого k-арного кардинального дерева [math]\displaystyle{ \mathcal{T} }[/math] с t вершинами существует схема индексации, использующая log Ctk + o(t) + O(loglog k) бит памяти и выполняющая за константное время следующие операции: поиск предка, степени, ординальной позиции среди братьев, потомка с меткой c и i-го потомка заданной вершины.

Это представление не поддерживает эффективного выполнения операции поиска размера поддерева; в случае, если она оказывается наиболее важной, обратитесь к работе [3].

Однако, несмотря на высокую активность исследователей, фундаментальная проблема сокращенной индексации помеченных деревьев большей частью остается нерешенной. Фактически вышеупомянутое сокращенное кодирование упорядоченных деревьев можно повторить \S\ раз (по одному разу на каждый возможный символ алфавита £), а затем применить алгоритм «разделяй и властвуй» [8] для снижения объема занимаемой памяти. Однако окончательная граница объема памяти составит 2t + tlog 1-Е1! + O(f|i;|(logloglog t)/(loglog t)) бит, что по-прежнему далеко от теоретико-информационной границы даже для относительно небольших значений S. С другой стороны, если наивысший приоритет имеют запросы о подпути (например, в XML), можно использовать подход из работы [12] – вариант структуры данных суффиксного дерева, должным образом адаптированной для индексации всех помеченных путей дерева [math]\displaystyle{ \mathcal{T} }[/math]. Запросы о подпутях могут быть выполнены за время O(\П\ log \E\ + occ), однако памяти требуется по-прежнему O(t log t) бит (большие скрытые константы появляются в силу использования суффиксных деревьев). Недавно в нескольких работах [1, 2, 5] эта задача была рассмотрена во всей своей совокупности при помощи одновременной обработки запросов о подпути и базовых навигационных запросов [5] либо при помощи рассмотрения деревьев с множественными метками и более широкого множества навигационных операций [1, 2].

2 В некоторых статьях [Цзян и др., ACM-SIAM SODA '01; Садакане, ISAAC '01; Манро и др., J.ALG '01; Манро и Рао, IC ALP '04] алгоритм BP был дополнен поддержкой за константное время других усложненных навигационных запросов – таких как поиск самого низкого общего предка, нахождение степени вершины, ранжирование или выбор листьев и количество листьев в поддереве, поиск потомка или предка нужного уровня.

3 Представление BP и представление Гири и др. [8] недавно были дополнены поддержкой большего количества операций – таких как поиск глубины или высоты вершины, следующей вершины того же уровня, ранжирование или выбор согласно другим способам упорядочения вершин; все они выполняются за константное время, а полное представление требует 2t + o(t) бит памяти (см. [9] и ссылки в данной работе).

Схема индексации дерева из работы [5] основана на преобразовании помеченного дерева [math]\displaystyle{ \mathcal{T} }[/math], которое обозначается как xbw[T] и линеаризует дерево в два массива координат hSlast ; Sa}: первый из них хранит структуру дерева, а второй – перестановку меток [math]\displaystyle{ \mathcal{T} }[/math]. xbw[T] имеет оптимальный (с точностью до членов более низкого порядка) размер 2t + tlog j17j бит и может быть построен и инвертирован за оптимальное линейное время. При разработке алгоритма XBW-Transform авторы вдохновлялись элегантным преобразованием Барроуза-Уилера для строк [4]. Мощь преобразования xbw[T] определяется тем фактом, что оно позволяет преобразовать задачи сжатия и индексации на помеченных деревьях в более простые задачи на строках. Следующие два примитива поиска по строке являются основными инструментами для индексации xbw[T]: rankc(S, i) возвращает количество вхождений символа c в префиксе строки S[1, i], а selectc(S, j) возвращает позицию j-го вхождения символа c в строке S. В литературе встречается множество эффективных по времени и объему памяти реализаций данных примитивов, которые могут трактоваться как черные ящики в задаче сжатой индексации xbw[T] (см., например, [2, 14] и ссылки в этих работах).

Теорема 3 ([Ферраджина и др. 2005]). Рассмотрим дерево [math]\displaystyle{ \mathcal{T} }[/math], состоящее из t вершин, помеченных символами алфавита S. Существует схема индексации сжатого дерева, обеспечивающая следующие показатели эффективности:

• Если \S\ = O(polylog(t)), индексация требует не более tHo(Sa) + 2t + o(t) бит, схема поддерживает выполнение базовых навигационных запросов за константное время, а (численных) запросов о подпутях – за время О(\П\).

• Для любого алфавита S индексация требует не менее tHk (Sa) + 2t + o(floglX'l)) бит, однако выполнение базовых навигационных запросов с метками и (численных) запросов о подпутях замедляется на коэффициент o((loglog\E\)3).

Здесь Hk(s) – эмпирическая энтропия k-го порядка для строки s, Hk(s) < Hk_i(s) для любого k > 0. Поскольку Hk(Sa) < Ho(Sa) < log \E\, индексация xbw[T] занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву [math]\displaystyle{ \mathcal{T} }[/math]. Это представление относится к классу представлений помеченного дерева [math]\displaystyle{ \mathcal{T} }[/math], не имеющих указателей и поддерживающих дополнительные функции поиска (подробнее см. в [5]).

Если более всего интересуют усложненные навигационные запросы над помеченными деревьями, а запросов о путях не предполагается, в этом случае больше всего подойдет подход Барбая и др. [1, 2]. Авторы предложили новое понятие сокращенного индекса, отличное от понятия сокращенного или сжатого кодирования, применяющегося во всех вышеприведенных решениях. Сокращенный индекс не затрагивает индексируемые данные; он обращается к ним только при помощи базовых операций, обеспечиваемых лежащим в его основе абстрактным типом данных (ADT), и требует асимптотически меньшего объема памяти в сравнении с теоретико-информационной нижней границей объема памяти для хранения самих данных. Авторы сводят задачу индексации помеченных деревьев к задаче индексации ординальных деревьев и строк, а задачу индексации деревьев с множественными метками – к задаче индексации ординальных деревьев и бинарных отношений. Затем они строят сокращенные индексы для строк и бинарных отношений. Для представления их результата нам потребуются следующие определения. Пусть m – общее количество символов в [math]\displaystyle{ \mathcal{T} }[/math], tc – количество вершин, помеченных символом c в [math]\displaystyle{ \mathcal{T} }[/math], а pc – максимальное количество меток c на любом корневом пути [math]\displaystyle{ \mathcal{T} }[/math] (называемое рекурсивностью c). Определим p как среднюю рекурсивность [math]\displaystyle{ \mathcal{T} }[/math], а именно

Теорема 4 ([Барбай и др. 2007]). Рассмотрим дерево [math]\displaystyle{ \mathcal{T} }[/math], состоящее из t вершин с (возможно, множественными) метками с максимально возможным числом символов из алфавита S. Пусть m – общее количество символов в [math]\displaystyle{ \mathcal{T} }[/math]. Предположим, что лежащий в его основе абстрактный тип данных обеспечивает выполнение базовых навигационных запросов за константное время и извлекает i-ю метку вершины за время f. Существует сокращенный индекс [math]\displaystyle{ \mathcal{T} }[/math], использующий m(logp + o(log(|I7|p))) бит и поддерживающий для данной вершины u следующие операции (где L = log log j E j log log log \£\):

• Каждый c-наследник или c-потомок u может быть получен за время O(L (f + log log j E j )).

• Множество A c-предков u может быть получено за время 0(L(/+loglog|i;|)+|A|(loglogpc+logloglog|i;|(/+loglog|i;|))).

Применение

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

Первый пример касается суффиксных деревьев – важнейшего блока алгоритмов для многих приложений для обработки строк, от биоинформатики до добычи данных и сжатия данных до поисковых машин. Стандартные реализации суффиксных деревьев требуют не менее 80 бит памяти на одну вершину. Сжатое суффиксное дерево для строки S[1, s] состоит из трех компонентов: топологии дерева, значений глубины строк, хранящихся во внутренних вершинах суффиксного дерева, и суффиксных указателей, хранящихся в листьях суффиксного дерева (также называемых суффиксным массивом S). Сокращенное представление дерева, предложенное в [11], может использоваться для кодирования топологии суффиксного дерева и глубины строк, что требует 4s + o(s) бит (предполагая без потери общности, что \S\ = 2). Суффиксный массив может быть сжат вплоть до энтропии k-го порядка S при помощи любого решения из перечисленных в работе [14]. Общий результат никогда не превышает 80 бит на вершину, а для строк с высоким уровнем сжимаемости может оказаться значительно ниже.

Второй пример относится к формату XML, который нередко моделируется при помощи помеченного дерева. Сжатые и сокращенные индексы, описанные в работах [1, 2, 5], разработаны с теоретической точки зрения, однако оказываются вполне релевантными для практических систем обработки XML-файлов. К примеру, в [6] были опубликованы первые обнадеживающие экспериментальные результаты, подчеркивающие эффективность преобразования XBW-Transform на реальных базах данных XML. Авторы показали, что качественная адаптация алгоритма XBW-Transform позволяет сжимать данные в формате XML до самых современных XML-совместимых компрессоров, обеспечивая доступ к контенту, навигацию вверх и вниз по структуре XML-дерева и поиск простых выражений и подстрок в виде путей за несколько миллисекунд на данных в формате MB или XML, для каждой операции выполняя декомпрессию только небольшого фрагмента данных. Предыдущим решениям требовалось несколько секунд на операцию!

Открытые вопросы

Полный список открытых вопросов и направлений будущих исследований слишком велик для данного обзора; подробно эти темы рассматриваются в литературе из прилагаемого списка. Упомянем два основных вопроса, естественным образом вытекающих из вышеизложенных соображений.

Учитывая потенциал XML-приложений, можно попробовать расширить операцию поиска подпутей для эффективного поиска всех листьев дерева [math]\displaystyle{ \mathcal{T} }[/math], метки которых содержат подстроку f$ и которые происходят от заданного подпути П. Под термином «эффективный» здесь понимается поиск, пропорциональный по времени \П\ и количеству полученных вхождений, но насколько возможно независимый от размера дерева [math]\displaystyle{ \mathcal{T} }[/math] в наихудшем случае. В настоящее время такая операция поиска применима только для листьев, являющихся непосредственными потомками П, и даже при таком ограничении решение, предложенное в [6], не является оптимальным.

Существуют два возможных преставления деревьев, дающих вышеописанные результаты: представление в виде ординального дерева (BP, DFUDS или представление Гири и др. [8]) и XBW. Первое служит основой решений для усложненных навигационных операций, а второе – основой для сложных операций поиска подпутей. Возможно ли вывести одно уникальное преобразование для помеченного дерева [math]\displaystyle{ \mathcal{T} }[/math], сочетающее преимущества обоих подходов и все еще допускающее сжатие?

Экспериментальные результаты

Многочисленные примеры баз данных XML можно найти по адресу http://cs.fit.edu/~mmahoney/compression/text.html и в статье [6].

Наборы данных

См. http://cs.fit.edu/~mmahoney/compression/text.html и ссылки в статье [6].

Ссылка на код

Статья [6] включает список программных инструментов для сжатия и индексации данных в формате XML.

См. также

• Индексация сжатого текста
• Операции ранжирования и выбора на двоичных строках
• Сокращенное кодирование перестановок: применение к индексации текста
• Сжатие таблиц
• Индексация текста

Литература

1. Barbay, J., Golynski, A., Munro, J.I., Rao, S.S.: Adaptive searching in succinctly encoded binary relations and tree-structured documents. In: Proc. 17th Combinatorial Pattern Matching (CPM). LNCS n. 4009 Springer, Barcelona (2006), pp. 24-35

2. Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, USA, (2007), pp. 680-689

3. Benoit, D., Demaine, E., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43, 275-292 (2005)

4. Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Tech. Report 124, Digital Equipment Corporation (1994)

5. Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 184-193. Cambridge, USA (2005)

6. Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and searching XML data via two zips. In: Proc. 15th World Wide Web Conference (WWW), pp. 751-760. Edingburg, UK(2006)

7. Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci. 372, (1):115-121 (2007)

8. Geary, R., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. In: Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1-10. New Orleans, USA (2004)

9. He, M., Munro, J.I., Rao, S.S.: Succinct ordinal trees based on tree covering. In: Proc. 34th International Colloquium on Algorithms, Language and Programming (ICALP). LNCS n. 4596, pp. 509-520. Springer, Wroclaw, Poland (2007)

10. Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 549-554. Triangle Park, USA (1989)

11. Jansson, J., Sadakane, K., Sung, W.: Ultra-succinct representation of ordered trees. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 575-584. New Orleans, USA(2007)

12. Kosaraju, S.R.: Efficient tree pattern matching. In: Proc. 20th IEEE Foundations of Computer Science (FOCS), pp. 178-183. Triangle Park, USA (1989)

13. Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762-776 (2001)

14. Navarro, G., Makinen, V.: Compressed full text indexes. ACM Comput. Surv. 39(1) (2007)

15. Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242. San Francisco, USA (2002)