Сжатие и индексация дерева: различия между версиями

Кардинальные k-арные деревья. Дерево T помечено: его ребра снабжены символами из алфавита S = f1..: ; kg. Любая вершина имеет степень не более k, поскольку ребра, выходящие из одной вершины, имеют различные метки. Типичными примерами кардинальных деревьев являются бинарные деревья (k = 2), несжатые деревья и Patricia-деревья, или сжатые радиксные деревья. Количество k-арных кардинальных деревьев на t вершинах составляет Ctk = I \l{kt + 1), что дает нижнюю границу памяти t(log k + log e) бит, где k – медленно растущая функция от t.

Помеченные деревья и деревья с множественными метками. T – ординальное дерево, вершины которого помечены символами из алфавита E. В случае дерева с множественными метками каждая вершина помечена хотя бы одним символом. Вершины-братья могут иметь одинаковые символы в качестве меток, так что степень каждой вершины не ограничена; подпути с одними и теми же метками могут встречаться в дереве T неоднократно и начинаться в каких угодно местах. Теоретико-информационную нижнюю границу объема памяти данного класса деревьев на t вершинах легко вычислить посредством отдельного рассмотрения структуры дерева и памяти для хранения меток. Для помеченных деревьев она составляет logCt + tlog |i7| = t (log j £ j + 2) -©(log t) бит.

Над деревом T должны поддерживаться следующие операции запроса:

Базовые навигационные запросы: предок вершины u, i-й потомок вершины u, степень вершины u. Если дерево T является помеченным, эти операции могут быть ограничены получением некоторой метки c 2 S.

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

Запросы о подпути: пусть дан помеченный подпуть П, запрос ищет количество occ вершин дерева T, являющихся непосредственными потомками П. Каждое вхождение подпути может встречаться в дереве где угодно (т.е. он необязательно должен начинаться от корня).

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

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

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

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

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

Схема индексации дерева из работы [5] основана на преобразовании помеченного дерева T, которое обозначается как xbw[T] и линеаризует дерево в два массива координат hSlast ; Sa}: первый из них хранит структуру дерева, а второй – перестановку меток T. 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]). Рассмотрим дерево T, состоящее из t вершин, помеченных символами алфавита S. Существует схема индексации сжатого дерева, обеспечивающая следующие показатели эффективности:

Поскольку Hk(Sa) < Ho(Sa) < log \E\, индексация xbw[T] занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву T. Это представление относится к классу представлений помеченного дерева T, не имеющих указателей и поддерживающих дополнительные функции поиска (подробнее см. в [5]).

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

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

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

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