4430
правок
Сжатие и индексация дерева: различия между версиями
Материал из WEGA
Сжатие и индексация дерева (посмотреть исходный код)
Версия от 15:15, 22 января 2017
, 22 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 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> бит и может быть | Схема индексации дерева из работы [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] и ссылки в этих работах). | ||
| Строка 68: | Строка 70: | ||
• Если <math>| \Sigma | = O(polylog(t)) \;</math>, индексация требует не более <math>tH_0(S_{\alpha}) + 2t + o(t) \;</math> бит, схема поддерживает выполнение базовых навигационных запросов за константное время, а (численных) запросов о подпутях – за время <math>O( | \Pi | ) \;</math>. | • Если <math>| \Sigma | = O(polylog(t)) \;</math>, индексация требует не более <math>tH_0(S_{\alpha}) + 2t + o(t) \;</math> бит, схема поддерживает выполнение базовых навигационных запросов за константное время, а (численных) запросов о подпутях – за время <math>O( | \Pi | ) \;</math>. | ||
• Для любого алфавита <math>\Sigma \;</math> индексация требует | • Для любого алфавита <math>\Sigma \;</math> индексация требует менее <math>tH_k (S_{\alpha}) + 2t + o(t \; log \; | \Sigma | ))</math> бит, однако выполнение базовых навигационных запросов с метками и (численных) запросов о подпутях замедляется на коэффициент <math>o((log \; log \; | \Sigma | )3)</math>. | ||
Здесь <math>H_k(s) \;</math> – эмпирическая энтропия k-го порядка для строки s, <math>H_k(s) \le H_{k - 1}(s)</math> для любого k > 0. | Здесь <math>H_k(s) \;</math> – эмпирическая энтропия k-го порядка для строки s, <math>H_k(s) \le H_{k - 1}(s)</math> для любого k > 0. | ||
Поскольку <math>H_k(S_{\alpha}) \le H_0(S_{\alpha}) \le log \; | \Sigma |</math>, индексация <math>xbw[\mathcal{T}]</math> занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву <math>\mathcal{T}</math>. Это представление относится к классу представлений помеченного дерева <math>\mathcal{T}</math>, не имеющих указателей и поддерживающих дополнительные функции поиска (подробнее см. в [5]). | |||
Поскольку <math>H_k(S_{\alpha}) \le H_0(S_{\alpha}) \le log \; | \Sigma |</math>, индексация <math>xbw[\mathcal{T}]</math> занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву <math>\mathcal{T}</math>. Это представление относится к классу представлений помеченного дерева <math>\mathcal{T}</math>, ''не имеющих указателей'' и поддерживающих дополнительные функции поиска (подробнее см. в [5]). | |||
| Строка 88: | Строка 91: | ||
Первый пример касается суффиксных деревьев – важнейшего блока алгоритмов для многих приложений для обработки строк, от биоинформатики до добычи данных и сжатия данных до поисковых машин. Стандартные реализации суффиксных деревьев требуют не менее 80 бит памяти на одну вершину. Сжатое суффиксное дерево для строки S[1, s] состоит из трех компонентов: топологии дерева, значений глубины строк, хранящихся во внутренних вершинах суффиксного дерева, и суффиксных указателей, хранящихся в листьях суффиксного дерева (также называемых суффиксным массивом S). Сокращенное представление дерева, предложенное в [11], может использоваться для кодирования топологии суффиксного дерева и глубины строк, что требует 4s + o(s) бит (предполагая без потери общности, что <math>| \Sigma | = 2 \;</math>). Суффиксный массив может быть сжат вплоть до энтропии k-го порядка S при помощи любого решения из перечисленных в работе [14]. Общий результат никогда не превышает 80 бит на вершину, а для строк с высоким уровнем сжимаемости может оказаться значительно ниже. | Первый пример касается суффиксных деревьев – важнейшего блока алгоритмов для многих приложений для обработки строк, от биоинформатики до добычи данных и сжатия данных до поисковых машин. Стандартные реализации суффиксных деревьев требуют не менее 80 бит памяти на одну вершину. Сжатое суффиксное дерево для строки S[1, s] состоит из трех компонентов: топологии дерева, значений глубины строк, хранящихся во внутренних вершинах суффиксного дерева, и суффиксных указателей, хранящихся в листьях суффиксного дерева (также называемых [[суффиксный массив|суффиксным массивом]] S). Сокращенное представление дерева, предложенное в [11], может использоваться для кодирования топологии суффиксного дерева и значений глубины строк, что требует 4s + o(s) бит (предполагая без потери общности, что <math>| \Sigma | = 2 \;</math>). Суффиксный массив может быть сжат вплоть до энтропии k-го порядка строки S при помощи любого решения из перечисленных в работе [14]. Общий результат никогда не превышает 80 бит на вершину, а для строк с высоким уровнем сжимаемости может оказаться значительно ниже. | ||
Второй пример относится к формату XML, который нередко моделируется при помощи помеченного дерева. Сжатые и сокращенные индексы, описанные в работах [1, 2, 5], разработаны с теоретической точки зрения, однако оказываются вполне релевантными для практических систем обработки XML-файлов. К примеру, в [6] были опубликованы первые обнадеживающие экспериментальные результаты, подчеркивающие эффективность преобразования XBW-Transform на реальных базах данных XML. Авторы показали, что качественная адаптация алгоритма XBW-Transform позволяет сжимать данные в формате XML до самых современных XML-совместимых компрессоров, обеспечивая доступ к контенту, навигацию вверх и вниз по структуре XML-дерева и поиск простых выражений и подстрок в виде путей за несколько миллисекунд на мегабайтах данных в формате XML, для каждой операции выполняя декомпрессию только небольшого фрагмента данных. Предыдущим решениям требовалось несколько секунд на операцию! | |||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 100: | Строка 104: | ||
Существуют два возможных | Существуют два возможных представления деревьев, дающих вышеописанные результаты: представление в виде ординального дерева (BP, DFUDS или представление Гири и др. [8]) и XBW. Первое служит основой решений для усложненных навигационных операций, а второе – основой для сложных операций поиска подпутей. Возможно ли вывести одно уникальное преобразование для помеченного дерева <math>\mathcal{T}</math>, сочетающее преимущества обоих подходов и все еще допускающее сжатие? | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
