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

Пусть дана текстовая строка T = t1 t 2... tn над алфавитом E размера CT. Задача индексации сжатого текста (CTI) заключается в замене T экономичной по памяти структурой данных, способной эффективно отвечать на основные запросы по сравнению строк и подстрок над T. Примеры типичных запросов, требующих ответов с использованием подобного индекса:

• count(P): подсчитать, сколько раз заданная строка шаблона P = p1p2 : : : pm встречается в T.

• display(i,j): вернуть T[i, j].

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

BWT обладает свойством, заключающимся в том, что символы, имеющие одинаковый контекст (т.е. строки, следующие за ними в T), в Tbwt являются последовательными. Это упрощает сжатие Tbwt, достигая объема памяти, близкого к эмпирическим энтропиям высокого порядка [10]. С другой стороны, суффиксный массив является универсальным текстовым индексом, позволяющим, например, вести подсчет запросов за время O(m log n) (с использованием двух операций бинарного поиска в массиве SA), после чего можно локализовать вхождения за оптимальное время.

Сначала мы обратимся к извлечению произвольных подстрок из этого сжатого текстового представления, а затем рассмотрим возможности поиска. Для извлечения из структуры всего текста (то есть для поддержки отображения(1, n)) достаточно инвертировать BWT. Для этого рассмотрим таблицу LF[1, n], определенную таким образом, что если выполнить перестановку T[i] в Tbwt[j], а T[i - 1] – в Tbwt[j0], то LF[j] = f. После этого можно сразу же извлечь T в обратном порядке, напечатав rbwt[(-*] . xbwt[LF[i*]] • Tbvit[LF[LF[i*]]] (по определению Xbwt[i*] соответствует T[n]).

Лемма 1 (Ферраджина и Манзини, 2005 [ ]). LF[i] = C(c) + rankc(i), где c = Tbwt[i], C(c) сообщает, сколько раз в Tbwt встречаются символы меньше c, а rankc(i) – сколько раз символ c встречается в Tbwt[1, i].

Теперь рассмотрим потребность в памяти. Значения C() можно тривиально хранить в таблице на log2 n бит. Tbwt[i] можно вычислить за время О(ст) путем проверки, для какого c выполняется rankc(i) /rankc(i - 1). Частоту выборки можно взять в виде s = ©(log +e n), так что для выборок потребуется o(n) бит. Единственная реальная проблема заключается в предварительной обработке текста для запросов rankc(). В последние годы в этой области велись интенсивные исследования и было предложено множество решений. Первый предложенный алгоритм строит несколько маленьких структур данных с частичной суммой поверх сжатого BWT и достигает следующего результата:

Исходный FM-индекс налагает серьезные ограничения на размер алфавита. В последующих работах эти ограничения были устранены. С концептуальной точки зрения самый простой способ добиться более дружественного к алфавитам экземпляра FM-индекса заключается в построении дерева вейвлетов [ ] на Tbwt. Это бинарное дерево на S, устроенное таким образом, что каждый узел v обрабатывает подмножество алфавита S(v), которое делит между своими детьми. Корень обрабатывает элемент E, а каждый лист обрабатывает один символ. Каждый узел v кодирует такие позиции i таким образом, что Tbwt[i] 2 S(v). Для этих позиций в узле v хранится только битовый вектор, указывающий, какая из них направляется налево, а какая – направо. Битовые векторы узла предварительно обрабатываются для выполнения запросов rank1 ()  за константное время, используя o(n)-битные структуры данных [6, 12]. Гросси и др. [ ] показали, что дерево вейвлетов, построенное с использованием кодировки [ ], занимает nH0 + o(n log cr) бит. После этого легко смоделировать один запрос rankc() при помощи log2 запросов rank1(). С теми же затратами можно получить T [i]. Более поздние усовершенствования улучшили требования по времени, позволив получить, например, следующий результат:

Ферраджина и др. [ ] разработали технику под названием «форсирование сжатия» (compression boosting), которая находит оптимальное разбиение Tbwt, такое, что при сжатии каждого элемента по отдельности с использованием его модели нулевого порядка результат пропорционален энтропии k-го порядка. Этот подход можно совместить с идеей SSA, построив дерево вейвлетов отдельно для каждого отрезка и некоторые дополнительные структуры для решения глобальных запросов rankc() для отдельных деревьев вейвлетов: