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

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

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

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

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