Индексирование сжатого текста: различия между версиями

Экономичное по объему памяти индексирование текста; полнотекстовое индексирование сжатого текста; само-индексирование

Пусть дана ''текстовая строка'' <math>T = t_1 t_2... t_n</math> над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''индексирования сжатого текста'' (compressed text indexing, CTI) заключается в ''замене'' строки T экономичной с точки зрения используемой памяти структурой данных, способной эффективно отвечать на основные запросы по сравнению строк и подстрок над T. Примеры типичных запросов, требующих ответов с использованием подобного индекса:

Исходный FM-индекс налагает серьезные ограничения на размер алфавита. В последующих работах эти ограничения были устранены. С концептуальной точки зрения самый простой способ добиться более дружественного к алфавитам экземпляра FM-индекса заключается в построении ''дерева вейвлетов'' [5] на <math>T^{bwt}</math>. Это бинарное дерево над алфавитом <math>\Sigma</math>, устроенное таким образом, что каждый узел v обрабатывает подмножество алфавита S(v), которое делит между своими детьми. Корень обрабатывает <math>\Sigma</math>, а каждый лист обрабатывает один символ. Каждый узел v кодирует такие позиции i таким образом, что <math>T^{bwt}[i] \in S(v)</math>. Для этих позиций в узле v хранится только битовый вектор, указывающий, какая из них направляется налево, а какая – направо. Битовые векторы узла предварительно обрабатываются для выполнения запросов <math>rank_1()</math> за константное время, используя o(n)-битные структуры данных [6, 12]. Гросси и др. [4] показали, что дерево вейвлетов, построенное с использованием кодировки [12], занимает <math>nH_0 + o(n \; log \; \sigma)</math> бит. После этого легко смоделировать один запрос <math>rank_c()</math> при помощи <math>log_2 \; \sigma</math> запросов <math>rank_1()</math>. С теми же затратами можно получить <math>T^{bwt}[i]</math>. Более поздние усовершенствования улучшили требования по времени, позволив получить, например, следующий результат:

'''Теорема 4 ([Ферраджина и др. [4]). Задача CTI может быть решена с помощью так называемого дружественного к алфавитам FM-индекса (Alphabet-Friendly FM-Index, AF-FMI) размером <math>nH_k + o(n \; log \; \sigma)</math> бит, имеющего ту же временную сложностьи те же ограничения, что и SSA, при <math>k \le \alpha \; log_{\sigma}\; n</math> для любого константного <math>0 < \alpha < 1</math>.'''

Недавно проведенный анализ [8] показал, что требования к памяти простого алгоритма SSA ограничены тем же количеством бит <math>nH_k + o(n \; log \; \sigma)</math>, что теоретически делает подход на базе форсирования для достижения того же результата излишним. На практике реализации в работах [4, 7] намного превосходят реализации, построенные непосредственно на этой упрощенной идее.

Сайт Pizza-Chili (http://pizzachili.dcc.uchile.cl или http://pizzachili.di.unipi.it) содержит подборку стандартизированных реализаций библиотек, а также наборы данных и рещультаты экспериментальных сравнений.