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

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

Понятие сокращенных структур данных было введено Джейкобсоном в его важнейшей работе [10]. Он предложил схему хранения ординальных деревьев при помощи 2t + o(t) бит, поддерживающую базовые навигационные запросы за время O(log log t) (т.е. запросы о нахождении предка, первого потомка и следующего брата данной вершины). Позднее Манро и Раман [13] закрыли тему ординальных деревьев, предложив алгоритм выполнения базовых навигационных запросов и запроса о размере поддерева за константное время, требующий 2t + o(t) бит на хранение дерева. Эта схема хранения носит название сбалансированной скобочной записи дерева (Balanced Parenthesis, BP). (В некоторых статьях [Цзян и др., ACM-SIAM SODA '01; Садакане, ISAAC '01; Манро и др., J.ALG '01; Манро и Рао, IC ALP '04] алгоритм BP был дополнен поддержкой за константное время других усложненных навигационных запросов – таких как поиск самого низкого общего предка, нахождение степени вершины, ранжирование или выбор листьев и количество листьев в поддереве, поиск потомка или предка нужного уровня).

Хотя все эти три представления обеспечивают оптимальное использование памяти, ни одно из них не поддерживает выполнение всех имеющихся операций за константное время: так, BP не поддерживает поиск i-го потомка и ранга потомка, а DFUDS и представление Гири не поддерживают поиск самого низкого общего предка. Недавно Дженссон и др. [11] расширили схему DFUDS по двум направлениям: (1) они показали, как реализовать все вышеупомянутые навигационные запросы за константное время, и (2) показали, как сжать новую схему хранения дерева до H*(T), что обозначает энтропию распределения степеней вершин дерева <math>\mathcal{T}</math>.

(Представление BP и представление Гири и др. [8] недавно были дополнены поддержкой большего количества операций – таких как поиск глубины или высоты вершины, следующей вершины того же уровня, ранжирование или выбор согласно другим способам упорядочения вершин; все они выполняются за константное время, а полное представление требует 2t + o(t) бит памяти - см. [9] и ссылки в данной работе).