4430
правок
Сжатие и индексация дерева: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
== Основные результаты == | == Основные результаты == | ||
Понятие сокращенных структур данных было введено Джейкобсоном в его важнейшей работе [10]. Он предложил схему хранения ординальных деревьев | Понятие сокращенных структур данных было введено Джейкобсоном в его важнейшей работе [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 запросом уровня предка. | Впоследствии Бенуа и др. [3] предложили схему хранения под названием «последовательность унарной степени с обходом в ширину» (Depth-First Unary Degree Sequence, DFUDS), также использующую 2t + o(t) бит памяти, но выполняющую за константное время большее количество запросов – таких как поиск i-го потомка, ранга потомка и степени вершины. Гири и др. [8] предложили еще одно представление, также требующее оптимального объема памяти и расширяющее список операций DFUDS запросом уровня предка. | ||
| Строка 40: | Строка 40: | ||
Хотя все эти три представления обеспечивают оптимальное использование памяти, ни одно из них не поддерживает выполнение всех имеющихся операций за константное время: так, BP не поддерживает поиск i-го потомка и ранга потомка, а DFUDS и представление Гири не поддерживают поиск самого низкого общего предка. Недавно Дженссон и др. [11] расширили схему DFUDS по двум направлениям: (1) они показали, как реализовать все вышеупомянутые навигационные запросы за константное время, и (2) показали, как сжать новую схему хранения дерева до <math>H^* (\mathcal{T}) \;</math>, что обозначает энтропию распределения степеней вершин дерева <math>\mathcal{T}</math>. | Хотя все эти три представления обеспечивают оптимальное использование памяти, ни одно из них не поддерживает выполнение всех имеющихся операций за константное время: так, BP не поддерживает поиск i-го потомка и ранга потомка, а DFUDS и представление Гири не поддерживают поиск самого низкого общего предка. Недавно Дженссон и др. [11] расширили схему DFUDS по двум направлениям: (1) они показали, как реализовать все вышеупомянутые навигационные запросы за константное время, и (2) показали, как сжать новую схему хранения дерева до <math>H^* (\mathcal{T}) \;</math>, что обозначает энтропию распределения степеней вершин дерева <math>\mathcal{T}</math>. | ||
(''Представление BP и представление Гири и др. [8] недавно были дополнены поддержкой большего количества операций – таких как поиск глубины или высоты вершины, следующей вершины того же уровня, ранжирование или выбор согласно | (''Представление BP и представление Гири и др. [8] недавно были дополнены поддержкой большего количества операций – таких как поиск глубины или высоты вершины, следующей вершины того же уровня, ранжирование или выбор согласно различным способам упорядочения вершин; все они выполняются за константное время, а полное представление требует 2t + o(t) бит памяти - см. [9] и ссылки в данной работе''). | ||
| Строка 46: | Строка 46: | ||
Этот подход заметно лучше стандартного представления при помощи указателей, поскольку он требует не более <math>H^* (\mathcal{T})</math> бит на одну вершину и не снижает эффективности усложненных навигационных запросов. В силу соотношения <math>H^* (\mathcal{T}) \le 2</math> | Этот подход заметно лучше стандартного представления при помощи указателей, поскольку он требует не более <math>H^* (\mathcal{T})</math> бит на одну вершину и не снижает эффективности усложненных навигационных запросов. В силу соотношения <math>H^* (\mathcal{T}) \le 2</math> данное решение ни в каком случае не уступает BP и DFUDS, а его преимущества могут быть значительными. Этот результат может быть расширен для получения последовательности DFUDS с энтропией k-го порядка за счет применения любой схемы хранения строк со сжатием (см, например, [7] и ссылки в этой работе). | ||
