Суффикс-автомат

Суффикс-автомат
Тип	Индекс подстроки
Изобрел	1983 г.
Изобретенный	Ансельм Блумер; Джанет Блумер; Анджей Эренфойхт ; Дэвид Хаусслер ; Росс МакКоннелл
Сложность времени в большой нотации O
Алгоритм Средний Худший случай Космос ${\ Displaystyle О (п)}$ ${\ Displaystyle О (п)}$

В информатике , А суффикс автомат является эффективной структурой данных для представления подстроки индекса из заданной строки , который позволяет хранение, обработке и извлечению сжатой информации о все ее подстроках . Суффиксный автомат строки - это наименьший ориентированный ациклический граф с выделенной начальной вершиной и набором «конечных» вершин, так что пути от начальной вершины к конечным вершинам представляют суффиксы строки. Формально суффиксный автомат определяется следующим набором свойств:${\ displaystyle S}$

1. Его дуги помечены буквами ;
2. ни один из его узлов не имеет двух исходящих дуг, помеченных одной и той же буквой;
3. для каждого суффикса существует такой путь от начальной вершины до некоторой конечной вершины, что конкатенация букв на пути образует этот суффикс;${\ displaystyle S}$
4. у него наименьшее количество вершин среди всех графов, определенных указанными выше свойствами.

В терминах теории автоматов суффиксный автомат - это минимальный частичный детерминированный конечный автомат, который распознает набор суффиксов данной строки . Граф состояний из автомата суффиксом называется ориентированный ациклический граф слов (DAWG), термин , который также иногда используется для любого детерминированного ациклического конечного автомата .${\ displaystyle S = s_ {1} s_ {2} \ dots s_ {n}}$

Суффикс-автоматы были представлены в 1983 году группой ученых из Университета Денвера и Университета Колорадо в Боулдере . Они предложили онлайн-алгоритм линейного времени для его построения и показали, что суффиксный автомат строки длиной не менее двух символов имеет не более состояний и не более переходов. Дальнейшие работы показали тесную связь между суффиксными автоматами и суффиксными деревьями и обрисовали в общих чертах несколько обобщений суффиксных автоматов, таких как сжатый суффиксный автомат, полученный сжатием узлов с одной исходящей дугой.${\ displaystyle S}$${\ textstyle 2 | S | -1}$${\ textstyle 3 | S | -4}$

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

История [ править ]

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

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

Определения [ править ]

Обычно , когда речь идет о суффиксе автоматах и связанных с ними понятия, некоторые понятия из теории формальных языков и теории автоматов используются, в частности: ^[9]

• «Алфавит» - это конечный набор, который используется для построения слов. Его элементы называются «персонажами»;${\ 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}$

Структура автомата [ править ]

Формально детерминированный конечный автомат определяется 5-кортежем , где: ^[10]${\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}$- это частичная функция «перехода» автомата, такая, что for и либо не определено, либо определяет переход от более символа .${\displaystyle \delta (q,\sigma )}$${\displaystyle q\in Q}$${\displaystyle \sigma \in \Sigma }$${\displaystyle q}$${\displaystyle \sigma }$

Чаще всего детерминированный конечный автомат представляется в виде ориентированного графа («диаграммы»), такого что: ^[10]

• Набор вершин графа соответствует состоянию состояний ,${\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}}$

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

Состояния автоматов [ править ]

«Правильный контекст» слова по отношению к языку - это набор, который представляет собой набор слов , соединение которых с ними образует слово из . Правые контексты индуцируют естественное отношение эквивалентности на множестве всех слов. Если язык распознается некоторым детерминированным конечным автоматом, существует единственный с точностью до изоморфизма автомат, распознающий тот же язык и имеющий минимально возможное количество состояний. Такой автомат называется минимальным автоматом для данного языка . Теорема Майхилла – Нероде позволяет ему явно определить его в терминах правых контекстов: ^{[11] [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}$

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

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

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

• Если и имеют хотя бы один общий элемент , то и имеют общий элемент. Подразумевается, что это суффикс и, следовательно, и . В вышеупомянутом примере, so является суффиксом и, следовательно, и ;${\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\}}$
• Если и является суффиксом такого that , то . В приведенном выше примере и для «промежуточного» суффикса это .${\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\}}$

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

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

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

В этом смысле можно сказать, что он распознает точно все суффиксы, которые длиннее и не длиннее чем . Также имеет место: ^[15]${\displaystyle q=[\alpha ]_{R}}$${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}}$${\displaystyle len(link(q))}$${\displaystyle len(q)}$

Связь с суффиксными деревьями [ править ]

« Префиксное дерево » (или « дерево ») - это ориентированное корневое дерево, в котором дуги помечены символами таким образом, что ни одна вершина такого дерева не имеет двух выходящих дуг, отмеченных одним и тем же символом. Некоторые вершины в trie помечаются как конечные. Говорят, что Trie распознает набор слов, определяемых путями от его корня до конечных вершин. Таким образом, префиксные деревья представляют собой особый вид детерминированных конечных автоматов, если вы воспринимаете их корень как начальную вершину. ^[16] «Суффиксное дерево » слова - это префиксное дерево, распознающее набор его суффиксов. « Суффиксное дерево » - это дерево, полученное из суффиксного дерева с помощью процедуры сжатия,при котором последующие ребра объединяются, если степень вершины между ними равна двум.${\displaystyle v}$${\displaystyle S}$^[15]

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

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

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

Как и в случае левых расширений, для правых расширений верна следующая лемма: ^[15]

Размер [ править ]

Суффиксный автомат строки длины имеет не больше состояний и не больше переходов. Эти границы достигаются на строках и соответственно. ^[13] Это можно сформулировать более строго как где и - номера переходов и состояний в автомате соответственно. ^[14]${\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}$${\displaystyle |\delta |\leq |Q|+n-2}$${\displaystyle |\delta |}$${\displaystyle |Q|}$

Строительство [ править ]

Первоначально автомат состоит только из одного состояния, соответствующего пустому слову, затем символы строки добавляются один за другим и автомат перестраивается на каждом шаге постепенно. ^[19]

Обновления состояния [ править ]

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

После добавления к текущему слову правый контекст может существенно измениться, только если это суффикс . Это означает , отношение эквивалентности является уточнение о . Другими словами, если , то . После добавления нового символа будет разделено не более двух классов эквивалентности , и каждый из них может разделиться не более чем на два новых класса. Во-первых, класс эквивалентности, соответствующий пустому правому контексту, всегда разделяется на два класса эквивалентности, один из которых соответствует самому себе и имеет в качестве правого контекста. Этот новый класс эквивалентности содержит точно и все его суффиксы, которые не встречались в${\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 \equiv _{R_{\omega }}}$${\displaystyle \omega x}$${\displaystyle \{\varepsilon \}}$${\displaystyle \omega x}$${\displaystyle \omega }$, поскольку правый контекст таких слов раньше был пуст, а теперь содержит только пустое слово. ^[14]

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

Это означает, что если (например, когда не встречается вообще и ), то разделяется только класс эквивалентности, соответствующий пустому правому контексту. ^[14]${\displaystyle \alpha =\beta }$${\displaystyle x}$${\displaystyle \omega }$${\displaystyle \alpha =\beta =\varepsilon }$

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

Обновления переходов и суффиксных ссылок [ править ]

После добавления символа к возможным новым состояниям автомата суффикса относятся и . Суффиксная ссылка от идет к и от нее идет . Слова from встречаются только как его суффиксы, поэтому не должно быть вообще никаких переходов из while, переходы к нему должны идти от суффиксов, имеющих как минимум длину, и быть отмеченными символом . Состояние формируется подмножеством , поэтому переходы из должны быть такими же, как из . Между тем, переходы, ведущие к, должны начинаться с суффиксов , длина которых меньше и не меньше${\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 \omega }$${\displaystyle \alpha }$${\displaystyle x}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle [\alpha ]_{R_{\omega }}}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle [\alpha ]_{R_{\omega }}}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle \omega }$${\displaystyle |\alpha |}$${\displaystyle len(link([\alpha ]_{R_{\omega }}))}$, поскольку такие переходы привели к предыдущему и соответствовали отделенной части этого состояния. Состояния, соответствующие этим суффиксам, могут быть определены путем обхода пути ссылки суффикса для . ^[19]${\displaystyle [\alpha ]_{R_{\omega }}}$${\displaystyle [\omega ]_{R_{\omega }}}$

Алгоритм строительства [ править ]

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

1. Состояние, соответствующее слову , сохраняется как ;${\displaystyle \omega }$${\displaystyle last}$
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. После завершения вышеупомянутого цикла возможны 3 случая:
   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}$
   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. Переходы, которые привели к предыдущим, но соответствуют словам максимальной длины , перенаправляются на . Для этого продолжают проходить суффиксный путь до тех пор, пока не будет найдено состояние, при котором переход by от него не приведет к .${\displaystyle q}$${\displaystyle len(p)+1}$${\displaystyle cl}$${\displaystyle p}$${\displaystyle x}$${\displaystyle q}$

Вся процедура описывается следующим псевдокодом: ^[19]

функция  add_letter (x) : определить  p = last  assign  last = new_state ()  assign  len (last) = len (p) + 1,  пока  δ (p, x) не определено: назначить  δ (p, x) = last, p = link (p)  define  q = δ (p, x)  if  q = last : assign  link (last) = q 0  else if  len (q) = len (p) + 1 : assign  link (last) = q  else : define  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)

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

Сложность [ править ]

Сложность алгоритма может варьироваться в зависимости от базовой структуры, используемой для хранения переходов автомата. Это может быть реализовано с накладными расходами памяти или с накладными расходами памяти, если предполагается, что распределение памяти выполняется в . Чтобы получить такую ​​сложность, необходимо использовать методы амортизированного анализа . Значение строго уменьшается с каждой итерацией цикла, в то время как оно может увеличиваться только на единицу после первой итерации цикла при следующем вызове add_letter . Общая стоимость никогда не превышает${\displaystyle O(n\log |\Sigma |)}$${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle O(n|\Sigma |)}$${\displaystyle O(1)}$${\displaystyle len(p)}$${\displaystyle len(p)}$${\displaystyle n}$и он увеличивается только на единицу между итерациями добавления новых букв, что предполагает, что общая сложность также является не более чем линейной. Аналогично демонстрируется линейность второго цикла. ^[19]

Обобщения [ править ]

Суффиксный автомат тесно связан с другими суффиксными структурами и индексами подстроки . Имея суффиксный автомат конкретной строки, можно построить ее суффиксное дерево с помощью сжатия и рекурсивного обхода за линейное время. ^[20] Подобные преобразования возможны в обоих направлениях для переключения между суффиксным автоматом и суффиксным деревом перевернутой строки . ^[18] Помимо этого, было разработано несколько обобщений для построения автомата для набора строк, заданных trie, ^[8] сжатым суффиксом автоматизации (CDAWG), ^[7] для поддержания структуры автомата на скользящем окне, ^{[21 ]}${\displaystyle S}$${\displaystyle S^{R}}$и строить его двунаправленным способом, поддерживая вставку символов как в начало, так и в конец строки. ^[22]

Сжатый суффикс-автомат [ править ]

Как уже упоминалось выше, уплотненный суффиксный автомат получается как посредством уплотнения регулярного суффиксного автомата (путем удаления состояний, которые не являются конечными и имеют ровно одну выходящую дугу), так и посредством минимизации суффиксного дерева. Как и в случае обычного суффиксного автомата, состояния уплотненного суффиксного автомата могут быть определены явно. Двустороннее расширение слова - это самое длинное слово , так что каждому вхождению in предшествует и следует за ним . В терминах левого и правого расширений это означает, что двустороннее расширение - это левое расширение правого расширения или, что эквивалентно, правое расширение левого расширения, то есть${\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 }}}}$. В терминах двусторонних расширений компактный автомат определяется следующим образом: ^[15]

Двусторонние расширения индуцируют отношение эквивалентности, которое определяет набор слов, распознаваемых одним и тем же состоянием уплотненного автомата. Это отношение эквивалентности является транзитивным замыканием отношения, определяемого с помощью , которое подчеркивает тот факт, что компактный автомат может быть получен как склейкой вершин суффиксного дерева, эквивалентной через отношение (минимизация суффиксного дерева), так и склейкой состояний суффиксного автомата, эквивалентных через отношение (сжатие суффиксного автомата). ^[23] Если слова и имеют такое же право расширения и слова и имеют одинаковые левые расширения, то кумулятивно все строки , и${\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 \,}}}$${\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}$самой длинной строки с одинаковым двусторонним расширением, но может даже случиться так, что у них нет общей непустой подстроки. Общее количество классов эквивалентности для этого отношения не превосходит, что означает, что сжатый суффиксный автомат строки, имеющей длину, имеет не больше состояний. Количество переходов в таком автомате не больше . ^[15]${\displaystyle n+1}$${\displaystyle n}$${\displaystyle n+1}$${\displaystyle 2n-2}$

Суффиксный автомат из нескольких строк [ править ]

Рассмотрим набор слов . Можно построить обобщение суффиксного автомата, которое распознало бы язык, образованный суффиксами всех слов из набора. Ограничения на количество состояний и переходов в таком автомате останутся такими же, как и для однословного автомата, если вы установите . ^[23] Алгоритм похож на построение однословного автомата, за исключением того, что вместо состояния функция add_letter будет работать с состоянием, соответствующим слову, предполагая переход от набора слов к набору . ^{[24] [25]}${\displaystyle T=\{S_{1},S_{2},\dots ,S_{k}\}}$${\displaystyle n=|S_{1}|+|S_{2}|+\dots +|S_{k}|}$${\displaystyle last}$${\displaystyle \omega _{i}}$${\displaystyle \{\omega _{1},\dots ,\omega _{i},\dots ,\omega _{k}\}}$${\displaystyle \{\omega _{1},\dots ,\omega _{i}x,\dots ,\omega _{k}\}}$

Эта идея далее обобщается на случай, когда не задается явно, а задается префиксным деревом с вершинами. Mohri et al . показал, что такой автомат будет иметь самое большее и может быть построен за линейное время из своего размера. При этом количество переходов в таком автомате может достигать , например, для набора слов по алфавиту общая длина рабочих операций равна , количество вершин в соответствующем суффиксном trie равно, а соответствующий суффиксный автомат равен сформированный из государств и${\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)}$переходы. Алгоритм, предложенный Мохри, в основном повторяет общий алгоритм построения автомата из нескольких строк, но вместо того, чтобы наращивать слова одно за другим, он просматривает дерево в порядке поиска в ширину и добавляет новые символы, когда они встречаются с ними при обходе, что гарантирует амортизацию линейная сложность. ^[26]

Скользящее окно [ править ]

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

То же самое должно быть верно и для суффиксного дерева, потому что его вершины соответствуют состояниям суффиксного автомата перевернутой строки, но эту проблему можно решить, не сохраняя явно каждую вершину, соответствующую суффиксу всей строки, таким образом сохраняя только вершины с at минимум два выходящих края. Вариант алгоритма построения суффиксного дерева МакКрайта для этой задачи был предложен в 1989 году Эдвардом Фиала и Дэниелом Грином; ^[28], спустя несколько лет аналогичный результат был получен с вариацией алгоритма Укконена Джеспером Ларссоном. ^{[29] [30]}Существование такого алгоритма для сжатого суффиксного автомата, который вбирает в себя некоторые свойства как суффиксных деревьев, так и суффиксных автоматов, долгое время оставалось открытым вопросом, пока в 2008 году Мартин Зенфт и Томаш Дворжак не обнаружили, что это невозможно, если размер алфавита не менее двух. ^[31]

Один из способов преодолеть это препятствие - позволить ширине окна немного варьироваться во время пребывания . Этого можно добиться с помощью приблизительного алгоритма, предложенного Inenaga et al. в 2004 году. Не гарантируется, что окно, для которого построен суффиксный автомат в этом алгоритме, будет иметь длину, но гарантированно будет по крайней мере и максимум при обеспечении линейной общей сложности алгоритма. ^[32]${\displaystyle O(k)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle 2k+1}$

Приложения [ править ]

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

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

Здесь предполагается, что на входе после построения суффиксного автомата . ^[33]${\displaystyle T}$${\displaystyle S}$

Суффикс-автоматы также используются при сжатии данных, ^[35] поиске музыки ^{[36] [37]} и сопоставлении последовательностей генома. ^[38]

Ссылки [ править ]

Библиография [ править ]

Внешние ссылки [ править ]

• СМИ, связанные с автоматом суффиксов на Викискладе?
• Статья о суффиксных автоматах по алгоритмам E-Maxx на английском языке