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

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