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

С точки зрения теории информации стоимость хранения любого элемента совокупности U можно вычислить при помощи простого механизма подсчета: для различения любых двух элементов U необходимо не менее |U| бит. Будем считать, что <math>\mathcal{T}</math> – корневое дерево произвольных формы и размера. (''Далее будем считать, что основание всех логарифмов равно 2 и что 0 log 0 = 0'').

'''Ординальные деревья'''. <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.

'''Помеченные деревья и деревья с множественными метками'''. <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> бит.