1294
правки
Сжатие и индексация дерева: различия между версиями
Материал из WEGA
Сжатие и индексация дерева (посмотреть исходный код)
Версия от 04:52, 22 ноября 2024
, 22 ноября 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 5: | Строка 5: | ||
== Постановка задачи == | == Постановка задачи == | ||
Деревья – одна из базовых структур любых вычислений. Они используются практически в любых аспектах моделирования и представления таких вычислительных процессов, как поиск ключей, ведение каталогов и представление трассировки разбора или выполнения – и это лишь малая часть примеров. Один из новейших способов использования деревьев – XML, формат номер один для хранения и интеграции данных и обмена ими через Интернет (см. http://www.w3.org/XML/). Явное хранение деревьев, по одному указателю на потомка плюс указатели на некоторую дополнительную информацию (такую как метки) нередко рассматривается как данность; однако хранение в таком виде может требовать значительных расходов на память. Чтобы получить представление об их размерах, вспомним, что при простом кодировании дерева необходимо по меньшей мере 16 байт на вершину дерева: один указатель на дополнительную информацию (например, метку вершины) плюс три указателя на вершины – родителя, первого ребенка и следующего брата. Подобные требования к объему памяти могут стать препятствием для обработки даже деревьев среднего размера – например, XML-документов. Далее будут рассмотрены лучшие решения для хранения непомеченных и помеченных деревьев, эффективные по объему занимаемой памяти и поддерживающие быстрые операции навигации и поиска над структурой дерева. В литературе такие решения носят название решений для индексации сокращенных или сжатых деревьев. | Деревья – одна из базовых структур любых вычислений. Они используются практически в любых аспектах моделирования и представления таких вычислительных процессов, как поиск ключей, ведение каталогов и представление трассировки разбора или выполнения – и это лишь малая часть примеров. Один из новейших способов использования деревьев – XML, формат номер один для хранения и интеграции данных и обмена ими через Интернет (см. http://www.w3.org/XML/). Явное хранение деревьев, по одному указателю на потомка плюс указатели на некоторую дополнительную информацию (такую как метки) нередко рассматривается как данность; однако хранение в таком виде может требовать значительных расходов на память. Чтобы получить представление об их размерах, вспомним, что при простом кодировании дерева необходимо по меньшей мере 16 байт на вершину дерева: один указатель на дополнительную информацию (например, метку вершины) плюс три указателя на вершины – родителя, первого ребенка и следующего брата. Подобные требования к объему памяти могут стать препятствием для обработки даже деревьев среднего размера – например, XML-документов. Далее будут рассмотрены лучшие решения для хранения непомеченных и помеченных деревьев, эффективные по объему занимаемой памяти и поддерживающие быстрые операции навигации и поиска над структурой дерева. В литературе такие решения носят название решений для индексации сокращенных или сжатых деревьев. | ||
== Нотация и основные факты == | == Нотация и основные факты == | ||
| Строка 32: | Строка 33: | ||
Далее будет предполагаться, что <math>t \ge | \Sigma | \;</math>, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти ([[RAM]]) с размером слова <math>\Theta (lg \; t)</math>. В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время. | Далее будет предполагаться, что <math>t \ge | \Sigma | \;</math>, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти ([[RAM]]) с размером слова <math>\Theta (lg \; t)</math>. В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 61: | Строка 63: | ||
Схема индексации дерева из работы [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] и ссылки в этих работах). | Схема индексации дерева из работы [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] и ссылки в этих работах). | ||
| Строка 93: | Строка 95: | ||
Второй пример относится к формату XML, который нередко моделируется при помощи помеченного дерева. Сжатые и сокращенные индексы, описанные в работах [1, 2, 5], разработаны с теоретической точки зрения, однако оказываются вполне релевантными для практических систем обработки XML-файлов. К примеру, в [6] были опубликованы первые обнадеживающие экспериментальные результаты, подчеркивающие эффективность преобразования XBW-Transform на реальных базах данных XML. Авторы показали, что качественная адаптация алгоритма XBW-Transform позволяет сжимать данные в формате XML до самых современных XML-совместимых компрессоров, обеспечивая доступ к контенту, навигацию вверх и вниз по структуре XML-дерева и поиск простых выражений и подстрок в виде путей за несколько миллисекунд на мегабайтах данных в формате XML, для каждой операции выполняя декомпрессию только небольшого фрагмента данных. Предыдущим решениям требовалось несколько секунд на операцию! | Второй пример относится к формату XML, который нередко моделируется при помощи помеченного дерева. Сжатые и сокращенные индексы, описанные в работах [1, 2, 5], разработаны с теоретической точки зрения, однако оказываются вполне релевантными для практических систем обработки XML-файлов. К примеру, в [6] были опубликованы первые обнадеживающие экспериментальные результаты, подчеркивающие эффективность преобразования XBW-Transform на реальных базах данных XML. Авторы показали, что качественная адаптация алгоритма XBW-Transform позволяет сжимать данные в формате XML до самых современных XML-совместимых компрессоров, обеспечивая доступ к контенту, навигацию вверх и вниз по структуре XML-дерева и поиск простых выражений и подстрок в виде путей за несколько миллисекунд на мегабайтах данных в формате XML, для каждой операции выполняя декомпрессию только небольшого фрагмента данных. Предыдущим решениям требовалось несколько секунд на операцию! | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 153: | Строка 156: | ||
15. Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242. San Francisco, USA (2002) | 15. Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242. San Francisco, USA (2002) | ||
[[Категория: Совместное определение связанных терминов]] | |||
