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

Схема индексации дерева из работы [5] основана на преобразовании помеченного дерева <math>\mathcal{T}</math>, которое обозначается как xbw[T] и линеаризует дерево в два массива координат hSlast ; Sa}: первый из них хранит структуру дерева, а второй – перестановку меток <math>\mathcal{T}</math>. xbw[T] имеет оптимальный (с точностью до членов более низкого порядка) размер 2t + tlog j17j бит и может быть построен и инвертирован за оптимальное линейное время. При разработке алгоритма XBW-Transform авторы вдохновлялись элегантным преобразованием Барроуза-Уилера для строк [4]. Мощь преобразования xbw[T] определяется тем фактом, что оно позволяет преобразовать задачи сжатия и индексации на помеченных деревьях в более простые задачи на строках. Следующие два примитива поиска по строке являются основными инструментами для индексации xbw[T]: rankc(S, i) возвращает количество вхождений символа c в префиксе строки S[1, i], а selectc(S, j) возвращает позицию j-го вхождения символа c в строке S. В литературе встречается множество эффективных по времени и объему памяти реализаций данных примитивов, которые могут трактоваться как черные ящики в задаче сжатой индексации xbw[T] (см., например, [2, 14] и ссылки в этих работах).