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

Изящное решение задачи достигается за счет применения комбинации ''преобразования Барроуза-Уилера'' (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].

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

Сначала мы обратимся к извлечению произвольных подстрок из этого сжатого текстового представления, а затем рассмотрим возможности поиска. Для извлечения из структуры всего текста (то есть для поддержки отображения(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]).