4430
правок
Сжатие и индексация дерева: различия между версиями
Материал из WEGA
м
→Нотация и основные факты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Рассмотрим три основных класса деревьев: | Рассмотрим три основных класса деревьев: | ||
'''Ординальные деревья'''. <math>\mathcal{T}</math> – непомеченное дерево, его потомки ''упорядочены'' слева направо. Количество ординальных деревьев на t вершинах составляет <math>C_t = \binom{c2t}{t} / (t + 1) \;</math>, что порождает нижнюю границу памяти в <math>2t - \Theta (log \; t)</math> бит. | '''Ординальные деревья'''. <math>\mathcal{T}</math> – непомеченное дерево, его потомки ''упорядочены'' слева направо. Количество ординальных деревьев на t вершинах составляет <math>C_t = \binom{c2t}{t} / (t + 1) \;</math>, что порождает нижнюю границу памяти в <math>2t - \Theta (log \; t)</math> бит. | ||
'''Кардинальные k-арные деревья'''. Дерево <math>\mathcal{T}</math> помечено: его ''ребра'' снабжены символами из алфавита <math>\Sigma = \{ 1, ..., k \} \;</math>. Любая вершина имеет степень не более k, поскольку ребра, выходящие из одной вершины, имеют различные метки. Типичными примерами кардинальных деревьев являются [[бинарное дерево|бинарные деревья]] (k = 2), несжатые деревья и Patricia-деревья, или сжатые радиксные деревья. Количество k-арных кардинальных деревьев на t вершинах составляет <math>C^k_t = \binom{kt + 1}{t} / (kt + 1) \;</math>, что дает нижнюю границу памяти t(log k + log e) бит, где k – медленно растущая функция от t. | |||
'''Кардинальные k-арные деревья'''. Дерево <math>\mathcal{T}</math> помечено: его ''ребра'' снабжены символами из алфавита <math>\Sigma = \{ 1, ..., k \} \;</math>. Любая вершина имеет степень не более k, поскольку ребра, выходящие из одной вершины, имеют различные метки. Типичными примерами кардинальных деревьев являются бинарные деревья (k = 2), несжатые деревья и Patricia-деревья, или сжатые радиксные деревья. Количество k-арных кардинальных деревьев на t вершинах составляет <math>C^k_t = \binom{kt + 1}{t} / (kt + 1) \;</math>, что дает нижнюю границу памяти t(log k + log e) бит, где k – медленно растущая функция от t. | |||
'''Помеченные деревья и деревья с множественными метками'''. <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> бит. | '''Помеченные деревья и деревья с множественными метками'''. <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> бит. | ||
| Строка 25: | Строка 22: | ||
'''Базовые навигационные запросы''': предок вершины u, i-й потомок вершины u, степень вершины u. Если дерево <math>\mathcal{T}</math> является помеченным, эти операции могут быть ограничены получением некоторой метки <math>c \in \Sigma \;</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]. | '''Усложненные навигационные запросы''': потомок вершины u j-го уровня, глубина вершины u, размер поддерева u, самый низкий общий предок пары вершин, i-я вершина согласно некоторому упорядочению вершин над деревом <math>\mathcal{T}</math>. Если <math>\mathcal{T}</math> является помеченным, эти операции могут быть ограничены получением некоторой метки <math>c \in \Sigma \;</math>. Примеры других операций см. в [2, 11]. | ||
'''Запросы о подпути''': пусть дан помеченный подпуть <math>\Pi \;</math>; запрос ищет количество ''occ'' вершин дерева <math>\mathcal{T}</math>, являющихся непосредственными потомками <math>\Pi \;</math>. Каждое вхождение подпути может встречаться в дереве где угодно (т.е. он необязательно должен начинаться от корня). | |||
'''Запросы о подпути''': пусть дан помеченный подпуть <math>\Pi \;</math> | |||
Элементарное решение задачи индексации дерева заключается в кодировании дерева <math>\mathcal{T}</math> при помощи указателей и массивов, на которое требуется в сумме <math>\Theta(t \; log \; t)</math> бит. Такое кодирование поддерживает ответ на базовые навигационные запросы за константное время, однако не является эффективным по объему памяти и требует полного обхода дерева для выполнения запроса о подпути или усложненных навигационных запросов. Задача заключается в разработке схем хранения деревьев, являющихся либо | Элементарное решение задачи индексации дерева заключается в кодировании дерева <math>\mathcal{T}</math> при помощи указателей и массивов, на которое требуется в сумме <math>\Theta(t \; log \; t)</math> бит. Такое кодирование поддерживает ответ на базовые навигационные запросы за константное время, однако не является эффективным по объему памяти и требует полного обхода дерева для выполнения запроса о подпути или усложненных навигационных запросов. Задача заключается в разработке схем хранения деревьев, являющихся либо ''сокращенными'', точнее говоря, «близкими к теоретико-информационной нижней границе», упоминавшейся выше, либо ''сжатыми'' в том смысле, что они обеспечивают объем хранения, «ограниченный рамками энтропии». Кроме того, такие схемы не должны требовать полного обхода дерева при выполнении большинства навигационных операций. Таким образом, решения для индексации сокращенного или сжатого дерева отличаются от простого сжатия входного дерева и последующей его декомпрессии в момент выполнения запроса. | ||
Далее будет предполагаться, что <math>t \ge | \Sigma | \;</math>, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти (RAM) с размером слова <math>\Theta (lg \; t)</math>. В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время. | Далее будет предполагаться, что <math>t \ge | \Sigma | \;</math>, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти ([[RAM]]) с размером слова <math>\Theta (lg \; t)</math>. В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время. | ||
== Основные результаты == | == Основные результаты == | ||
