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

Однако, несмотря на высокую активность исследователей, фундаментальная проблема сокращенной индексации помеченных деревьев большей частью остается нерешенной. Фактически вышеупомянутое сокращенное кодирование упорядоченных деревьев можно повторить <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].