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

== Постановка задачи ==

Деревья – одна из базовых структур любых вычислений. Они используются практически в любых аспектах моделирования и представления таких вычислительных процессов, как поиск ключей, ведение каталогов и представление трассировки разбора или выполнения – и это лишь малая часть примеров. Один из новейших способов использования деревьев – XML, формат номер один для хранения и интеграции данных и обмена ими через Интернет (см. http://www.w3.org/XML/). Явное хранение деревьев, по одному указателю на потомка плюс указатели на некоторую дополнительную информацию (такую как метки) нередко рассматривается как данность; однако хранение в таком виде может требовать значительных расходов на память. Чтобы получить представление об их размерах, вспомним, что при простом кодировании дерева необходимо по меньшей мере 16 байт на вершину дерева: один указатель на дополнительную информацию (например, метку вершины) плюс три указателя на вершины – родителя, первого ребенка и следующего брата. Подобные требования к объему памяти могут стать препятствием для обработки даже деревьев среднего размера – например, XML-документов. Далее будут рассмотрены лучшие решения для хранения непомеченных и помеченных деревьев, эффективные по объему занимаемой памяти и поддерживающие быстрые операции навигации и поиска над структурой дерева. В литературе такие решения носят название решений для индексации сокращенных или сжатых деревьев.

== Нотация и основные факты ==

Далее будет предполагаться, что <math>t \ge | \Sigma | \;</math>, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти ([[RAM]]) с размером слова <math>\Theta (lg \; t)</math>. В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время.

== Основные результаты ==

• Множество A c-предков u может быть получено за время <math>O(L(f + log\; log \; | \Sigma |) + |A|(log \; log \; \rho_c + log \; log \; log \; | \Sigma | \; (f + log \; log \; | \Sigma |)))</math>.

== Применение ==

Второй пример относится к формату XML, который нередко моделируется при помощи помеченного дерева. Сжатые и сокращенные индексы, описанные в работах [1, 2, 5], разработаны с теоретической точки зрения, однако оказываются вполне релевантными для практических систем обработки XML-файлов. К примеру, в [6] были опубликованы первые обнадеживающие экспериментальные результаты, подчеркивающие эффективность преобразования XBW-Transform на реальных базах данных XML. Авторы показали, что качественная адаптация алгоритма XBW-Transform позволяет сжимать данные в формате XML до самых современных XML-совместимых компрессоров, обеспечивая доступ к контенту, навигацию вверх и вниз по структуре XML-дерева и поиск простых выражений и подстрок в виде путей за несколько миллисекунд на мегабайтах данных в формате XML, для каждой операции выполняя декомпрессию только небольшого фрагмента данных. Предыдущим решениям требовалось несколько секунд на операцию!

== Открытые вопросы ==