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

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

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

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

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

История

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

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

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

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

Обозначения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размер

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

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

Построение

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

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

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

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

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

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

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

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

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

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

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

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

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

Построение суффиксного автомата для слова 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.

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

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

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

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

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

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

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

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

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

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

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

• ${\displaystyle V=\{{\overleftrightarrow {\omega }}:\omega \in \Sigma ^{*}\}}$ — множество состояний автомата;
• ${\displaystyle 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 }})}$, что подчёркивает тот факт, что состояния сжатого суффиксного автомата могут быть получены как склеиванием вершин суффиксного дерева, эквивалентных по ${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }}}$ (минимизация суффиксного дерева), так и склеиванием состояний суффиксного автомата, эквивалентных по ${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}}$ (сжатие суффиксного автомата)[25]. Если у слов ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ совпадают правые расширения, а у слов ${\displaystyle \beta }$ и ${\displaystyle \gamma }$ — левые, то в совокупности у слов ${\displaystyle \alpha }$, ${\displaystyle \beta }$ и ${\displaystyle \gamma }$ совпадает двустороннее расширение. При этом может оказаться, что у слов ${\displaystyle \alpha }$ и ${\displaystyle \gamma }$ не совпадают ни левые, ни правые расширения. В случае ${\displaystyle S=\beta =ab}$, ${\displaystyle \alpha =a}$ и ${\displaystyle \gamma =b}$ левые и правые расширения таковы: ${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}=ab={\overset {\scriptstyle {\leftarrow }}{\beta }}={\overset {\scriptstyle {\leftarrow }}{\gamma }}}$, но ${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\gamma \,}}=b}$ и ${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}=a}$. В случае односторонних контекстов и расширений слова из одного и того же класса эквивалентности образовывали непрерывную цепочку вложенных друг в друга префиксов или суффиксов и могли быть однозначно определены длинами самого короткого и самого длинного слов в классе. В случае же двусторонних расширений наверняка можно сказать только то, что слова из одного и того же класса являются подсловами самого длинного слова из этого класса, а в остальном классы могут иметь достаточно сложную структуру. Общее число таких классов эквивалентности не превосходит ${\displaystyle n+1}$, из чего следует, что у сжатого суффиксного автомата строки длины ${\displaystyle n}$ будет не больше ${\displaystyle n+1}$ состояний. Количество переходов в таком автомате не превосходит ${\displaystyle 2n-2}$[18].

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

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

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

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

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

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

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

Применения

Суффиксный автомат строки ${\displaystyle S}$ может использоваться для решения таких задач, как[35][36]:

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

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

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

Примечания

1. Weiner, 1973
2. Pratt, 1973
3. Slisenko, 1983
4. Blumer et al., 1984, p. 109—110
5. Chen, Seiferas, 1985, p. 97
6. Blumer et al., 1987, p. 578
7. Crochemore, Vérin, 1997, p. 192
8. Inenaga et al., 2005, pp. 156—158
9. Inenaga et al., 2001, p. 1
10. Perrin, 1990, p. 10
11. Sgarbas et al., 2003, p. 2
12. Crochemore, Hancart, 1997, pp. 3—6
13. Серебряков и др., 2006, с. 50—54
14. Рубцов, 2019, с. 89—94
15. Hopcroft, Ullman, 1979, pp. 65—68
16. Blumer et al., 1984, pp. 111—114
17. Crochemore, Hancart, 1997, pp. 27—31
18. Inenaga et al., 2005, pp. 159—162
19. Rubinchik, Shur, 2018, pp. 1—2
20. Fujishige et al., 2016, pp. 1—3
21. Crochemore, Hancart, 1997, pp. 31—36
22. Паращенко, 2007, с. 19—22
23. Blumer, 1987, p. 451
24. Inenaga, 2003, p. 1
25. Blumer et al., 1987, pp. 585—588
26. Blumer et al., 1987, pp. 588—589
27. Blumer et al., 1987, p. 593
28. Mohri et al., 2009, pp. 3558—3560
29. Blumer, 1987, pp. 461—465
30. Fiala, Greene, 1989, p. 490
31. Larsson, 1996
32. Brodnik, Jekovec, 2018, p. 1
33. Senft, Dvořák, 2008, p. 109
34. Inenaga et al., 2004
35. Crochemore, Hancart, 1997, pp. 39—41
36. Crochemore, Hancart, 1997, pp. 36—39
37. Yamamoto et al., 2014, p. 675
38. Crochemore et al., 2003, p. 211
39. Mohri et al., 2009, p. 3553
40. Faro, 2016, p. 145

Литература

• Sgarbas K. N., Fakotakis N. D., Kokkinakis G. K. Optimal insertion in deterministic DAWGs (англ.) // Theoretical Computer Science — Elsevier BV, 2003. — Vol. 301, Iss. 1-3. — P. 103—117. — ISSN 0304-3975; 1879-2294 — doi:10.1016/S0304-3975(02)00571-6
• Perrin D. Finite Automata (англ.) // Formal Models and Semantics: Handbook of Theoretical Computer Science / J. v. Leeuwen — Elsevier BV, 1990. — Vol. B. — P. 1—57. — ISBN 978-0-444-88074-1 — doi:10.1016/B978-0-444-88074-1.50006-8
• Weiner P. Linear pattern matching algorithms (англ.) // Symposium on Foundations of Computer Science — 1973. — P. 1—11. — 213 p. — doi:10.1109/SWAT.1973.13
• Pratt V. R. Improvements and applications for the Weiner repetition finder (англ.) — 1973.
• Slisenko A. O. Detection of periodicities and string-matching in real time (англ.) // Journal of Soviet mathematics — Springer Science+Business Media, 1983. — Vol. 22, Iss. 3. — P. 1316—1387. — ISSN 1072-3374; 1573-8795 — doi:10.1007/BF01084395
• Blumer A. C., Blumer J., Ehrenfeucht A., Haussler D., McConnell R. Building the minimal DFA for the set of all subwords of a word on-line in linear time (англ.) // Automata, Languages and Programming — 1984. — P. 109—118. — 526 p. — ISBN 978-3-540-13345-2 — doi:10.1007/3-540-13345-3_9
• Blumer A. C., Blumer J., Ehrenfeucht A., Haussler D., McConnell R. Complete inverted files for efficient text retrieval and analysis (англ.) // Journal of the ACM / D. J. Rosenkrantz — New York City: Association for Computing Machinery, 1987. — Vol. 34, Iss. 3. — P. 578—595. — ISSN 0004-5411 — doi:10.1145/28869.28873
• Blumer J. How much is that DAWG in the window? A moving window algorithm for the directed acyclic word graph (англ.) // Journal of Algorithms — Academic Press, 1987. — Vol. 8, Iss. 4. — P. 451—469. — ISSN 0196-6774; 1090-2678 — doi:10.1016/0196-6774(87)90045-9
• Chen M., Seiferas J. Efficient and Elegant Subword-Tree Construction (англ.) // (unknown type) / A. Apostolico, Z. Galil — Springer Berlin Heidelberg, 1985. — P. 97—107. — ISBN 978-3-642-82456-2 — doi:10.1007/978-3-642-82456-2_7
• Inenaga S. Bidirectional Construction of Suffix Trees (англ.) // Nordic Journal of Computing — 2003. — Vol. 10, Iss. 1. — P. 52—67. — ISSN 1236-6064
• Inenaga S., Hoshino H., Shinohara A., Takeda M., Arikawa S., Mauri G., Pavesi G. On-line construction of compact directed acyclic word graphs (англ.) // Discrete Applied Mathematics — Elsevier BV, 2005. — Vol. 146, Iss. 2. — P. 156—179. — ISSN 0166-218X; 1872-6771 — doi:10.1016/J.DAM.2004.04.012
• Inenaga S., Hoshino H., Shinohara A., Takeda M., Arikawa S. Construction of the CDAWG for a trie (англ.) // Prague Stringology Conference — Czech Technical University in Prague: 2001. — P. 37—48.
• Inenaga S., Shinohara A., Takeda M., Arikawa S. Compact directed acyclic word graphs for a sliding window (англ.) // Journal of Discrete Algorithms — Elsevier BV, 2004. — Vol. 2, Iss. 1. — P. 33—51. — ISSN 1570-8667; 1570-8675 — doi:10.1016/S1570-8667(03)00064-9
• Yamamoto J., I T., Bannai H., Inenaga S., Takeda M. Faster Compact On-Line Lempel-Ziv Factorization (англ.) // Symposium on Theoretical Aspects of Computer Science / E. Mayr, N. Portier — 2014. — Vol. 25. — P. 675—686. — ISBN 978-3-939897-65-1 — ISSN 1868-8969 — doi:10.4230/LIPICS.STACS.2014.675
• Fujishige Y., Tsujimaru Y., Inenaga S., Bannai H., Takeda M. Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets (англ.) // Mathematical Foundations of Computer Science / P. Faliszewski, A. Muscholl, R. Niedermeier — 2016. — Vol. 58. — P. 38:1–38:14. — ISBN 978-3-95977-016-3 — ISSN 1868-8969 — doi:10.4230/LIPICS.MFCS.2016.38
• Mohri M., Moreno P., Weinstein E. General suffix automaton construction algorithm and space bounds (англ.) // Theoretical Computer Science — Elsevier BV, 2009. — Vol. 410, Iss. 37. — P. 3553—3562. — ISSN 0304-3975; 1879-2294 — doi:10.1016/J.TCS.2009.03.034
• Faro S. Evaluation and Improvement of Fast Algorithms for Exact Matching on Genome Sequences (англ.) // Algorithms for Computational Biology / M. Botón-Fernández, C. M. Vide, M. A. Vega-Rodríguez — Springer Nature Switzerland AG, 2016. — P. 145—157. — ISBN 978-3-319-38827-4 — doi:10.1007/978-3-319-38827-4_12
• Crochemore M., Hancart C. Automata for Matching Patterns (англ.) // (unknown type) / G. Rozenberg, A. Salomaa — Springer Berlin Heidelberg, 1997. — Vol. 2. — P. 399—462. — ISBN 978-3-642-59136-5 — doi:10.1007/978-3-662-07675-0_9
• Crochemore M., Vérin R. On compact directed acyclic word graphs (англ.) // Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht / J. Mycielski, G. Rozenberg, A. Salomaa — Springer Berlin Heidelberg, 1997. — P. 192—211. — ISBN 978-3-540-69242-3 — doi:10.1007/3-540-63246-8_12
• Crochemore M., Iliopoulos C. S., Navarro G., Pinzon Y. J. A Bit-Parallel Suffix Automaton Approach for (δ,γ)-Matching in Music Retrieval (англ.) // String Processing and Information Retrieval / M. A. Nascimento, E. S. de Moura, A. L. Oliveira — Springer Berlin Heidelberg, 2003. — P. 211—223. — ISBN 978-3-540-39984-1 — doi:10.1007/978-3-540-39984-1_16
• Hopcroft J. E., Ullman J. D. Introduction to Automata Theory, Languages, and Computation (англ.) — 1 — Massachusetts: Addison-Wesley, 1979. — 418 p. — ISBN 978-81-7808-347-6
• Fiala E. R., Greene D. H. Data compression with finite windows (англ.) // Communications of the ACM — New York City: Association for Computing Machinery, 1989. — Vol. 32, Iss. 4. — P. 490—505. — ISSN 0001-0782; 1557-7317 — doi:10.1145/63334.63341
• Senft M., Dvořák T. Sliding CDAWG Perfection (англ.) // String Processing and Information Retrieval / A. Turpin, A. Moffat, A. Amir — Springer Berlin Heidelberg, 2008. — P. 109—120. — ISBN 978-3-540-89097-3 — doi:10.1007/978-3-540-89097-3_12
• Larsson N. J. Extended application of suffix trees to data compression (англ.) // Proceedings. Data Compression Conference — IEEE, 1996. — P. 190—199. — ISBN 0-8186-7358-3 — ISSN 2375-0383; 2375-0391; 1068-0314; 2375-0359 — doi:10.1109/DCC.1996.488324
• Brodnik A., Jekovec M. Sliding Suffix Tree (англ.) // Algorithms — MDPI, 2018. — Vol. 11, Iss. 8. — P. 118. — ISSN 1999-4893 — doi:10.3390/A11080118
• Rubinchik M., Shur A. M. Eertree (англ.): An efficient data structure for processing palindromes in strings // European Journal of Combinatorics / P. O. de Mendez, P. Rosenstiehl, É. C. de Verdière, A. Björner, F. Brenti, A. Brouwer, P. Cameron, R. Cordovil, D. Foata, P. Frankl et al. — Elsevier BV, 2018. — Vol. 68. — P. 249—265. — ISSN 0195-6698; 1095-9971 — doi:10.1016/J.EJC.2017.07.021 — arXiv:1506.04862
• Серебряков В. А., Галочкин М. П., Фуругян М. Г., Гончар Д. Р. Теория и реализация языков программирования: Учебное пособие — М.: МЗ Пресс, 2006. — 352 с. — ISBN 5-94073-094-9
• Рубцов А. А. Заметки и задачи о регулярных языках и конечных автоматах — М.: МФТИ, 2019. — 112 с. — ISBN 978-5-7417-0702-9
• Паращенко Д. А. Обработка строк на основе суффиксных автоматов — СПб.: ИТМО, 2007. — 35 с.

Ссылки

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