Аноним

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

Материал из WEGA
Строка 67: Строка 67:
   
   
   
   
Схема индексации дерева из работы [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] и ссылки в этих работах).
Схема индексации дерева из работы [5] основана на преобразовании помеченного дерева <math>\mathcal{T}</math>, которое обозначается как <math>xbw[\mathcal{T}]</math> и линеаризует дерево в два массива координат <math>\langle S_{last}, S_{\alpha} \rangle</math>: первый из них хранит структуру дерева, а второй – перестановку меток <math>\mathcal{T}</math>. <math>xbw[\mathcal{T}]</math> имеет оптимальный (с точностью до членов более низкого порядка) размер <math>2t + t \; log \; | \Sigma |</math> бит и может быть построен и инвертирован за оптимальное линейное время. При разработке алгоритма XBW-Transform авторы вдохновлялись элегантным преобразованием Барроуза-Уилера для строк [4]. Мощь преобразования <math>xbw[\mathcal{T}]</math> определяется тем фактом, что оно позволяет преобразовать задачи сжатия и индексации на помеченных деревьях в более простые задачи на строках. Следующие два примитива поиска по строке являются основными инструментами для индексации <math>xbw[\mathcal{T}]: rank_c(S, i)</math> возвращает количество вхождений символа c в префиксе строки S[1, i], а <math>select_c(S, j) \;</math> возвращает позицию j-го вхождения символа c в строке S. В литературе встречается множество эффективных по времени и объему памяти реализаций данных примитивов, которые могут трактоваться как черные ящики в задаче сжатой индексации <math>xbw[\mathcal{T}]</math> (см., например, [2, 14] и ссылки в этих работах).




4551

правка