Сжатие и индексация дерева: различия между версиями

'''Помеченные деревья и деревья с множественными метками'''. <math>\mathcal{T}</math> – ординальное дерево, вершины которого помечены символами из алфавита <math>\Sigma \;</math>. В случае дерева с множественными метками каждая вершина помечена хотя бы одним символом. Вершины-братья могут иметь одинаковые символы в качестве меток, так что степень каждой вершины не ограничена; подпути с одними и теми же метками могут встречаться в дереве <math>\mathcal{T}</math> неоднократно и начинаться в каких угодно местах. Теоретико-информационную нижнюю границу объема памяти данного класса деревьев на t вершинах легко вычислить посредством отдельного рассмотрения структуры дерева и памяти для хранения меток. Для помеченных деревьев она составляет <math>log \; C_t + t \; log \; | \Sigma | = t (log \; | \Sigma | + 2 ) - \Theta (log \; t)</math> бит.

'''Базовые навигационные запросы''': предок вершины u, i-й потомок вершины u, степень вершины u. Если дерево <math>\mathcal{T}</math> является помеченным, эти операции могут быть ограничены получением некоторой метки <math>c \in \Sigma \;</math>.

'''Усложненные навигационные запросы''': потомок вершины u j-го уровня, глубина вершины u, размер поддерева u, самый низкий общий предок пары вершин, i-я вершина согласно некоторому упорядочению вершин над деревом <math>\mathcal{T}</math>. Если <math>\mathcal{T}</math> является помеченным, эти операции могут быть ограничены получением некоторой метки <math>c \in \Sigma \;</math>. Примеры других операций см. в [2, 11].