4511
правок
Сжатие и индексация дерева: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
== Основные результаты == | == Основные результаты == | ||
Понятие сокращенных структур данных было введено Джейкобсоном в его важнейшей работе [10]. Он предложил схему хранения ординальных деревьев при помощи 2t + o(t) бит, поддерживающую базовые навигационные запросы за время O(log log t) (т.е. запросы о нахождении предка, первого потомка и следующего брата данной вершины). Позднее Манро и Раман [13] закрыли тему ординальных деревьев, предложив алгоритм выполнения базовых навигационных запросов и запроса о размере поддерева за константное время, требующий 2t + o(t) бит на хранение дерева. Эта схема хранения носит название сбалансированной скобочной записи дерева (Balanced Parenthesis, BP) | Понятие сокращенных структур данных было введено Джейкобсоном в его важнейшей работе [10]. Он предложил схему хранения ординальных деревьев при помощи 2t + o(t) бит, поддерживающую базовые навигационные запросы за время O(log log t) (т.е. запросы о нахождении предка, первого потомка и следующего брата данной вершины). Позднее Манро и Раман [13] закрыли тему ординальных деревьев, предложив алгоритм выполнения базовых навигационных запросов и запроса о размере поддерева за константное время, требующий 2t + o(t) бит на хранение дерева. Эта схема хранения носит название сбалансированной скобочной записи дерева (Balanced Parenthesis, BP). (В некоторых статьях [Цзян и др., ACM-SIAM SODA '01; Садакане, ISAAC '01; Манро и др., J.ALG '01; Манро и Рао, IC ALP '04] алгоритм BP был дополнен поддержкой за константное время других усложненных навигационных запросов – таких как поиск самого низкого общего предка, нахождение степени вершины, ранжирование или выбор листьев и количество листьев в поддереве, поиск потомка или предка нужного уровня). | ||
Впоследствии Бенуа и др. [3] предложили схему хранения под названием «последовательность унарной степени с обходом в ширину» (Depth-First Unary Degree Sequence, DFUDS), также использующую 2t + o(t) бит памяти, но выполняющую за константное время большее количество запросов – таких как поиск i-го потомка, ранга потомка и степени вершины. Гири и др. [8] предложили еще одно представление, также требующее оптимального объема памяти и расширяющее список операций DFUDS запросом уровня предка. | |||
Хотя все эти три представления обеспечивают оптимальное использование памяти, ни одно из них не поддерживает выполнение всех имеющихся операций за константное время: так, BP не поддерживает поиск i-го потомка и ранга потомка, а DFUDS и представление Гири не поддерживают поиск самого низкого общего предка. Недавно Дженссон и др. [11] расширили схему DFUDS по двум направлениям: (1) они показали, как реализовать все вышеупомянутые навигационные запросы за константное время | |||
Хотя все эти три представления обеспечивают оптимальное использование памяти, ни одно из них не поддерживает выполнение всех имеющихся операций за константное время: так, BP не поддерживает поиск i-го потомка и ранга потомка, а DFUDS и представление Гири не поддерживают поиск самого низкого общего предка. Недавно Дженссон и др. [11] расширили схему DFUDS по двум направлениям: (1) они показали, как реализовать все вышеупомянутые навигационные запросы за константное время, и (2) показали, как сжать новую схему хранения дерева до H*(T), что обозначает энтропию распределения степеней вершин дерева <math>\mathcal{T}</math>. | |||
(Представление BP и представление Гири и др. [8] недавно были дополнены поддержкой большего количества операций – таких как поиск глубины или высоты вершины, следующей вершины того же уровня, ранжирование или выбор согласно другим способам упорядочения вершин; все они выполняются за константное время, а полное представление требует 2t + o(t) бит памяти - см. [9] и ссылки в данной работе). | |||
| Строка 63: | Строка 66: | ||
Однако, несмотря на высокую активность исследователей, фундаментальная проблема сокращенной индексации помеченных деревьев большей частью остается нерешенной. Фактически вышеупомянутое сокращенное кодирование упорядоченных деревьев можно повторить \S\ раз (по одному разу на каждый возможный символ алфавита £), а затем применить алгоритм «разделяй и властвуй» [8] для снижения объема занимаемой памяти. Однако окончательная граница объема памяти составит 2t + tlog 1-Е1! + O(f|i;|(logloglog t)/(loglog t)) бит, что по-прежнему далеко от теоретико-информационной границы даже для относительно небольших значений S. С другой стороны, если наивысший приоритет имеют запросы о подпути (например, в XML), можно использовать подход из работы [12] – вариант структуры данных суффиксного дерева, должным образом адаптированной для индексации всех помеченных путей дерева <math>\mathcal{T}</math>. Запросы о подпутях могут быть выполнены за время O(\П\ log \E\ + occ), однако памяти требуется по-прежнему O(t log t) бит (большие скрытые константы появляются в силу использования суффиксных деревьев). Недавно в нескольких работах [1, 2, 5] эта задача была рассмотрена во всей своей совокупности при помощи одновременной обработки запросов о подпути и базовых навигационных запросов [5] либо при помощи рассмотрения деревьев с множественными метками и более широкого множества навигационных операций [1, 2]. | Однако, несмотря на высокую активность исследователей, фундаментальная проблема сокращенной индексации помеченных деревьев большей частью остается нерешенной. Фактически вышеупомянутое сокращенное кодирование упорядоченных деревьев можно повторить \S\ раз (по одному разу на каждый возможный символ алфавита £), а затем применить алгоритм «разделяй и властвуй» [8] для снижения объема занимаемой памяти. Однако окончательная граница объема памяти составит 2t + tlog 1-Е1! + O(f|i;|(logloglog t)/(loglog t)) бит, что по-прежнему далеко от теоретико-информационной границы даже для относительно небольших значений S. С другой стороны, если наивысший приоритет имеют запросы о подпути (например, в XML), можно использовать подход из работы [12] – вариант структуры данных суффиксного дерева, должным образом адаптированной для индексации всех помеченных путей дерева <math>\mathcal{T}</math>. Запросы о подпутях могут быть выполнены за время O(\П\ log \E\ + occ), однако памяти требуется по-прежнему O(t log t) бит (большие скрытые константы появляются в силу использования суффиксных деревьев). Недавно в нескольких работах [1, 2, 5] эта задача была рассмотрена во всей своей совокупности при помощи одновременной обработки запросов о подпути и базовых навигационных запросов [5] либо при помощи рассмотрения деревьев с множественными метками и более широкого множества навигационных операций [1, 2]. | ||
Схема индексации дерева из работы [5] основана на преобразовании помеченного дерева <math>\mathcal{T}</math>, которое обозначается как xbw[T] и линеаризует дерево в два массива координат hSlast ; Sa}: первый из них хранит структуру дерева, а второй – перестановку меток <math>\mathcal{T}</math>. xbw[T] имеет оптимальный (с точностью до членов более низкого порядка) размер 2t + tlog j17j бит и может быть построен и инвертирован за оптимальное линейное время. При разработке алгоритма XBW-Transform авторы вдохновлялись элегантным преобразованием Барроуза-Уилера для строк [4]. Мощь преобразования xbw[T] определяется тем фактом, что оно позволяет преобразовать задачи сжатия и индексации на помеченных деревьях в более простые задачи на строках. Следующие два примитива поиска по строке являются основными инструментами для индексации xbw[T]: rankc(S, i) возвращает количество вхождений символа c в префиксе строки S[1, i], а selectc(S, j) возвращает позицию j-го вхождения символа c в строке S. В литературе встречается множество эффективных по времени и объему памяти реализаций данных примитивов, которые могут трактоваться как черные ящики в задаче сжатой индексации xbw[T] (см., например, [2, 14] и ссылки в этих работах). | Схема индексации дерева из работы [5] основана на преобразовании помеченного дерева <math>\mathcal{T}</math>, которое обозначается как xbw[T] и линеаризует дерево в два массива координат hSlast ; Sa}: первый из них хранит структуру дерева, а второй – перестановку меток <math>\mathcal{T}</math>. xbw[T] имеет оптимальный (с точностью до членов более низкого порядка) размер 2t + tlog j17j бит и может быть построен и инвертирован за оптимальное линейное время. При разработке алгоритма XBW-Transform авторы вдохновлялись элегантным преобразованием Барроуза-Уилера для строк [4]. Мощь преобразования xbw[T] определяется тем фактом, что оно позволяет преобразовать задачи сжатия и индексации на помеченных деревьях в более простые задачи на строках. Следующие два примитива поиска по строке являются основными инструментами для индексации xbw[T]: rankc(S, i) возвращает количество вхождений символа c в префиксе строки S[1, i], а selectc(S, j) возвращает позицию j-го вхождения символа c в строке S. В литературе встречается множество эффективных по времени и объему памяти реализаций данных примитивов, которые могут трактоваться как черные ящики в задаче сжатой индексации xbw[T] (см., например, [2, 14] и ссылки в этих работах). | ||
| Строка 91: | Строка 89: | ||
• Множество A c-предков u может быть получено за время 0(L(/+loglog|i;|)+|A|(loglogpc+logloglog|i;|(/+loglog|i;|))). | • Множество A c-предков u может быть получено за время 0(L(/+loglog|i;|)+|A|(loglogpc+logloglog|i;|(/+loglog|i;|))). | ||
== Применение == | == Применение == | ||