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

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

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

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

История

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

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

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

Обозначения

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

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

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

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

• Σ {displaystyle Sigma } — алфавит, из которого состоят слова, распознаваемые автоматом,
• Q {displaystyle Q} — множество состояний автомата,
• q 0 ∈ Q {displaystyle q_{0}in Q} — начальное состояние автомата,
• F ⊂ Q {displaystyle Fsubset Q} — множество финальных состояний автомата,
• δ : Q × Σ ↦ Q {displaystyle delta :Q imes Sigma mapsto Q} — частично определённая функция переходов автомата, такая что δ ( q , σ ) {displaystyle delta (q,sigma )} для q ∈ Q {displaystyle qin Q} и σ ∈ Σ {displaystyle sigma in Sigma } либо не определена, либо указывает на состояние, в которое может быть произведён переход из q {displaystyle q} по σ {displaystyle sigma } .

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

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

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

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

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

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

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

Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть | α | ≤ | β | {displaystyle |alpha |leq |eta |} , тогда:

• Если у [ α ] R {displaystyle [alpha ]_{R}} и [ β ] R {displaystyle [eta ]_{R}} есть хотя бы один общий элемент x {displaystyle x} , то общий элемент также есть у e n d p o s ( α ) {displaystyle endpos(alpha )} и e n d p o s ( β ) {displaystyle endpos(eta )} . Это, в свою очередь, значит, что α {displaystyle alpha } — суффикс β {displaystyle eta } и потому e n d p o s ( β ) ⊂ e n d p o s ( α ) {displaystyle endpos(eta )subset endpos(alpha )} и [ β ] R ⊂ [ α ] R {displaystyle [eta ]_{R}subset [alpha ]_{R}} . В приведённом выше примере, a ∈ [ a b ] R ∩ [ c a b ] R {displaystyle ain [ab]_{R}cap [cab]_{R}} и, как следствие, a b {displaystyle ab} — суффикс c a b {displaystyle cab} , а также [ c a b ] R = { a } ⊂ { a , a c a b a } = [ a b ] R {displaystyle [cab]_{R}={a}subset {a,acaba}=[ab]_{R}} и e n d p o s ( c a b ) = { 6 } ⊂ { 2 , 6 } = e n d p o s ( a b ) {displaystyle endpos(cab)={6}subset {2,6}=endpos(ab)} ;
• Если [ α ] R = [ β ] R {displaystyle [alpha ]_{R}=[eta ]_{R}} , то e n d p o s ( α ) = e n d p o s ( β ) {displaystyle endpos(alpha )=endpos(eta )} , то есть α {displaystyle alpha } встречается в S {displaystyle S} только в качестве суффикса β {displaystyle eta } . Это видно на примере слов α = b {displaystyle alpha =b} и β = a b {displaystyle eta =ab} , для которых [ b ] R = [ a b ] R = { a , a c a b a } {displaystyle [b]_{R}=[ab]_{R}={a,acaba}} и e n d p o s ( b ) = e n d p o s ( a b ) = { 2 , 6 } {displaystyle endpos(b)=endpos(ab)={2,6}} ;
• Если [ α ] R = [ β ] R {displaystyle [alpha ]_{R}=[eta ]_{R}} и γ {displaystyle gamma } — суффикс β {displaystyle eta } , такой что | α | ≤ | γ | ≤ | β | {displaystyle |alpha |leq |gamma |leq |eta |} , то [ α ] R = [ γ ] R = [ β ] R {displaystyle [alpha ]_{R}=[gamma ]_{R}=[eta ]_{R}} . В приведённом выше примере, [ c ] R = [ b a c ] R = { a b a } {displaystyle [c]_{R}=[bac]_{R}={aba}} , а «промежуточным» суффиксом является γ = a c {displaystyle gamma =ac} . И действительно, [ a c ] R = { a b a } {displaystyle [ac]_{R}={aba}} .

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

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

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

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

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

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

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

Аналогично правым контекстам можно ввести левые контексты [ ω ] L = { β ∈ Σ ∗ : β ω ∈ L } {displaystyle [omega ]_{L}={eta in Sigma ^{*}:eta omega in L}} и правые расширения ω   → {displaystyle {overset {scriptstyle { ightarrow }}{omega ~}}} , соответствующие самым длинным строкам, имеющим заданный левый контекст, а также отношение эквивалентности [ α ] L = [ β ] L {displaystyle [alpha ]_{L}=[eta ]_{L}} . Если рассматривать правые расширения относительно языка L {displaystyle L} префиксов строки S {displaystyle S} , то можно получить, что:

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

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

Размер

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

Построение

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

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

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

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

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

В частности, если α = β {displaystyle alpha =eta } (например, когда x {displaystyle x} вообще не встречается в ω {displaystyle omega } и α = β = ε {displaystyle alpha =eta =varepsilon } ), расщепления второго состояния не происходит.

Помимо суффиксных ссылок, в новом автомате также нужно определить финальные состояния. Из структурных свойств автомата следует, что суффиксы любого слова α {displaystyle alpha } расположены таким образом, что если q = [ α ] R {displaystyle q=[alpha ]_{R}} , то суффиксы α {displaystyle alpha } , чья длина превышает l e n ( l i n k ( q ) ) {displaystyle len(link(q))} , лежат в q {displaystyle q} , суффиксы, чья длина больше l e n ( l i n k ( l i n k ( q ) ) {displaystyle len(link(link(q))} , но не больше l e n ( l i n k ( q ) ) {displaystyle len(link(q))} , лежат в l i n k ( q ) {displaystyle link(q)} и так далее. Иными словами, для любого суффикса α {displaystyle alpha } найдётся вершина в суффиксном пути состояния q {displaystyle q} , который задаётся последовательностью ( q , l i n k ( q ) , l i n k 2 ( q ) , … ) {displaystyle (q,link(q),link^{2}(q),dots )} . Соответственно если обозначить состояние, принимающее в текущий момент всю строку ω {displaystyle omega } , как l a s t {displaystyle last} , то терминальными (принимающими суффиксы ω {displaystyle omega } ) состояниями будут те и только те состояния, которые входят в суффиксный путь ( l a s t , l i n k ( l a s t ) , l i n k 2 ( l a s t ) , … ) {displaystyle (last,link(last),link^{2}(last),dots )} .

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

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

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

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

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

Здесь q 0 {displaystyle q_{0}} — начальное состояние автомата, n e w _ s t a t e ( ) {displaystyle new_state()} — функция, добавляющая в автомат новое состояние. Предполагается, что l a s t {displaystyle last} , l e n {displaystyle len} , l i n k {displaystyle link} и δ {displaystyle delta } хранятся в виде глобальных переменных.

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

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

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

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

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

Как было сказано выше, сжатый суффиксный автомат может быть получен из обычного суффиксного автомата сжатием (удалением состояний, которые не являются финальными и из которых ведёт ровно один переход), а также минимизацией суффиксного дерева, если считать, что алфавит образуют слова, записанные на рёбрах дерева. Кроме того, состояния сжатого автомата могут быть описаны явно, аналогично тому, как это было сделано для несжатого автомата. Двусторонним расширением γ ⟷ {displaystyle {overset {scriptstyle {longleftrightarrow }}{gamma }}} слова γ {displaystyle gamma } называют самое длинное слово ω = β γ α {displaystyle omega =eta gamma alpha } , такое что любому вхождение γ {displaystyle gamma } в S {displaystyle S} предшествует слово β {displaystyle eta } , а сразу за ним следует слово α {displaystyle alpha } . В терминах левых и правых расширений это значит, что двустороннее расширение является левым расширением от правого расширения или, что эквивалентно, правым расширением от левого расширения: γ ⟷ = γ → ← = γ ← → { extstyle {overset {scriptstyle longleftrightarrow }{gamma }}={overset {scriptstyle leftarrow }{overset { ightarrow }{gamma }}}={overset { ightarrow }{overset {scriptstyle leftarrow }{gamma }}}} . В терминах двусторонних расширений сжатый суффиксный автомат можно описать следующим образом:

Двусторонние расширения порождают отношение эквивалентности α ⟷ = β ⟷ { extstyle {overset {scriptstyle longleftrightarrow }{alpha }}={overset {scriptstyle longleftrightarrow }{eta }}} , описывающее слова, принимаемые одним и тем же состоянием сжатого автомата. Это отношение является транзитивным замыканием отношения ( α → = β → ) ∨ ( α ← = β ← ) { extstyle ({overset {scriptstyle { ightarrow }}{alpha ,}}={overset {scriptstyle { ightarrow }}{eta ,}})vee ({overset {scriptstyle {leftarrow }}{alpha }}={overset {scriptstyle {leftarrow }}{eta }})} , что подчёркивает тот факт, что состояния сжатого суффиксного автомата могут быть получены как склеиванием вершин суффиксного дерева, эквивалентных по α ← = β ← {displaystyle {overset {scriptstyle {leftarrow }}{alpha }}={overset {scriptstyle {leftarrow }}{eta }}} (минимизация суффиксного дерева), так и склеиванием состояний суффиксного автомата, эквивалентных по α → = β → {displaystyle {overset {scriptstyle { ightarrow }}{alpha ,}}={overset {scriptstyle { ightarrow }}{eta ,}}} (сжатие суффиксного автомата). Если у слов α {displaystyle alpha } и β {displaystyle eta } совпадают правые расширения, а у слов β {displaystyle eta } и γ {displaystyle gamma } — левые, то в совокупности у слов α {displaystyle alpha } , β {displaystyle eta } и γ {displaystyle gamma } совпадает двустороннее расширение. При этом может оказаться, что у слов α {displaystyle alpha } и γ {displaystyle gamma } не совпадают ни левые, ни правые расширения. В случае S = β = a b {displaystyle S=eta =ab} , α = a {displaystyle alpha =a} и γ = b {displaystyle gamma =b} левые и правые расширения таковы: α → = β → = a b = β ← = γ ← {displaystyle {overset {scriptstyle { ightarrow }}{alpha ,}}={overset {scriptstyle { ightarrow }}{eta ,}}=ab={overset {scriptstyle {leftarrow }}{eta }}={overset {scriptstyle {leftarrow }}{gamma }}} , но γ → = b {displaystyle {overset {scriptstyle { ightarrow }}{gamma ,}}=b} и α ← = a {displaystyle {overset {scriptstyle {leftarrow }}{alpha }}=a} . В случае односторонних контекстов и расширений слова из одного и того же класса эквивалентности образовывали непрерывную цепочку вложенных друг в друга префиксов или суффиксов и могли быть однозначно определены длинами самого короткого и самого длинного слов в классе. В случае же двусторонних расширений наверняка можно сказать только то, что слова из одного и того же класса являются подсловами самого длинного слова из этого класса, а в остальном классы могут иметь достаточно сложную структуру. Общее число таких классов эквивалентности не превосходит n + 1 {displaystyle n+1} , из чего следует, что у сжатого суффиксного автомата строки длины n {displaystyle n} будет не больше n + 1 {displaystyle n+1} состояний. Количество переходов в таком автомате не превосходит 2 n − 2 {displaystyle 2n-2} .

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

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

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

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

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

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

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

Применения

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

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

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

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