4551
правка
Сжатие и индексация дерева: различия между версиями
Материал из WEGA
м
→Нотация и основные факты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
== Нотация и основные факты == | == Нотация и основные факты == | ||
С точки зрения теории информации стоимость хранения любого элемента совокупности U можно вычислить при помощи простого механизма подсчета: для различения любых двух элементов U необходимо не менее |U| | С точки зрения теории информации стоимость хранения любого элемента совокупности U можно вычислить при помощи простого механизма подсчета: для различения любых двух элементов U необходимо не менее |U| бит. Будем считать, что <math>\mathcal{T}</math> – корневое дерево произвольных формы и размера. (Далее будем считать, что основание всех логарифмов равно 2 и что 0 log 0 = 0). | ||
Ординальные деревья. | Рассмотрим три основных класса деревьев: | ||
'''Ординальные деревья'''. <math>\mathcal{T}</math> – непомеченное дерево, его потомки упорядочены слева направо. Количество ординальных деревьев на t вершинах составляет Q = t t /(t + 1), что порождает нижнюю границу памяти в 2f- ©(log t) бит. | |||
| Строка 26: | Строка 29: | ||
Усложненные навигационные запросы: потомок вершины u j-го уровня, глубина вершины u, размер поддерева u, самый низкий общий предок пары вершин, i-я вершина согласно некоторому упорядочению вершин над деревом T. Если T является помеченным, эти операции могут быть ограничены получением некоторой метки c 2 S. Примеры других операций см. в [2, 11]. | Усложненные навигационные запросы: потомок вершины u j-го уровня, глубина вершины u, размер поддерева u, самый низкий общий предок пары вершин, i-я вершина согласно некоторому упорядочению вершин над деревом T. Если T является помеченным, эти операции могут быть ограничены получением некоторой метки c 2 S. Примеры других операций см. в [2, 11]. | ||
Запросы о подпути: пусть дан помеченный подпуть П, запрос ищет количество occ вершин дерева T, являющихся непосредственными потомками П. Каждое вхождение подпути может встречаться в дереве где угодно (т.е. он необязательно должен начинаться от корня). | Запросы о подпути: пусть дан помеченный подпуть П, запрос ищет количество occ вершин дерева T, являющихся непосредственными потомками П. Каждое вхождение подпути может встречаться в дереве где угодно (т.е. он необязательно должен начинаться от корня). | ||
| Строка 36: | Строка 37: | ||
Далее будет предполагаться, что t > \S\, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти (RAM) с размером слова @(lg t). В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время. | Далее будет предполагаться, что t > \S\, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти (RAM) с размером слова @(lg t). В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время. | ||
== Основные результаты == | == Основные результаты == | ||
