Сжатие и индексация дерева: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
'''Ординальные деревья'''. <math>\mathcal{T}</math> – непомеченное дерево, его потомки упорядочены слева направо. Количество ординальных деревьев на t вершинах составляет | '''Ординальные деревья'''. <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> помечено: его ребра снабжены символами из алфавита | '''Кардинальные 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. | ||