Суффиксный массив

Суффиксный массив — лексикографически отсортированный массив всех суффиксов строки. Эта структура данных была разработана Юджином Майерсом и Уди Манбером как более экономная альтернатива суффиксному дереву с точки зрения необходимой памяти. Она часто применяется там, где необходим быстрый поиск подстрок, например в преобразовании Барроуза — Уилера (BWT), а также в качестве структуры данных в поисковом индексе.

Пример

Рассмотрим строку «abracadabra» длиной 11 символов.

a  b  r  a  c  a  d  a  b  r  a
1  2  3  4  5  6  7  8  9  10 11

Отсортированный список её суффиксов:

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

Суффиксный массив этой строки — {11,8,1,4,6,9,2,5,7,10,3}, потому что суффикс «a» начинается с 11-го знака, суффикс «abra» — с 8-го, и так далее, вплоть до последнего суффикса «racadabra», который начинается с третьего символа исходного слова.

Теперь с помощью этого массива можно легко найти все подстроки. Например, если нужно найти подстроку «ab», достаточно найти все суффиксы, которые начинаются на «ab». За счёт сортировки по алфавиту они находятся рядом друг с другом. Используя бинарный поиск, мы находим 2-й и 3-й суффиксы «abra» и «abracadabra», которым соответствуют 2-й и 3-й элемент суффиксного массива (8 и 1). Это означает, что искомая подстрока «ab» встречается на первом и восьмом символе в исходном слове.

Построение

Суффиксный массив можно построить как с помощью суффиксного дерева, так и без него, дополнив строку до циклической длины степени двойки, и применив к нему конкретный алгоритм.

Через суффиксное дерево

Строим суффиксное дерево для строки T$, где T — текст. В этом суффиксном дереве запускаем поиск в глубину с приоритетом выбора лексиграфически минимальных рёбер. Во время поиска считаем, что $ (сентинел) — лексикографически наименьший символ. Приход в лист достижение некоторого ещё не рассмотренного[что?] в данный момент лексикографически наименьшего суффикса, значение в листе которого, начальный индекс в, нужно записать в текущую ячейку суффиксного массива. Так получается суффиксный массив для всего текста.

Сложность построения — $O(|T|)$, линия включает в себя построение суффиксного дерева и обход в глубину.

Поиск

Поиск в суффиксном массиве можно осуществить через бинарный поиск. Его худшая оценка $O(n\log {m})$. Но можно ускорить до $O(n+\log _{2}{m})$.

Наивный бинарный поиск

Идея поиска в том, что если образец встречается в тексте, то все суффиксы, начинающиеся с $P$, в суффиксном массиве $Pos$ будут располагаться рядом. Запускаем двоичный поиск $P$ в суффиксном массиве $Pos$ и находим такой наименьший индекс $i$: $Pos(i-1)$ не начинается с $P$ и наибольший индекс $i'$: $Pos(i'+1)$ тоже не начинается с $P$. Тогда образец входит в позициях $Pos(i)$ до $Pos(i')$. Если существует много префиксов паттерна, то оценка работы падает до $O(n\log {m})$.

Простое ускорение

$L$, $R$ — границы интервала поиска. На начале $L=1$, $R=m$. Запоминаем длину префиксов $Pos(L)$, $Pos(R)$, совпадающих с префиксом $P:l,r$. $mlr=min(l,r)$. При очередном сравнении в позиции $M={\frac {L+R}{2}}$ начинаем обрабатывать символы не с первой позиции, а с $mlr(l,r)+1$. Обычно время работы $O(n+\log {m})$, но худшее время работы всё ещё $O(n\log {m})$.

Ускорение через LCP

Наибольший общий префикс (англ. Largest Common Prefix) — для двух строк $S_{1}$, $S_{2}$ $LCP(S_{1},S_{2})$ — длина наибольшего совпадающего префикса.

В этом алгоритме будем считать, что $LCP$ для любых двух суффиксов вычисляется за $O(1)$. Функция вычисляется на этапе препроцессинга при построении дерева. Также верно утверждение: $LCP(i,j)=min(LCP(k,k+1)),i\leq k<j$.

Благодаря этой функции можно оптимизировать бинарный поиск по суффиксному массиву.

Лемма: Если на левой и правой границе ($L$, $R$ соответственно индексы суффиксного массива) совпадают первые $k$ символов суффикса, то столько же символов будет совпадать для всех суффиксов на отрезке $[L,R]$.

$L=1$, $R=|T|$, $l=LCP(P,L)$, $r=LCP(P,R)$. Дальше возможны следующие случаи $l=r$. Сравниваем суффикс в $M={\frac {L+R}{2}}$ с паттерном с позиции $l+1$. Суффикс лексикографически больше или равен $P$ и на $i$ позиции в суффиксе произошло несовпадение (если произошло лексикографическое совпадение $M$ и $P$, то считаем $i$ равным $|P|+1$), то меняем границы поиска: $L=M,R=R,l=i-1$. Иначе меняем границы так: $L=L,R=M,r=i-1$. $l>r$. Проверяем $LCP(L,M),M={\frac {L+R}{2}}$. $LCP(L,M)>l$. В таком случае после позиции $l$ в суффиксе на позиции $M$ следует некоторое количество тех же самых символов, что и в $L$, которые не совпадают с паттерном (если бы совпадали, то $l$ было бы больше). Значит, нужно изменить границы следующим образом: $L=M,R=R,l=l$. $LCP(L,M)<l$, это значит, что после позиции $LCP(L,M)$ в суффиксе на позиции $M$ следует несовпадение с некоторыми символами префикса $L$, причём в $L$ содержится большая часть совпадения с паттерном — значит в отрезке $[M,R]$ точно не найдется вхождений паттерна. Изменить границы нужно следующим образом: $L=L,R=M,r=LCP(L,M)$. $LCP(L,M)=l$, это значит, что на отрезке $[L,M]$ во всех суффиксах совпадают первые $l$ символов, и нельзя сразу сказать, в какой подотрезок нужно пойти. Для разрешения этого необходимо сравнить с паттерном $P$ следующие за позицией $l$ символы в суффиксе $M$. Если $M$ лексикографически меньше или равно $P$ и на $i$-ой позиции произошло несовпадение (если произошло лексикографическое совпадение $M$ и $P$, то считаем $i$ равным $|P|+1$), то изменяем границы так: $L=M$, $R=R$, $l=i-1$; иначе ($M$ лексикографически больше): $R=M$, $L=L$,$r=i-1$. $l<r$. Проверяем $LCP(R,M),M={\frac {L+R}{2}}$ и сравниваем с $r$ как на прошлом шаге, но $L$ меняем на $R$ и $l$ на $r$. Алгоритм работает, пока $l$ и $r$ не станут равными $|P|$. Это значит, что есть отрезок совпадения. Если не выполняется инвариант $L<P<R$, то паттерна как подстроки в тексте нет.

Такое сверхускорение даёт время $O(|P|+\log _{2}{|T|})$, так как выполняется $\log _{2}{|T|}$ итераций по суффиксному массиву.

Связанные алгоритмы

• Алгоритм Касаи построения массива наибольших общих префиксов.

См. также

• Суффиксное дерево

Ссылки

• Суффиксный массив. Алгоритм построения и применения
• Суффиксный массив и BWT
• Визуализатор алгоритма (требуется Java)
• Дискретная математика: алгоритмы. Суффиксные массивы
• Реализация суффиксного массива на Java

Литература

• Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер. с англ. И. В. Романовского. — 2-е изд. — СПб.: Невский Диалект, 2003. — 654 с.
• Смит Б. Методы и алгоритмы вычислений на строках = Computing Patterns in Strings. — М.: Вильямс, 2006. — 496 с. — ISBN 5-8459-1081-1, 0-201-39839-7.