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

Понятие сокращенных структур данных было введено Джейкобсоном в его важнейшей работе [10]. Он предложил схему хранения ординальных деревьев при помощи 2t + o(t) бит, поддерживающую базовые навигационные запросы за время O(log log t) (т.е. запросы о нахождении предка, первого потомка и следующего брата данной вершины). Позднее Манро и Раман [13] закрыли тему ординальных деревьев, предложив алгоритм выполнения базовых навигационных запросов и запроса о размере поддерева за константное время, требующий 2t + o(t) бит на хранение дерева. Эта схема хранения носит название сбалансированной скобочной записи дерева (Balanced Parenthesis, BP). (''В некоторых статьях [Цзян и др., ACM-SIAM SODA '01; Садакане, ISAAC '01; Манро и др., J.ALG '01; Манро и Рао, IC ALP '04] алгоритм BP был дополнен поддержкой за константное время других усложненных навигационных запросов – таких как поиск самого низкого общего предка, нахождение степени вершины, ранжирование или выбор листьев и количество листьев в поддереве, поиск потомка или предка нужного уровня'').

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

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

Однако, несмотря на высокую активность исследователей, фундаментальная проблема сокращенной индексации помеченных деревьев большей частью остается нерешенной. Фактически вышеупомянутое сокращенное кодирование упорядоченных деревьев можно повторить <math>| \Sigma | \;</math> раз (по одному разу на каждый возможный символ алфавита <math>\Sigma \;</math>), а затем применить алгоритм «разделяй и властвуй» [8] для снижения объема занимаемой памяти. Однако окончательная граница объема памяти составит <math>2t + t \; log \; | \Sigma | + O(t \; | \Sigma | \; (log \; log \; t) / (log \; log \; t))</math> бит, что по-прежнему далеко от теоретико-информационной границы даже для относительно небольшого размера <math>\Sigma \;</math>. С другой стороны, если наивысший приоритет имеют запросы о подпути (например, в XML), можно использовать подход из работы [12] – вариант структуры данных суффиксного дерева, должным образом адаптированной для индексации всех помеченных путей дерева <math>\mathcal{T}</math>. Запросы о подпутях могут быть выполнены за время <math>O(| \Pi | \; log \; | \Sigma | \; + occ)</math>, однако памяти требуется по-прежнему <math>\Theta (t \; log \; t)</math> бит (большие скрытые константы появляются в силу использования суффиксных деревьев). Недавно в нескольких работах [1, 2, 5] эта задача была рассмотрена во всей своей совокупности при помощи одновременной обработки запросов о подпути и базовых навигационных запросов [5] либо при помощи рассмотрения деревьев с множественными метками и более широкого множества навигационных операций [1, 2].

Схема индексации дерева из работы [5] основана на преобразовании помеченного дерева <math>\mathcal{T}</math>, которое обозначается как <math>xbw[\mathcal{T}]</math> и линеаризует дерево в два массива координат <math>\langle S_{last}, S_{\alpha} \rangle</math>: первый из них хранит структуру дерева, а второй – перестановку меток <math>\mathcal{T}</math>. <math>xbw[\mathcal{T}]</math> имеет оптимальный (с точностью до членов более низкого порядка) размер <math>2t + t \; log \; | \Sigma |</math> бит и может быть построен и инвертирован за оптимальное линейное время. При разработке алгоритма XBW-Transform авторы вдохновлялись элегантным преобразованием Барроуза-Уилера для строк [4]. Мощь преобразования <math>xbw[\mathcal{T}]</math> определяется тем фактом, что оно позволяет преобразовать задачи сжатия и индексации на помеченных деревьях в более простые задачи на строках. Следующие два примитива поиска по строке являются основными инструментами для индексации <math>xbw[\mathcal{T}]: rank_c(S, i)</math> возвращает количество вхождений символа c в префиксе строки S[1, i], а <math>select_c(S, j) \;</math> возвращает позицию j-го вхождения символа c в строке S. В литературе встречается множество эффективных по времени и объему памяти реализаций данных примитивов, которые могут трактоваться как черные ящики в задаче сжатой индексации <math>xbw[\mathcal{T}]</math> (см., например, [2, 14] и ссылки в этих работах).

• Для любого алфавита <math>\Sigma \;</math> индексация требует не менее <math>tH_k (S_{\alpha}) + 2t + o(t \; log \; | \Sigma | ))</math> бит, однако выполнение базовых навигационных запросов с метками и (численных) запросов о подпутях замедляется на коэффициент <math>o((log \; log \; | \Sigma | )3)</math>.

Поскольку <math>H_k(S_{\alpha}) \le H_0(S_{\alpha}) \le log \; | \Sigma |</math>, индексация <math>xbw[\mathcal{T}]</math> занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву <math>\mathcal{T}</math>. Это представление относится к классу представлений помеченного дерева <math>\mathcal{T}</math>, не имеющих указателей и поддерживающих дополнительные функции поиска (подробнее см. в [5]).

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

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