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

Изящное решение задачи достигается за счет применения комбинации ''преобразования Барроуза-Уилера'' (Burrows-Wheeler Transform, BWT) [1] и структуры данных в виде суффиксного массива [9]. Суффиксный массив SA[1, n] строки T представляет собой перестановку текстовых позиций (1...n), в которой ''суффиксы'' T[i, n] перечислены в лексикографическом порядке. Таким образом, T[SA[i], n] – наименьший i-й суффикс. BWT определяется (1) перестановкой <math>T^{bwt}</math> строки T, определяемой как <math>T^{bwt}[i] = T[SA[i] - 1]</math>, где T[0] = T[n], и (2) числом <math>i^* = SA^{-1}</math>[1].

Ферраджина и Манзини [3] обнаружили способ объединить высокую сжимаемость BWT и индексирующие свойства суффиксного массива. Структура, в сущности, представляет собой сжатое представление BWT плюс некоторые небольшие дополнительные структуры, делающие его пригодным для поиска.

Сначала мы обратимся к извлечению произвольных подстрок из этого сжатого текстового представления, а затем рассмотрим возможности поиска. Для извлечения из структуры всего текста (то есть для поддержки отображения(1, n)) достаточно инвертировать BWT. Для этого рассмотрим таблицу LF[1, n], определенную таким образом, что если выполнить перестановку T[i] в <math>T^{bwt}[j]</math>, а T[i - 1] – в <math>T^{bwt}[j']</math>, то LF[j] = j'. После этого можно сразу же извлечь T ''в обратном порядке'', напечатав <math>T^{bwt}[i^*] \cdot T^{bwt}[LF[i^*]] \cdot T^{bwt}[LF[LF[i^*]]]</math>... (по определению <math>T^{bwt}[i^*]</math> соответствует T[n]).

'''Лемма 1 (Ферраджина и Манзини, 2005 [3])'''. <math>LF[i] = C(c) + rank_c(i)</math>, где <math>c = T^{bwt}[i]</math>, C(c) сообщает, сколько раз в <math>T^{bwt}</math> встречаются символы меньше c, а <math>rank_c(i)</math> – сколько раз символ c встречается в <math>T^{bwt}[1, i]</math>.

Запросы display(i, j) общего вида основываются на  регулярной выборке из текста. Каждая текстовая позиция вида j' • s, где s – частота дискретизации, хранится вместе с <math>SA^{-1} [j \cdot s]</math>, на которую указывает позиция суффиксного массива. Для выполнения запроса display(i, j) мы начинаем с наименьшей выбранной текстовой позиции j' • s > j и применяем обращение процедуры BWT, начиная с <math>SA^{-1} [j \cdot s]</math> вместо i*. Это дает нам символы с j' • s - 1 до i в обратном порядке и требует не более j - i + s шагов.