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

Су́ффиксный автома́т (англ. suffix automaton, directed acyclic word graph) — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова $S=s_{1}s_{2}\dots s_{n}$ и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова $S$ существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин.

Суффиксный автомат
англ. suffix automaton англ. directed acyclic word graph
Суффиксный автомат для abbcbc
Тип	Индекс подстрок
Год изобретения	1983
Автор	Ансельм Блумер, Джанет Блумер, Анджей Эренфехт, Дэвид Хаусслер, Росс Макконнелл
Сложность в О-символике
В худшем случае Построение $O(\vert S\vert \log \vert \Sigma \vert )$ Расход памяти $O(\vert S\vert )$
Медиафайлы на Викискладе

Суффиксный автомат был впервые описан группой учёных из Денверского и Колорадского университетов в 1983 году, они же показали, что размер автомата линейно зависит от длины $S$, а также предложили онлайн-алгоритм для его построения с линейным временем работы. В дальнейших работах на эту тему была обнаружена тесная связь суффиксного автомата с суффиксными деревьями, а сама концепция суффиксного автомата получила различные обобщения. Так были введены сжатый суффиксный автомат, получаемый из исходного процедурой, аналогичной той, которая применяется к суффиксному бору для получения суффиксного дерева, а также обобщённый суффиксный автомат, который строится для набора слов $S_{1},S_{2},\dots ,S_{k}$ и принимает слова, являющиеся суффиксами хотя бы одного из данных.

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

История

Ансельм Блумер, на доске изображён сжатый суффиксный автомат для строк ababc и abcab

Концепция суффиксного автомата была представлена группой учёных из Денверского и Колорадского университетов Ансельмом Блумером, Анджеем Эренфехтом, Дэвидом Хаусслером, Россом МакКоннеллом и Джанет Блумер в 1983 году, хотя связанные с ним структуры встречались ранее в работах Питера Вайнера, Вона Пратта и Анатолия Олесьевича Слисенко, посвящённых алгоритмам построения суффиксных деревьев. В той же работе Блумер и другие показали, что построенный по слову $S$ длины больше $1$ автомат содержит не больше $2|S|-1$ состояний и не больше $3|S|-4$ переходов, а также привели линейный алгоритм построения автомата.

В 1983 году Му Тянь Чэнь и Джоэл Сейферас независимо разработали алгоритм построения суффиксного автомата, показывающий, что алгоритм Вайнера, предложенный в 1973 году для построения суффиксного дерева слова $S$, также строит суффиксный автомат для обращённого слова ${\textstyle S^{R}}$ в качестве вспомогательной структуры. В 1987 году Блумер и другие, по аналогии с суффиксным деревом, описали сжатый суффикный автомат, получаемый из суффиксного автомата удалением нефинальных состояний с полустепенью исхода, равной единице, а в 1997 году Максим Крошемор и Рено Верин разработали линейный алгоритм для его прямого построения. В 2001 году Сюнсукэ Инэнага и другие разработали линейный онлайн-алгоритм для построения сжатого суффиксного автомата, а также линейный алгоритм для построения сжатого суффиксного автомата для набора слов, заданного префиксным деревом.

В своей исходной работе Блумер с коллегами определили описанную ими структуру как минимальный автомат, распознающий все подстроки (а не суффиксы) данного слова. Данную структуру они назвали ориентированным ациклическим графом слов (англ. directed acyclic word graph). Впоследствии данное название также использовалось как синоним детерминированного ациклического конечного автомата — минимального автомата, распознающего произвольный конечный набор слов (не обязательно составляющих множество суффиксов или подстрок некоторой строки).

Обозначения

При описании суффиксных автоматов и связанных с ними фактов и теорем часто используются обозначения из теории формальных языков в целом и теории автоматов в частности:

• Алфавит — конечное множество $\Sigma$, из которого могут состоять слова. Его элементы называются символами;
• Слово — конечная последовательность символов алфавита $\omega =\omega _{1}\omega _{2}\dots \omega _{n}$. Длина слова $\omega$ обозначается как $|\omega |=n$;
• Формальный язык — некоторое множество слов над заданным алфавитом;
• Язык всех слов обозначается как $\Sigma ^{*}$(здесь символ «*» несёт смысл звезды Клини), пустое слово (слово нулевой длины) — символом $\varepsilon$;
• Конкатенация (произведение) слов $\alpha =\alpha _{1}\alpha _{2}\dots \alpha _{n}$ и $\beta =\beta _{1}\beta _{2}\dots \beta _{m}$ обозначается как $\alpha \cdot \beta$ или $\alpha \beta$ и равна слову, получаемому приписыванием $\beta$ к $\alpha$ справа, то есть, $\alpha \beta =\alpha _{1}\alpha _{2}\dots \alpha _{n}\beta _{1}\beta _{2}\dots \beta _{m}$;
• Конкатенация языков $A$ и $B$ обозначается как $A\cdot B$ или $AB$ и равна множеству попарных конкатенаций $AB=\{\alpha \beta :\alpha \in A,\beta \in B\}$;
• Если слово $\omega \in \Sigma ^{*}$ представимо в виде $\omega =\alpha \gamma \beta$, где $\alpha ,\beta ,\gamma \in \Sigma ^{*}$, то слова $\alpha$, $\beta$ и $\gamma$ называют префиксом, суффиксом и подсловом (подстрокой) слова $\omega$ соответственно;
• Если $T_{l}T_{l+1}\dots T_{r}=S$, то говорят, что слово $S$ входит (встречается) в $T$ как подслово. При этом $l$ и $r$ называются левой и правой позициями вхождения $S$ в $T$ соответственно.

Структура автомата

Формально, детерминированный конечный автомат определяется набором из пяти элементов ${\mathcal {A}}=(\Sigma ,Q,q_{0},F,\delta )$, где:

• $\Sigma$ — алфавит, из которого состоят слова, распознаваемые автоматом,
• $Q$ — множество состояний автомата,
• $q_{0}\in Q$ — начальное состояние автомата,
• $F\subset Q$ — множество финальных состояний автомата,
• $\delta :Q\times \Sigma \mapsto Q$ — частично определённая функция переходов автомата, такая что $\delta (q,\sigma )$ для $q\in Q$ и $\sigma \in \Sigma$ либо не определена, либо указывает на состояние, в которое может быть произведён переход из $q$ по $\sigma$.

Чаще всего на практике конечные автоматы представляются в виде ориентированного графа (диаграммы) такого что:

• Множество вершин графа соответствует множеству состояний $Q$,
• В графе выделена некоторая вершина, соответствующая начальному состоянию $q_{0}$,
• В графе выделен набор вершин, соответствующих множеству финальных состояний $F$,
• Множество дуг в графе соответствует множеству переходов $\delta$,
• При этом переходу ${\textstyle \delta (q_{1},\sigma )=q_{2}}$ соответствует дуга из $q_{1}$ в $q_{2}$, помеченная символом алфавита $\sigma$. Такой переход также обозначают как ${\textstyle q_{1}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}q_{2}}$.

В таком графе вершины и дуги отождествляются с состояниями и переходами автомата соответственно. Автомат принимает слово $\omega =\omega _{1}\omega _{2}\dots \omega _{m}$ в том и только том случае, если существует путь из начального состояния $q_{0}$ в некоторое финальное состояние $q\in F$, такой что если сконкатенировать символы, встретившиеся на этом пути, то получится слово $\omega$. Множество слов, которые принимает автомат, образуют язык этого автомата.

Состояния автомата

Основная статья: Минимизация ДКА

Правым контекстом слова $\omega$ относительно языка $L$ называют множество $[\omega ]_{R}=\{\alpha :\omega \alpha \in L\}$. То есть это множество слов $\alpha$, при приписывании которых к слову $\omega$ справа получается слово из языка $L$. Правые контексты индуцируют естественное отношение эквивалентности $[\alpha ]_{R}=[\beta ]_{R}$ на множестве всех слов. Если язык $L$ может быть задан некоторым детерминированным конечным автоматом, то для него существует единственный, с точностью до изоморфизма, автомат, обладающий при этом наименьшим возможным числом состояний. Такой автомат называется минимальным для данного языка $L$, теорема Майхилла — Нероуда позволяет задать его в явном виде:

Минимальный автомат, распознающий язык $L$ над алфавитом $\Sigma$, может быть задан следующим образом:

• Алфавит $\Sigma$ остаётся без изменений,
• Состояниям $Q$ соответствуют правые контексты $[\omega ]_{R}$ всех слов $\omega \in \Sigma ^{*}$,
• Начальному состоянию $q_{0}$ соответствует правый контекст пустого слова $[\varepsilon ]_{R}$,
• Финальным состояниям $F$ соответствуют правые контексты $[\omega ]_{R}$ слов из языка $\omega \in L$,
• Переходы $\delta$ имеют вид $[\omega ]_{R}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}[\omega \sigma ]_{R}$, где $\omega \in \Sigma ^{*}$ и $\sigma \in \Sigma$.

В таких обозначениях, суффиксный автомат — это минимальный ДКА, принимающий язык суффиксов слова $S=s_{1}s_{2}\dots s_{n}$. Правый контекст слова $\omega$ относительно данного языка состоит из слов $\alpha$ таких что $\omega \alpha$ — суффикс $S$. Это позволяет сформулировать следующую лемму, определяющую взаимно-однозначное соответствие между правым контекстом слова и множеством позиций его вхождений в $S$ в качестве подслова:

Пусть $endpos(\omega )=\{r:\omega =s_{l}\dots s_{r}\}$ — множество правых позиций вхождений $\omega$ в $S$.

Между элементами множеств $endpos(\omega )$ и $[\omega ]_{R}$ есть следующее взаимно-однозначное соответствие:

• Если $x\in endpos(\omega )$, то $s_{x+1}s_{x+2}\dots s_{n}\in [\omega ]_{R}$;
• Если $\alpha \in [\omega ]_{R}$, то $n-\vert \alpha \vert \in endpos(\omega )$.

Например, для слова $S=abacaba$ и его подслова $\omega =ab$ выполнено $endpos(ab)=\{2,6\}$ и $[ab]_{R}=\{a,acaba\}$. Неформально, $[ab]_{R}$ состоит из слов, которые следуют за вхожениями $ab$ до конца слова, а $endpos(ab)$ — из позиций этих вхождений. В этом примере, элементу $x=2\in endpos(ab)$ соответствует слово $s_{3}s_{4}s_{5}s_{6}s_{7}=acaba\in [ab]_{R}$. В то же время, слову $a\in [ab]_{R}$ соответствует элемент $7-|a|=6\in endpos(ab)$.

Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть $|\alpha |\leq |\beta |$, тогда:

• Если у $[\alpha ]_{R}$ и $[\beta ]_{R}$ есть хотя бы один общий элемент $x$, то общий элемент также есть у $endpos(\alpha )$ и $endpos(\beta )$. Это, в свою очередь, значит, что $\alpha$ — суффикс $\beta$ и потому $endpos(\beta )\subset endpos(\alpha )$ и $[\beta ]_{R}\subset [\alpha ]_{R}$. В приведённом выше примере, $a\in [ab]_{R}\cap [cab]_{R}$ и, как следствие, $ab$ — суффикс $cab$, а также $[cab]_{R}=\{a\}\subset \{a,acaba\}=[ab]_{R}$ и $endpos(cab)=\{6\}\subset \{2,6\}=endpos(ab)$;
• Если $[\alpha ]_{R}=[\beta ]_{R}$, то $endpos(\alpha )=endpos(\beta )$, то есть $\alpha$ встречается в $S$ только в качестве суффикса $\beta$. Это видно на примере слов $\alpha =b$ и $\beta =ab$, для которых $[b]_{R}=[ab]_{R}=\{a,acaba\}$ и $endpos(b)=endpos(ab)=\{2,6\}$;
• Если $[\alpha ]_{R}=[\beta ]_{R}$ и $\gamma$ — суффикс $\beta$, такой что $|\alpha |\leq |\gamma |\leq |\beta |$, то $[\alpha ]_{R}=[\gamma ]_{R}=[\beta ]_{R}$. В приведённом выше примере, $[c]_{R}=[bac]_{R}=\{aba\}$, а «промежуточным» суффиксом является $\gamma =ac$. И действительно, $[ac]_{R}=\{aba\}$.

Таким образом, любое состояние $q=[\alpha ]_{R}$ суффиксного автомата принимает некоторую непрерывную цепочку вложенных друг в друга суффиксов наибольшей строки из этого состояния.

Левым расширением ${\overset {\scriptstyle {\leftarrow }}{\gamma }}$ строки $\gamma$ называют самую длинную строку $\omega$, имеющую тот же правый контекст, что и $\gamma$. Длину $|{\overset {\scriptstyle {\leftarrow }}{\gamma }}|$ самой длинной строки, принимаемой состоянием $q=[\gamma ]_{R}$, обозначают как $len(q)$. Для него верно, что:

Левое расширение строки $\gamma$ может быть представлено в виде ${\overleftarrow {\gamma }}=\beta \gamma$, где $\beta$ — самое длинное слово, такое что любому вхождению слова $\gamma$ в $S$ предшествует слово $\beta$.

Суффиксной ссылкой $link(q)$ от состояния $q=[\alpha ]_{R}$ называют указатель на состояние $p$, содержащее наибольший суффикс $\alpha$, который не принимается состоянием $q$.

В таких обозначениях можно сказать, что состояние $q=[\alpha ]_{R}$ принимает в точности все суффиксы ${\overset {\scriptstyle {\leftarrow }}{\alpha }}$, которые длиннее $len(link(q))$ и не длиннее $len(q)$. Кроме того, верно следующее:

Суффиксные ссылки образуют дерево ${\mathcal {T}}(V,E)$, которое можно задать явно следующим образом:

1. Вершинам $V$ соответствуют левые расширения ${\overleftarrow {\omega }}$ всех подстрок $S$,
2. Рёбра $E$ соединяют вершины $({\overleftarrow {\omega }},{\overleftarrow {\alpha \omega }})$, такие что $\alpha \in \Sigma$ и ${\overleftarrow {\omega }}\neq {\overleftarrow {\alpha \omega }}$.

Связь с суффиксным деревом

Преобразования суффиксных структур

Основная статья: Суффиксное дерево

Префиксным деревом (или бором) называют корневое ориентированное дерево, дуги которого помечены символами таким образом, что из любой вершины $v$ этого дерева исходит не больше одной дуги, помеченной данным символом. Некоторые вершины в префиксном дереве помечены. Говорят, что префиксное дерево задаёт множество слов, определяемое путями из корня дерева в помеченные вершины. Таким образом, префиксные деревья представляют собой особую разновидность конечных автоматов, если рассматривать корень как начальное состояние, а помеченные вершины — как финальные состояния. Суффиксным бором слова $S$ называют префиксное дерево, задающее язык суффиксов этого слова. Суффиксным деревом называют дерево, получаемое из суффиксного бора процедурой сжатия, при которой последовательно идущие рёбра склеиваются если между ними находится нефинальная вершина, степень которой равна 2.

По определению, суффиксный автомат может быть получен минимизацией суффиксного бора. Кроме того, сжатый суффиксный автомат может быть получен как минимизацией суффиксного дерева (если считать, что символы алфавита — это слова на рёбрах дерева), так и сжатием обычного автомата. Однако, помимо очевидной связи между суффиксным автоматом и суффиксным деревом одной и той же строки, можно также установить некоторое соответствие между суффиксным автоматом строки $S=s_{1}s_{2}\dots s_{n}$ и суффиксным деревом обращённой строки $S^{R}=s_{n}s_{n-1}\dots s_{1}$.

Аналогично правым контекстам можно ввести левые контексты $[\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\}$ и правые расширения ${\overset {\scriptstyle {\rightarrow }}{\omega ~}}$, соответствующие самым длинным строкам, имеющим заданный левый контекст, а также отношение эквивалентности $[\alpha ]_{L}=[\beta ]_{L}$. Если рассматривать правые расширения относительно языка $L$ префиксов строки $S$, то можно получить, что:

Суффиксное дерево строки $S$ может быть задано в явном виде следующим образом:

• Вершинам $V$ соответствуют правые расширения ${\overrightarrow {\omega }}$ всех подстрок $S$,
• Рёбрам $E$ соответствуют тройки $({\overrightarrow {\omega }},x\alpha ,{\overrightarrow {\omega x}})$ такие что $x\in \Sigma$ и ${\overrightarrow {\omega x}}={\overrightarrow {\omega }}x\alpha$.

Здесь тройка $(v_{1},\omega ,v_{2})\in E$ значит, что на ребре из $v_{1}$ в $v_{2}$ записана строка $\omega$.

Из чего следует, что дерево суффиксных ссылок для автомата строки $S$ и суффиксное дерево строки $S^{R}$ изоморфны:

Суффиксные структуры слов abbcbc и cbcbba
Суффиксный автомат для слова abbcbc Суффиксный бор, суффиксное дерево и сжатый суффиксный автомат для слова abbcbc. Номера вершин соответствуют состояниям, в которые они переходят при минимизации или сжатии Суффиксное дерево для слова cbcbba (дерево суффиксных ссылок для автомата слова abbcbc)

Аналогично левым расширениям, для правых расширений также может быть сформулирована структурная лемма:

Правое расширение строки $\gamma$ может быть представлено в виде ${\overrightarrow {\gamma }}=\gamma \alpha$, где $\alpha$ — самое длинное слово, такое что за любым вхождением $\gamma$ в $S$ сразу следует слово $\beta$.

Размер

В суффиксном автомате строки $S$ длины $n>1$ не больше $2n-1$ состояний и не больше $3n-4$ переходов, причём данные оценки достигаются на строках $abb\dots bb=ab^{n-1}$ и $abb\dots bc=ab^{n-2}c$ соответственно. Можно также сформулировать более сильное утверждение о связи числа состояний и переходов в автомате: $|\delta |\leq |Q|+n-2$, где $|\delta |$ и $|Q|$ — это число переходов и состояний соответственно.

Максимальные суффиксные автоматы
Суффиксный автомат для $ab^{n-1}$ Суффиксный автомат для $ab^{n-2}c$

Построение

Суффиксный автомат строки $S=s_{1}s_{2}\dots s_{n}$ строится последовательным наращиванием слова, для которого он построен. Изначально имеется тривиальный автомат, построенный для пустого слова, а затем на каждом шаге к текущему слову добавляется один символ, что влечёт за собой перестройку состояний и переходов автомата.

Изменение состояний

После приписывания нового символа к слову, некоторые классы эквивалентности изменятся. Пусть $[\alpha ]_{R_{\omega }}$ — правый контекст слова $\alpha$ относительно языка суффиксов слова $\omega$. Тогда переход от $[\alpha ]_{R_{\omega }}$ к $[\alpha ]_{R_{\omega x}}$ при приписывании символа $x$ к слову $\omega$ описывается следующей леммой:

Пусть $\alpha ,\omega \in \Sigma ^{*}$ — некоторые слова над алфавитом $\Sigma$ и $x\in \Sigma$ — некоторый символ этого алфавита. Тогда между правыми контекстами $[\alpha ]_{R_{\omega }}$ и $[\alpha ]_{R_{\omega x}}$ слова $\alpha$ относительно языков суффиксов слов $\omega$ и $\omega x$ соответственно имеет место следующая связь:

• $[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x\cup \{\varepsilon \}$ если $\alpha$ — суффикс $\omega x$;
• $[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x$ в противном случае.

То есть при добавлении одного символа $x$ к текущему слову $\omega$ правый контекст слова $\alpha$ может измениться только в том случае, если $\alpha$ является суффиксом слова $\omega x$. Из этого следует, что разбиение всех слов на классы эквивалентности по $\equiv _{R_{\omega x}}$ является измельчением разбиения на классы эквивалентности по $\equiv _{R_{\omega }}$. Другими словами, если $[\alpha ]_{R_{\omega x}}=[\beta ]_{R_{\omega x}}$, то $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$. Кроме того, при добавлении очередного символа к слову расщепление произойдёт у не более чем двух состояний. В первую очередь будет расщеплено состояние, которому соответствует пустой правый контекст (то есть то, которое принимает язык слов, не входящих в $\omega$ в качестве подслова). Из этого состояния будет выделено новое состояние, содержащее всё слово $\omega x$, а также все его суффиксы, которые встречаются в $\omega x$, но не встречались в $\omega$. Соответственно, правый контекст этих слов, который ранее был пустым, теперь будет состоять только из пустого слова.

Учитывая связь между состояниями суффиксного автомата и вершинами суффиксного дерева, можно отследить и второе состояние, которое может расщепиться при добавлении очередного символа. Так как переход от слова $\omega$ к $\omega x$ соответствует переходу от $\omega ^{R}$ к $x\omega ^{R}$ для обращённой строки, приписывание символа $x$ к строке $\omega$ соответствует внесению одного нового (самого длинного) суффикса $x\omega ^{R}$ в суффиксное дерево строки $\omega ^{R}$. При этом появляется не более двух вершин: одна из них будет соответствовать всему слову $x\omega ^{R}$, а другая может появиться в том месте, где происходит ответвление от дерева. Таким образом, одно новое состояние соответствует правому контексту всей строки $\omega x$, а другое (если оно есть) может соответствовать только суффиксной ссылке этого состояния. Данные наблюдения можно обобщить теоремой:

Пусть $\omega \in \Sigma ^{*}$ и $x\in \Sigma$. Пусть также $\alpha$ является самым длинным суффиксом $\omega x$, который встречается в $\omega$, а $\beta ={\overset {\scriptstyle {\leftarrow }}{\alpha }}$ — его левое расширение относительно $\omega$, то есть самое длинное подслово слова $\omega$ такое что $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$. Тогда для любых подслов $u,v$ слова $\omega$ верно следующее:

• Если $[u]_{R_{\omega }}=[v]_{R_{\omega }}$ и $[u]_{R_{\omega }}\neq [\alpha ]_{R_{\omega }}$, то $[u]_{R_{\omega x}}=[v]_{R_{\omega x}}$;
• Если $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ и $\vert u\vert \leq \vert \alpha \vert$, то $[u]_{R_{\omega x}}=[\alpha ]_{R_{\omega x}}$;
• Если $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ и $\vert u\vert >\vert \alpha \vert$, то $[u]_{R_{\omega x}}=[\beta ]_{R_{\omega x}}$.

В частности, если $\alpha =\beta$ (например, когда $x$ вообще не встречается в $\omega$ и $\alpha =\beta =\varepsilon$), расщепления второго состояния не происходит.

Помимо суффиксных ссылок, в новом автомате также нужно определить финальные состояния. Из структурных свойств автомата следует, что суффиксы любого слова $\alpha$ расположены таким образом, что если $q=[\alpha ]_{R}$, то суффиксы $\alpha$, чья длина превышает $len(link(q))$, лежат в $q$, суффиксы, чья длина больше $len(link(link(q))$, но не больше $len(link(q))$, лежат в $link(q)$ и так далее. Иными словами, для любого суффикса $\alpha$ найдётся вершина в суффиксном пути состояния $q$, который задаётся последовательностью $(q,link(q),link^{2}(q),\dots )$. Соответственно если обозначить состояние, принимающее в текущий момент всю строку $\omega$, как $last$, то терминальными (принимающими суффиксы $\omega$) состояниями будут те и только те состояния, которые входят в суффиксный путь $(last,link(last),link^{2}(last),\dots )$.

Изменение переходов и суффиксных ссылок

Какие-либо изменения при добавлении очередного символа затрагивают не более чем два новых состояния, поэтому изменения в переходах автомата тоже будут затрагивать только эти состояния. После приписывания $x$ к слову $\omega$ образуется новое состояние $[\omega x]_{R_{\omega x}}$, а также, возможно, состояние $[\alpha ]_{R_{\omega x}}$. Суффиксная ссылка из $[\omega x]_{R_{\omega x}}$ будет вести в $[\alpha ]_{R_{\omega x}}$, а из $[\alpha ]_{R_{\omega x}}$ — в $link([\alpha ]_{R_{\omega }})$. Слова из $[\omega x]_{R_{\omega x}}$ встречаются в $\omega x$ только в виде суффиксов, поэтому из $[\omega x]_{R_{\omega x}}$ не должно быть переходов, а ведущие в него переходы должны вести по символу $x$ из суффиксов $\omega$ с длиной хотя бы $|\alpha |$. Состояние $[\alpha ]_{R_{\omega x}}$ отщепляется от $[\alpha ]_{R_{\omega }}$, поэтому переходы из этого состояния будут дублировать таковые у $[\alpha ]_{R_{\omega }}$. А ведущие в него переходы будут вести по символу $x$ из состояний, соответствующим суффиксам $\omega$ длины меньше $|\alpha |$ и не меньше $len(link([\alpha ]_{R_{\omega }}))$, так как ранее эти переходы вели в $[\alpha ]_{R_{\omega }}$ и соответствовали отделившейся части состояния. Состояния, принимающие данные слова, можно определить по суффиксному пути состояния $[\omega ]_{R_{\omega }}$.

Построение суффиксного автомата для слова abbcbc
∅ → a При добавлении первого символа в автомате создаётся единственное новое состояние. Аналогичным образом в суффиксном дереве добавляется единственный лист.	a → ab Новые переходы проводятся из всех финальных состояний, так как новый символ раньше не встречался. По той же причине в дереве суффиксных ссылок новая вершина подвешивается к корню.
ab → abb Состояние 2 принимает слова ab и b, но только b станет суффиксом, поэтому это слово выделяется в состояние 4. В суффиксном дереве развёрнутого слова это соответствует расщеплению ребра, ведущего в вершину 2.	abb → abbc Новый символ раньше не встречался, переходы в него проводятся из всех финальных. В дереве суффиксных ссылок добавляется новый лист, подвешенный к корню.
abbc → abbcb В состоянии 4 только слово b и оно является суффиксом, поэтому расщепления не происходит. Соответственно, в дереве суффиксных ссылок новый лист подвешивается к вершине 4.	abbcb → abbcbc Состояние 5 принимает слова abbc, bbc, bc и c, но только последние два являются суффиксами нового слова, поэтому они отделяются в отдельное состояние 8. Соответственно, в дереве суффиксных ссылок происходит расщепление ребра, ведущего в вершину 5.

Алгоритм построения автомата

Теоретические результаты выше приводят к следующему алгоритму, который принимает символ $x$ и перестраивает суффиксный автомат слова $\omega$ в суффиксный автомат слова $\omega x$:

1. Поддерживается номер состояния $last$, соответствующего всей строке $\omega$;
2. При добавлении символа $x$, номер $last$ запоминается в переменной $p$, а в $last$ записывается номер нового состояния, соответствующего слову $\omega x$;
3. Из состояний, соответствующих суффиксам $\omega$, проставляются переходы в $last$. Для этого идёт обход суффиксного пути $p,link(p),link^{2}(p),\dots$, пока не встретится состояние, из которого уже есть переход по $x$;
4. Дальнейшие действия соответствуют одному из трёх случаев:
   1. Если на всём суффиксном пути ни из одного состояния нет перехода по $x$, то $x$ раньше не встречался в $\omega$ и суффиксная ссылка из $last$ ведёт в $q_{0}$;
   2. Если переход по $x$ нашёлся и ведёт из состояния $p$ в состояние $q$, такое что $len(p)+1=len(q)$, то необходимости расщеплять $q$ нет и достаточно провести суффиксную ссылку из $last$ в $q$;
   3. Если же $len(q)>len(p)+1$, то слова из состояния $q$, чья длина не превосходит $len(p)+1$ должны быть выделены в отдельное состояние $cl$;
5. Если на прошлом шаге было выделено отдельное состояние $cl$, то переходы и суффиксная ссылка из него должны дублировать оные в $q$, при этом $cl$ станет общей суффиксной ссылкой состояний $q$ и $last$;
6. Переходы, которые вели в $q$, но соответствовали словам длины не больше $len(p)+1$, перенаправляются в $cl$. Для этого можно продолжать идти по суффиксному пути $p$, пока не найдётся состояние, переход из которого ведёт не в $q$.

Процедура, реализующая этот алгоритм, может быть описана следующим псевдокодом:

функция add_letter(x):
    определить p = last
    присвоить last = new_state()
    присвоить len(last) = len(p) + 1
    пока δ(p, x) не определено:
        присвоить δ(p, x) = last, p = link(p)
    определить q = δ(p, x)
    если q = last:
        присвоить link(last) = q0
    иначе если len(q) = len(p) + 1:
        присвоить link(last) = q
    иначе:
        определить cl = new_state()
        присвоить len(cl) = len(p) + 1
        присвоить δ(cl) = δ(q), link(cl) = link(q)
        присвоить link(last) = link(q) = cl
        пока δ(p, x) = q:
            присвоить δ(p, x) = cl, p = link(p)

Здесь $q_{0}$ — начальное состояние автомата, $new\_state()$ — функция, добавляющая в автомат новое состояние. Предполагается, что $last$, $len$, $link$ и $\delta$ хранятся в виде глобальных переменных.

Вычислительная сложность

В зависимости от используемых структур, детерминированная версия описанного выше алгоритма может быть реализована за время $O(n\log |\Sigma |)$ с $O(n)$ памяти или за время $O(n)$ с $O(n|\Sigma |)$ памяти, если считать, что выделение памяти происходит за $O(1)$. При этом для получения такой оценки времени работы необходимо провести амортизационный анализ внутренних циклов алгоритма. Если рассмотреть, как меняется параметр $len(p)$ после первой итерации первого цикла, то можно увидеть, что с каждой итерацией цикла он строго уменьшается. При этом если на последней итерации предыдущего шага эта величина была равна $k$, то на второй итерации на следующем шаге эта величина будет равна $k+1$. То, что $len(p)$ ни в какой момент времени не превосходит $n$ и что между циклами эта величина увеличивается только на единицу, даёт требуемое утверждение. Аналогичным анализом может быть показана линейность суммарного времени исполнения второго цикла алгоритма.

Вариации и обобщения

Суффиксный автомат тесно связан с другими суффиксными структурами и индексами подстрок. Имея суффиксный автомат некоторой строки, возможно сжатием и рекурсивным обходом данного автомата построить суффиксное дерево этой строки за линейное время. Аналогичные преобразования в обе стороны возможны между суффиксным автоматом строки $S$ и суффиксным деревом обращённой строки $S^{R}$. Помимо этого был разработан ряд модификаций алгоритма, позволяющих строить автомат для множества строк, заданных префиксным деревом, применять к нему сжатие, поддерживать его структуру в режиме скользящего окна, а также перестраивать при добавлении символов как с конца, так и с начала строки.

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

Как было сказано выше, сжатый суффиксный автомат может быть получен из обычного суффиксного автомата сжатием (удалением состояний, которые не являются финальными и из которых ведёт ровно один переход), а также минимизацией суффиксного дерева, если считать, что алфавит образуют слова, записанные на рёбрах дерева. Кроме того, состояния сжатого автомата могут быть описаны явно, аналогично тому, как это было сделано для несжатого автомата. Двусторонним расширением ${\overset {\scriptstyle {\longleftrightarrow }}{\gamma }}$ слова $\gamma$ называют самое длинное слово $\omega =\beta \gamma \alpha$, такое что любому вхождение $\gamma$ в $S$ предшествует слово $\beta$, а сразу за ним следует слово $\alpha$. В терминах левых и правых расширений это значит, что двустороннее расширение является левым расширением от правого расширения или, что эквивалентно, правым расширением от левого расширения: ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\gamma }}={\overset {\scriptstyle \leftarrow }{\overset {\rightarrow }{\gamma }}}={\overset {\rightarrow }{\overset {\scriptstyle \leftarrow }{\gamma }}}}$. В терминах двусторонних расширений сжатый суффиксный автомат можно описать следующим образом:

Сжатый суффиксный автомат слова $S$ может быть задан парой $(V,E)$, где:

• $V=\{{\overleftrightarrow {\omega }}:\omega \in \Sigma ^{*}\}$ — множество состояний автомата;
• $E=\{({\overleftrightarrow {\omega }},x\alpha ,{\overleftrightarrow {\omega x}}):x\in \Sigma ,\alpha \in \Sigma ^{*},{\overleftrightarrow {\omega x}}={\overleftrightarrow {\omega }}x\alpha \}$ — множество переходов автомата.

Двусторонние расширения порождают отношение эквивалентности ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\alpha }}={\overset {\scriptstyle \longleftrightarrow }{\beta }}}$, описывающее слова, принимаемые одним и тем же состоянием сжатого автомата. Это отношение является транзитивным замыканием отношения ${\textstyle ({\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}})\vee ({\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }})}$, что подчёркивает тот факт, что состояния сжатого суффиксного автомата могут быть получены как склеиванием вершин суффиксного дерева, эквивалентных по ${\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }}$ (минимизация суффиксного дерева), так и склеиванием состояний суффиксного автомата, эквивалентных по ${\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}$ (сжатие суффиксного автомата). Если у слов $\alpha$ и $\beta$ совпадают правые расширения, а у слов $\beta$ и $\gamma$ — левые, то в совокупности у слов $\alpha$, $\beta$ и $\gamma$ совпадает двустороннее расширение. При этом может оказаться, что у слов $\alpha$ и $\gamma$ не совпадают ни левые, ни правые расширения. В случае $S=\beta =ab$, $\alpha =a$ и $\gamma =b$ левые и правые расширения таковы: ${\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}=ab={\overset {\scriptstyle {\leftarrow }}{\beta }}={\overset {\scriptstyle {\leftarrow }}{\gamma }}$, но ${\overset {\scriptstyle {\rightarrow }}{\gamma \,}}=b$ и ${\overset {\scriptstyle {\leftarrow }}{\alpha }}=a$. В случае односторонних контекстов и расширений слова из одного и того же класса эквивалентности образовывали непрерывную цепочку вложенных друг в друга префиксов или суффиксов и могли быть однозначно определены длинами самого короткого и самого длинного слов в классе. В случае же двусторонних расширений наверняка можно сказать только то, что слова из одного и того же класса являются подсловами самого длинного слова из этого класса, а в остальном классы могут иметь достаточно сложную структуру. Общее число таких классов эквивалентности не превосходит $n+1$, из чего следует, что у сжатого суффиксного автомата строки длины $n$ будет не больше $n+1$ состояний. Количество переходов в таком автомате не превосходит $2n-2$.

Суффиксный автомат для набора строк

Пусть задан набор слов $T=\{S_{1},S_{2},\dots ,S_{k}\}$. Аналогично автомату, построенному по единственному слову $S$ можно рассмотреть обобщённый суффиксный автомат, который принимает язык слов, являющихся суффиксом хотя бы одного слова из $T$. При этом для числа состояний и переходов данного автомата будут выполняться все те же ограничения, которые были указаны выше, если положить $n=|S_{1}|+|S_{2}|+\dots +|S_{k}|$. Сам алгоритм построения по своей сути похож на алгоритм построения автомата для одной строки, но вместо указателя $last$ на состояние соответствующее слову $\omega$ при переходе к слову $\omega x$ функция add_letter будет принимать указатель на состояние, принимающее слово $\omega _{i}$, подразумевая, что переход происходит от текущего набора слов $\{\omega _{1},\dots ,\omega _{i},\dots ,\omega _{k}\}$ к набору $\{\omega _{1},\dots ,\omega _{i}x,\dots ,\omega _{k}\}$. Помимо основных действий, которые уже заложены в алгоритм нужно будет отдельно разобрать случай когда строка $\omega _{i}x$ уже присутствует в автомате — в таком случае, возможно, придётся расщепить состояние, которое её принимает, аналогично тому, как это происходило при формировании суффиксной ссылки в алгоритме для единичного слова.

Дальнейшим развитием этой идеи стало построение суффиксного автомата для случая когда набор $T$ задан не в явном виде, а префиксным деревом на $Q$ вершинах. Мохри и другие показали, что такой автомат содержит не более $2Q-2$ состояний и может быть построен за линейное от своего размера время. При этом количество переходов в таком автомате может достигать $O(Q|\Sigma |)$ — например, если рассмотреть множество слов $T=\{\sigma _{1},a\sigma _{1},a^{2}\sigma _{1},\dots ,a^{n}\sigma _{1},a^{n}\sigma _{2},\dots ,a^{n}\sigma _{k}\}$ над алфавитом $\Sigma =\{a,\sigma _{1},\dots ,\sigma _{k}\}$, то суммарная длина слов из этого множества будет порядка ${\textstyle O(n^{2}+nk)}$, число вершин в соответствующем префиксном дереве будет равна $O(n+k)$, а в суффиксном автомате будет порядка $O(n+k)$ состояний и $O(nk)$ переходов. Сам алгоритм, предложенный Мохри, во многом повторяет общий алгоритм построения автомата по набору строк, но вместо того, чтобы каждый раз дописывать символы слова из набора от начала до конца, алгоритм обходит префиксное дерево в порядке обхода в ширину и приписывает очередные символы в том порядке, в котором встречает их при обходе, что гарантирует амортизированно линейное время работы алгоритма.

Скользящее окно

В некоторых алгоритмах сжатия, таких как LZ77 и RLE может быть полезным хранить суффиксный автомат или подобную структуру не для всего считанного слова, а только для $k$ последних символов. В первую очередь, такая необходимость всплывает из-за специфики задач сжатия данных, где сжимаемые строки обычно достаточно велики и использование $O(n)$ памяти нежелательно. В 1985 году Джанет Блумер разработала алгоритм, поддерживающий суффиксный автомат на скользящем окне размера $k$ и работающий за $O(nk)$ в худшем случае и $O(n\log k)$ в среднем, в предположении, что символы в сжимаемом слове распределены независимо и равномерно. В той же работе было показано, что оценка $O(nk)$ является неулучшаемой — если рассмотреть слова, полученные конкатенацией нескольких слов вида $(ab)^{m}c(ab)^{m}d$, где $k=6m+2$, то число состояний автомата, который соответствует подсловам длины $k$ чередовалось бы с резкими прыжками порядка $m$ по величине, что делает существование даже теоретического алгоритма, улучшающего оценку в $O(nk)$ для суффиксного автомата невозможным.

Казалось бы, то же самое должно быть верно и для суффиксного дерева, так как вершины суффиксного дерева соответствуют состояниям суффиксного автомата развёрнутой строки. Однако, если в суффиксном дереве не выделять отдельную вершину для каждого суффикса, то таких резких скачков уже не будет и построение амортизированного алгоритма, поддерживающего суффиксное дерево на скользящем окне возможно. Соответствующий алгоритм для суффиксного дерева, основанный на алгоритме Маккрейта и поддерживающий добавление нового символа справа и удаление символа слева, был предложен в 1989 году Эдвардом Фиала и Дэниелом Грином, а в 1996 году изложен в терминах алгоритма Укконена Джеспером Ларссоном. В связи с этим долгое время оставался открытым вопрос о том, возможно ли поддержание быстрого скользящего окна для сжатого автомата, который объединяет в себе некоторые свойства как обычного суффиксного автомата, так и суффиксного дерева. Отрицательный ответ на этот вопрос был получен в 2008 Мартином Сенфтом и Томашем Двораком, показавшим, что если алфавит состоит из двух и более символов, то амортизированное время, требуемое для сдвига окна на один символ в худшем случае имеет порядок $O(k)$.

В то же время, если точная ширина окна не важна и задача заключается лишь в том, чтобы поддерживать окно, чья ширина по порядку величины не превосходит $O(k)$, это можно сделать приближённым алгоритмом, предложенным Иненагой и другими в 2004 году. Особенностью алгоритма является то, что «окно», которое двигается по слову, имеет переменную длину, которая при этом в любой момент не меньше $k$ и не больше $2k+1$, при этом суммарное время работы остаётся линейным.

Применения

Суффиксный автомат строки $S$ может использоваться для решения таких задач, как:

• Подсчёт количества различных подстрок $S$ за время $O(|S|)$ в режиме онлайн,
• Поиск самой длинной подстроки $S$, которая входит в неё хотя бы два раза, за время $O(|S|)$,
• Поиск наибольшей общей подстроки строк $S$ и $T$ за время $O(|T|)$,
• Подсчёт числа вхождений строки $T$ в $S$ в качестве подстроки за время $O(|T|)$,
• Поиск всех вхождений $T$ в $S$ за время $O(|T|+k)$, где $k$ — количество вхождений.

Здесь стоит считать, что некоторая строка $T$ подаётся на вход, когда автомат уже построен и готов к использованию.

Суффиксные автоматы также нашли своё применение в таких прикладных задачах, как сжатие данных, идентификация музыки по записанным фрагментам и сопоставление геномных последовательностей.

Ссылки

• Суффиксный автомат. Построение за O(N) и применения  (неопр.). MAXimal.
• Суффиксный автомат  (неопр.). Викиконспекты ИТМО.