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

Элементарное решение задачи индексации дерева заключается в кодировании дерева <math>\mathcal{T}</math> при помощи указателей и массивов, на которое требуется в сумме O(t log t) бит. Такое кодирование поддерживает ответ на базовые навигационные запросы за константное время, однако не является эффективным по объему памяти и требует полного обхода дерева для выполнения запроса о подпути или усложненных навигационных запросов. Задача заключается в разработке схем хранения деревьев, являющихся либо сжатыми, точнее говоря, «близкими к теоретико-информационной нижней границе», упоминавшейся выше, либо сжатыми в том смысле, что они обеспечивают хранение, «ограниченное рамками энтропии». Кроме того, такие схемы не должны требовать полного обхода дерева при выполнении большинства навигационных операций. Таким образом, решения для индексации сокращенного или сжатого дерева отличаются от простого сжатия входного дерева и последующей его декомпрессии в момент выполнения запроса.

Далее будет предполагаться, что t > \S\, а в качестве модели вычислений будет рассматриваться машина с произвольным доступом к памяти (RAM) с размером слова @(lg t). В этом случае различные арифметические и побитовые булевы операции на отдельных словах можно выполнять за константное время.