Индексирование сжатого текста
Ключевые слова и синонимы
Экономичная по памяти индексация текста; полнотекстовая индексация сжатого текста; внутренняя индексация
Постановка задачи
Пусть дана текстовая строка T = t1 t 2... tn над алфавитом E размера CT. Задача индексации сжатого текста (CTI) заключается в замене T экономичной по памяти структурой данных, способной эффективно отвечать на основные запросы по сравнению строк и подстрок над T. Примеры типичных запросов, требующих ответов с использованием подобного индекса:
• count(P): подсчитать, сколько раз заданная строка шаблона P = p1p2 : : : pm встречается в T.
• locate(P): вернуть местоположения всех вхождений P в 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), после чего можно локализовать вхождения за оптимальное время.
Ферраджина и Манзини [ ] обнаружили способ объединить высокую сжимаемость BWT и индексирующие свойства суффиксного массива. Структура, в сущности, представляет собой сжатое представление BWT плюс некоторые небольшие дополнительные структуры, делающие его пригодным для поиска.
Сначала мы обратимся к извлечению произвольных подстрок из этого сжатого текстового представления, а затем рассмотрим возможности поиска. Для извлечения из структуры всего текста (то есть для поддержки отображения(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]).
При поиске экономичного по памяти представления пространства массива LF Ферраджина и Манзини заметили, что каждый элемент LF[i] может быть выражен следующим образом:
Лемма 1 (Ферраджина и Манзини, 2005 [ ]). LF[i] = C(c) + rankc(i), где c = Tbwt[i], C(c) сообщает, сколько раз в Tbwt встречаются символы меньше c, а rankc(i) – сколько раз символ c встречается в Tbwt[1, i].
Запросы display(i, j) общего вида основываются на регулярной выборке из текста. Каждая текстовая позиция вида / • s, где s – частота дискретизации, хранится вместе с SA-1 [/ • s], на которую указывает позиция суффиксного массива. Для выполнения запроса display(i, j) мы начинаем с наименьшей выбранной текстовой позиции f • s > j и применяем обращение процедуры BWT, начиная с SA-1 [f ■ s] вместо i*. Это дает нам символы с / • s - 1 до i в обратном порядке и требует не более j - i + s шагов.
Кроме того, оказывается, что то же самое двухкомпонентное выражение LF[i] позволяет эффективно выполнять запросы типа count(P). Идея заключается в том, что если известен диапазон суффиксного массива, скажем SA[spi, epi], такого что единственными суффиксами, содержащими P[i, m] в качестве префикса, являются суффиксы T[SA[spi], n], T[SA[spi + 1], n], ..., T[SA[epi], n], то новый диапазон SA[sp,-_i, ep,-_i], суффиксы которого содержат P[i – 1, m] в качестве префикса, можно вычислить следующим образом: spi-i = C(P[i - 1]) + rankp[i-i](spi - 1) + 1 и epi-i = C(P[i - 1]) + rankp[i-i](epi). После этого достаточно просканировать шаблон в обратном порядке и вычислить значения C() и rankc() 2m раз, чтобы определить (возможно, пустой) диапазон суффиксного массива, в котором все суффиксы начинаются с полной P. Возврат ep1 - sp1 + 1 отвечает на запрос count(P), вообще не требуя наличия суффиксного массива.
Для локализации каждого такого вхождения SA[i], sp1 < i < ep1, можно вычислить последовательность i, LF[i], LF[LF[i]], ... до тех пор, пока не будет достигнут LF [i], являющийся выбранной позицией суффиксного массива и, таким образом, явно хранящийся в структуре выборки, предназначенной для запросов display(i, j). Тогда SA[i] = SA[LFk[i]] + k. Поскольку мы перемещаемся по тексту практически последовательно, мы не можем сделать в этом процессе более s шагов.
Теперь рассмотрим потребность в памяти. Значения C() можно тривиально хранить в таблице на log2 n бит. Tbwt[i] можно вычислить за время О(ст) путем проверки, для какого c выполняется rankc(i) /rankc(i - 1). Частоту выборки можно взять в виде s = ©(log +e n), так что для выборок потребуется o(n) бит. Единственная реальная проблема заключается в предварительной обработке текста для запросов rankc(). В последние годы в этой области велись интенсивные исследования и было предложено множество решений. Первый предложенный алгоритм строит несколько маленьких структур данных с частичной суммой поверх сжатого BWT и достигает следующего результата:
Теорема 2 (Ферраджина и Манзини, 2005 [3]). Задача CTI может быть решена с помощью так называемого FM-индекса (FM-Index, FMI) размером 5nHk + o(n log cr) бит, выполняющего операцию count(P) за время O(m), locate(P) за время O(cr log1+e n) на одно вхождение, а display(i, j) – за время O(a(j — i + log1+e n)). Здест Hk – эмпирическая энтропия строки T k-го порядка, a = o(log n/loglog n), k < log(J(M/log n) - !(1), а £ > 0 – произвольная константа.
Исходный 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]. Более поздние усовершенствования улучшили требования по времени, позволив получить, например, следующий результат:
Теорема 3 (Макинен и Наварро, 2005 [3]). Задача CTI может быть решена с помощью так называемого сокращенного суффиксного массива (Succinct Suffix Array SSA) размером пЩ + o(n log cr) бит, выполняющего операцию count(P) за время O(m(1 + log a/ log log n)), locate(P) – за время O(log1+e n log al log log n) на одно вхождение, а display(i, j) – за время O((j - i + log1+e n) log cr/log log n). Здесь H0 – энтропия нулевого порядка для T,a = o(n), а e > 0 – произвольная константа.
Ферраджина и др. [ ] разработали технику под названием «форсирование сжатия» (compression boosting), которая находит оптимальное разбиение Tbwt, такое, что при сжатии каждого элемента по отдельности с использованием его модели нулевого порядка результат пропорционален энтропии k-го порядка. Этот подход можно совместить с идеей SSA, построив дерево вейвлетов отдельно для каждого отрезка и некоторые дополнительные структуры для решения глобальных запросов rankc() для отдельных деревьев вейвлетов:
Теорема 4 ([Ферраджина и др. [4]). Задача CTI может быть решена с помощью так называемого дружественного к алфавитам FM-индекса (Alphabet-Friendly FM-Index, AF-FMI) размером nHk + o(n log cr) бит, имеющего ту же временную сложностьи те же ограничения, что и SSA при k < cdog^ n для любого константного 0 < a < 1.
Недавно проведенный анализ [ ] показал, что требования к памяти простого алгоритма SSA ограничены тем же количеством бит nHk + o(n log a), что теоретически делает подход на базе форсирования для достижения того же результата излишним. На практике реализации в работах [4, 7] намного превосходят реализации, построенные непосредственно на этой упрощенной идее.
Применение
Анализ последовательностей в биоинформатике, поиск и извлечение в запросах на восточных и агглютинирующих языках, мультимедийных потоках и даже сценариях работы со структурированными и традиционными базами данных.
Ссылки на код и наборы данных
Сайт Pizza-Chili (http://pizzachili.dcc.uchile.cl или http://pizzachili.di.unipi.it) содержит подборку стандартизированных реализаций библиотек, а также наборы данных и рещультаты экспериментальных сравнений.
См. также
Литература
1. Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)
2. Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression in optimal linear time. J. ACM 52(4), 688-713(2005)
3. Ferragina, P. Manzini, G.: Indexing compressed texts. J. ACM 52(4), 552-581 (2005)
4. Ferragina, P., Manzini, G., Makinen, V., Navarro, G.: Compressed representation of sequences and full-text indexes. ACM Trans. Algorithms 3(2) Article 20 (2007)
5. Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841-850 (2003)
6. Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 549-554 (1989)
7. Makinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1),40-66 (2005)
8. Makinen, V., Navarro, G.: Dynamic entropy-compressed se quences and full-text indexes. In: Proc. 17th Annual Symposium on Combinatorial Pattern Matching (CPM). LNCS, vol. 4009, pp. 307-318 (2006) Extended version as TR/DCC-2006-10, Department of Computer Science, University of Chile, July 2006
9. Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935-948 (1993)
10. Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM 48(3), 407-430 (2001)
11. Navarro, G., Makinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1) Article 2 (2007)
12. Raman, R., Raman, V., Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242 (2002)
