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

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

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

'''Лемма 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>.