|
|
| Строка 1: |
Строка 1: |
| {{Структура данных
| |
| | оригинал названия =
| |
| | создатель = Ансельм Блумер, Джанет Блумер, {{iw|Эренфехт, Анджей|Анджей Эренфехт|en|Andrzej Ehrenfeucht}}, {{iw|Хаусслер, Дэвид|Дэвид Хаусслер|en|David Haussler}}, Росс Макконнелл
| |
| | построение худшее = <math>O(\vert S\vert \log \vert\Sigma\vert)</math>
| |
| | память худшая = <math>O(\vert S\vert)</math>
| |
| | изобретён =
| |
| }}
| |
| '''Су́ффиксный автома́т''' ({{lang-en|''suffix automaton'', ''directed acyclic word graph''}}) — [[структура данных]], позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с [[подстрока]]ми данной строки. Представляет собой [[детерминированный конечный автомат]], принимающий все суффиксы [[Строковый тип|слова]] <math>S=s_1 s_2 \dots s_n</math> и только их, и обладающий [[Минимальная форма автомата|наименьшим]] возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это [[ориентированный ациклический граф]] с выделенной начальной вершиной и набором «финальных» вершин, [[Дуга (теория графов)|дуги]] которого помечены [[Символьный тип|символами]], такой что у любой [[Вершина (теория графов)|вершины]] символы на исходящих из неё дугах попарно различны и для любого суффикса слова <math>S</math> существует [[Путь (теория графов)|путь]] из начальной вершины в некоторую финальную вершину, символы на котором при [[Конкатенация|конкатенации]] образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин{{Переход|Структура автомата}}.
| |
|
| |
|
| Суффиксный автомат был впервые описан группой учёных из Денверского и Колорадского университетов в 1983 году, они же показали, что размер автомата [[Линейная функция|линейно]] зависит от длины <math>S</math>, а также предложили {{Не переведено 5|Онлайн-алгоритм|онлайн-алгоритм||Online algorithm}} для его построения с линейным [[Вычислительная сложность|временем работы]]{{Переход|История}}. В дальнейших работах на эту тему была обнаружена тесная связь суффиксного автомата с [[Суффиксное дерево|суффиксными деревьями]]{{Переход|Связь с суффиксным деревом}}, а сама концепция суффиксного автомата получила различные обобщения. Так были введены сжатый суффиксный автомат, получаемый из исходного процедурой, аналогичной той, которая применяется к суффиксному бору для получения суффиксного дерева, а также обобщённый суффиксный автомат, который строится для набора слов <math>S_1, S_2, \dots, S_k</math> и принимает слова, являющиеся суффиксами хотя бы одного из данных{{Переход|Вариации и обобщения}}.
| | '''Су́ффиксный автома́т''' — [[структура данных]], позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с [[подстрока]]ми данной строки. Представляет собой [[детерминированный конечный автомат]], принимающий все суффиксы [[Строковый тип|слова]] <math>S=s_1 s_2 \dots s_n</math> и только их, и обладающий [[Минимальная форма автомата|наименьшим]] возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это [[ориентированный ациклический граф]] с выделенной начальной вершиной и набором «финальных» вершин, [[Дуга (теория графов)|дуги]] которого помечены [[Символьный тип|символами]], такой что у любой [[Вершина (теория графов)|вершины]] символы на исходящих из неё дугах попарно различны и для любого суффикса слова <math>S</math> существует [[Путь (теория графов)|путь]] из начальной вершины в некоторую финальную вершину, символы на котором при [[Конкатенация|конкатенации]] образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин |
|
| |
|
| С помощью суффиксного автомата можно эффективно решать такие задачи как [[Поиск подстроки|поиск подстроки в строке]], определение [[Наибольшая общая подстрока|наибольшей общей подстроки]] двух и более строк и другие{{Переход|Применения}}.
| |
|
| |
| == История ==
| |
| [[Файл:Anselm Blumer with DAWG.jpg|мини|288x288px|Ансельм Блумер, на доске изображён сжатый суффиксный автомат для строк ''ababc'' и ''abcab'']]Концепция суффиксного автомата была представлена группой учёных из [[Денверский университет|Денверского]] и [[Колорадский университет в Боулдере|Колорадского]] университетов Ансельмом Блумером, {{Не переведено 5|Эренфехт, Анджей|Анджеем Эренфехтом||Andrzej Ehrenfeucht}}, {{Не переведено 5|Хаусслер, Дэвид|Дэвидом Хаусслером||David Haussler}}, Россом МакКоннеллом и Джанет Блумер в 1983 году, хотя связанные с ним структуры встречались ранее в работах Питера Вайнера<ref name=":5" />, [[Пратт, Воан|Вона Пратта]]<ref>{{sfn-текст|Pratt|1973}}</ref> и [[Слисенко, Анатолий Олесьевич|Анатолия Олесьевича Слисенко]]<ref>{{sfn-текст|Slisenko|1983}}</ref>, посвящённых алгоритмам построения [[Суффиксное дерево|суффиксных деревьев]]. В той же работе Блумер и другие показали, что построенный по слову <math>S</math> длины больше <math>1</math> автомат содержит не больше <math>2|S|-1</math> состояний и не больше <math>3|S|-4</math> переходов, а также привели линейный алгоритм построения автомата<ref name=":2">{{sfn-текст|Blumer et al.|1984|loc=|p=109—110}}</ref>.
| |
|
| |
| В 1983 году Му Тянь Чэнь и Джоэл Сейферас независимо разработали алгоритм построения суффиксного автомата, показывающий, что алгоритм Вайнера<ref name=":5">{{sfn-текст|Weiner|1973}}</ref>, предложенный в 1973 году для построения [[Суффиксное дерево|суффиксного дерева]] слова <math>S</math>, также строит суффиксный автомат для обращённого слова <math display="inline">S^R</math> в качестве вспомогательной структуры<ref name=":6">{{sfn-текст|Chen, Seiferas|1985|loc=|p=97}}</ref>. В 1987 году Блумер и другие, по аналогии с суффиксным деревом, описали сжатый суффикный автомат<ref name=":7">{{sfn-текст|Blumer et al.|1987|loc=|p=578}}</ref>, получаемый из суффиксного автомата удалением нефинальных состояний с [[Полустепень исхода|полустепенью исхода]], равной единице, а в 1997 году {{Iw|Крошемор, Максим|Максим Крошемор||Maxime Crochemore}} и Рено Верин разработали линейный алгоритм для его прямого построения<ref>{{sfn-текст|Crochemore, Vérin|1997|loc=|p=192}}</ref>. В 2001 году Сюнсукэ Инэнага и другие разработали линейный онлайн-алгоритм для построения сжатого суффиксного автомата<ref name=":0">{{sfn-текст|Inenaga et al.|2005|с=|loc=|pp=156—158}}</ref>, а также линейный алгоритм для построения сжатого суффиксного автомата для набора слов, заданного [[Префиксное дерево|префиксным деревом]]<ref name=":8">{{sfn-текст|Inenaga et al.|2001|loc=|p=1}}</ref>.
| |
|
| |
| В своей исходной работе Блумер с коллегами определили описанную ими структуру как минимальный автомат, распознающий все ''подстроки'' (а не суффиксы) данного слова. Данную структуру они назвали ''ориентированным ациклическим графом слов'' ({{Lang-en|directed acyclic word graph}})<ref name=":2" />. Впоследствии данное название также использовалось как синоним {{Не переведено 5|Детерминированный ациклический конечный автомат|детерминированного ациклического конечного автомата||Deterministic acyclic finite state automaton}} — минимального автомата, распознающего произвольный конечный набор слов (не обязательно составляющих множество суффиксов или подстрок некоторой строки)<ref>{{Sfn0|Perrin|1990|p=10}}</ref><ref>{{Sfn0|Sgarbas et al.|2003|p=2}}</ref>.
| |
|
| |
| == Обозначения ==
| |
| При описании суффиксных автоматов и связанных с ними фактов и теорем часто используются обозначения из теории [[Формальный язык|формальных языков]] в целом и [[Теория автоматов|теории автоматов]] в частности<ref name=":1" />:
| |
|
| |
| * ''[[Алфавит (формальный язык)|Алфавит]]'' — конечное [[множество]] <math>\Sigma</math>, из которого могут состоять слова. Его элементы называются ''символами'';
| |
| * ''[[Слово (формальный язык)|Слово]]'' — конечная последовательность символов алфавита <math>\omega = \omega_1 \omega_2 \dots \omega_n</math>. ''Длина'' слова <math>\omega</math> обозначается как <math>|\omega|=n</math>;
| |
| * ''[[Формальный язык]]'' — некоторое множество слов над заданным алфавитом;
| |
| * ''Язык всех слов'' обозначается как <math>\Sigma^*</math>(здесь символ «*» несёт смысл [[Звезда Клини|звезды Клини]]), ''пустое слово'' (слово нулевой длины) — символом <math>\varepsilon</math>;
| |
| * ''[[Конкатенация]] (произведение) слов'' <math>\alpha = \alpha_1 \alpha_2 \dots \alpha_n</math> и <math>\beta = \beta_1 \beta_2 \dots \beta_m</math> обозначается как <math>\alpha \cdot \beta</math> или <math>\alpha\beta</math> и равна слову, получаемому приписыванием <math>\beta</math> к <math>\alpha</math> справа, то есть, <math>\alpha \beta = \alpha_1 \alpha_2 \dots \alpha_n \beta_1 \beta_2 \dots \beta_m</math>;
| |
| * ''Конкатенация языков'' <math>A</math> и <math>B</math> обозначается как <math>A \cdot B</math> или <math>AB</math> и равна множеству попарных конкатенаций <math>AB = \{\alpha \beta : \alpha \in A, \beta \in B\}</math>;
| |
| * Если слово <math>\omega\in\Sigma^*</math> представимо в виде <math>\omega = \alpha\gamma\beta</math>, где <math>\alpha,\beta,\gamma \in \Sigma^*</math>, то слова <math>\alpha</math>, <math>\beta</math> и <math>\gamma</math> называют ''префиксом'', ''суффиксом'' и ''[[Подстрока|подсловом]]'' (подстрокой) слова <math>\omega</math> соответственно;
| |
| * Если <math>T_l T_{l+1} \dots T_r = S</math>, то говорят, что слово <math>S</math> ''входит (встречается)'' в <math>T</math> как подслово. При этом <math>l</math> и <math>r</math> называются левой и правой позициями вхождения <math>S</math> в <math>T</math> соответственно.
| |
|
| |
| == Структура автомата ==
| |
| Формально, [[детерминированный конечный автомат]] определяется [[Кортеж (информатика)|набором из пяти элементов]] <math>\mathcal A = (\Sigma, Q, q_0, F, \delta)</math>, где:
| |
|
| |
| * <math>\Sigma</math> — ''алфавит'', из которого состоят слова, распознаваемые автоматом,
| |
| * <math>Q</math> — множество ''[[Состояние (информатика)|состояний]]'' автомата,
| |
| * <math>q_0 \in Q</math> — ''начальное'' состояние автомата,
| |
| * <math>F \subset Q</math> — множество ''финальных'' состояний автомата,
| |
| * <math>\delta : Q \times \Sigma \mapsto Q</math> — {{Не переведено 5|Частично определённая функция|частично определённая||Partial function}} функция ''переходов'' автомата, такая что <math>\delta(q, \sigma)</math> для <math>q \in Q</math> и <math>\sigma \in \Sigma</math> либо не определена, либо указывает на состояние, в которое может быть произведён переход из <math>q</math> по <math>\sigma</math>.
| |
|
| |
| Чаще всего на практике конечные автоматы представляются в виде [[Ориентированный граф|ориентированного графа]] (''диаграммы'') такого что<ref>{{sfn-текст|Серебряков и др.|2006|с=50—54|loc=}}</ref>:
| |
|
| |
| * Множество [[Вершина графа|вершин]] графа соответствует множеству состояний <math>Q</math>,
| |
| * В графе выделена некоторая вершина, соответствующая начальному состоянию <math>q_0</math>,
| |
| * В графе выделен набор вершин, соответствующих множеству финальных состояний <math>F</math>,
| |
| * Множество [[Дуга (теория графов)|дуг]] в графе соответствует множеству переходов <math>\delta</math>,
| |
| * При этом переходу <math display="inline">\delta(q_1, \sigma) = q_2</math> соответствует дуга из <math>q_1</math> в <math>q_2</math>, помеченная символом алфавита <math>\sigma</math>. Такой переход также обозначают как <math display="inline">q_1 \begin{smallmatrix}{\sigma}\\[-5pt]{\longrightarrow}\end{smallmatrix} q_2</math>.
| |
|
| |
| В таком графе вершины и дуги отождествляются с состояниями и переходами автомата соответственно. Автомат принимает слово <math>\omega=\omega_1 \omega_2 \dots \omega_m</math> в том и только том случае, если существует путь из начального состояния <math>q_0</math> в некоторое финальное состояние <math>q \in F</math>, такой что если сконкатенировать символы, встретившиеся на этом пути, то получится слово <math>\omega</math>. Множество слов, которые принимает автомат, образуют язык этого автомата<ref name=":1">{{sfn-текст|Crochemore, Hancart|1997|pp=3—6|loc=}}</ref>.
| |
|
| |
| === Состояния автомата ===
| |
| {{Основная статья|Минимизация ДКА}}''Правым контекстом'' слова <math>\omega</math> относительно языка <math>L</math> называют множество <math>[\omega]_R=\{\alpha : \omega\alpha \in L\}</math>. То есть это множество слов <math>\alpha</math>, при приписывании которых к слову <math>\omega</math> справа получается слово из языка <math>L</math>. Правые контексты индуцируют естественное [[отношение эквивалентности]] <math>[\alpha]_R = [\beta]_R</math> на множестве всех слов. Если язык <math>L</math> может быть задан ''некоторым'' детерминированным конечным автоматом, то для него существует единственный, с точностью до [[изоморфизм]]а, автомат, обладающий при этом наименьшим возможным числом состояний. Такой автомат называется [[Минимальная форма автомата|минимальным]] для данного языка <math>L</math>, [[теорема Майхилла — Нероуда]] позволяет задать его в явном виде''<ref>{{Sfn-текст|Рубцов|2019|loc=|страницы=89—94}}</ref>''<ref>{{Sfn-текст|Hopcroft, Ullman|1979|loc=|pp=65—68}}</ref>:{{Теорема|Минимальный автомат, распознающий язык <math>L</math> над алфавитом <math>\Sigma</math>, может быть задан следующим образом:
| |
|
| |
| * Алфавит <math>\Sigma</math> остаётся без изменений,
| |
| * Состояниям <math>Q</math> соответствуют правые контексты <math>[\omega]_R</math> всех слов <math>\omega \in \Sigma^*</math>,
| |
| * Начальному состоянию <math>q_0</math> соответствует правый контекст пустого слова <math>[\varepsilon]_R</math>,
| |
| * Финальным состояниям <math>F</math> соответствуют правые контексты <math>[\omega]_R</math> слов из языка <math>\omega \in L</math>,
| |
| * Переходы <math>\delta</math> имеют вид <math>[\omega]_R \begin{smallmatrix}{\sigma}\\[-5pt]{\longrightarrow}\end{smallmatrix} [\omega\sigma]_R</math>, где <math>\omega \in \Sigma^*</math> и <math>\sigma \in \Sigma</math>.|макс-ширина=100%}}
| |
|
| |
| В таких обозначениях, ''суффиксный автомат'' — это минимальный ДКА, принимающий язык суффиксов слова <math>S=s_1s_2\dots s_n</math>. Правый контекст слова <math>\omega</math> относительно данного языка состоит из слов <math>\alpha</math> таких что <math>\omega \alpha</math> — суффикс <math>S</math>. Это позволяет сформулировать следующую лемму, определяющую [[взаимно-однозначное соответствие]] между правым контекстом слова и множеством позиций его вхождений в <math>S</math> в качестве подслова<ref name=":9" /><ref name=":10">{{Sfn-текст|Crochemore, Hancart|1997|loc=|pp=27—31}}</ref>:
| |
|
| |
| {{Теорема|Пусть <math>endpos(\omega)=\{r: \omega=s_l \dots s_r \}</math> — множество правых позиций вхождений <math>\omega</math> в <math>S</math>.
| |
|
| |
| Между элементами множеств <math>endpos(\omega)</math> и <math>[\omega]_R</math> есть следующее взаимно-однозначное соответствие:
| |
| * Если <math>x \in endpos(\omega)</math>, то <math>s_{x+1}s_{x+2}\dots s_n \in [\omega]_R</math>;
| |
| * Если <math>\alpha \in [\omega]_R</math>, то <math>n-\vert\alpha\vert \in endpos(\omega)</math>.|макс-ширина=100%}}
| |
| Например, для слова <math>S=abacaba</math> и его подслова <math>\omega = ab</math> выполнено <math>endpos(ab)=\{2,6\}</math> и <math>[ab]_R = \{a,acaba\}</math>. Неформально, <math>[ab]_R</math> состоит из слов, которые следуют за вхожениями <math>ab</math> до конца слова, а <math>endpos(ab)</math> — из позиций этих вхождений. В этом примере, элементу <math>x=2 \in endpos(ab)</math> соответствует слово <math>s_3 s_4 s_5 s_6 s_7 = acaba \in [ab]_R</math>. В то же время, слову <math>a \in [ab]_R</math> соответствует элемент <math>7-|a|=6 \in endpos(ab)</math>.
| |
|
| |
| Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть <math>|\alpha| \leq |\beta|</math>, тогда<ref name=":10" />:
| |
|
| |
| * Если у <math>[\alpha]_R</math> и <math>[\beta]_R</math> есть хотя бы один общий элемент <math>x</math>, то общий элемент также есть у <math>endpos(\alpha)</math> и <math>endpos(\beta)</math>. Это, в свою очередь, значит, что <math>\alpha</math> — суффикс <math>\beta</math> и потому <math>endpos(\beta) \subset endpos(\alpha)</math> и <math>[\beta]_R \subset [\alpha]_R</math>. В приведённом выше примере, <math>a \in [ab]_R \cap [cab]_R</math> и, как следствие, <math>ab</math> — суффикс <math>cab</math>, а также <math>[cab]_R=\{a\} \subset \{a,acaba\} = [ab]_R</math> и <math>endpos(cab) = \{6\} \subset \{2,6\} = endpos(ab)</math>;
| |
| * Если <math>[\alpha]_R=[\beta]_R</math>, то <math>endpos(\alpha)=endpos(\beta)</math>, то есть <math>\alpha</math> встречается в <math>S</math> только в качестве суффикса <math>\beta</math>. Это видно на примере слов <math>\alpha=b</math> и <math>\beta = ab</math>, для которых <math>[b]_R = [ab]_R = \{a,acaba\}</math> и <math>endpos(b)=endpos(ab)=\{2,6\}</math>;
| |
| * Если <math>[\alpha]_R=[\beta]_R</math> и <math>\gamma</math> — суффикс <math>\beta</math>, такой что <math>|\alpha| \leq |\gamma| \leq |\beta|</math>, то <math>[\alpha]_R = [\gamma]_R = [\beta]_R</math>. В приведённом выше примере, <math>[c]_R = [bac]_R = \{aba\}</math>, а «промежуточным» суффиксом является <math>\gamma = ac</math>. И действительно, <math>[ac]_R = \{aba\}</math>.
| |
|
| |
| Таким образом, любое состояние <math>q = [\alpha]_R</math> суффиксного автомата принимает некоторую непрерывную [[Линейно упорядоченное множество|цепочку]] вложенных друг в друга суффиксов наибольшей строки из этого состояния<ref name=":10" />.
| |
|
| |
| ''Левым расширением'' <math>\overset{\scriptstyle{\leftarrow}}{\gamma}</math> строки <math>\gamma</math> называют самую длинную строку <math>\omega</math>, имеющую тот же правый контекст, что и <math>\gamma</math>. Длину <math>|\overset{\scriptstyle{\leftarrow}}{\gamma}|</math> самой длинной строки, принимаемой состоянием <math>q=[\gamma]_R</math>, обозначают как <math>len(q)</math>. Для него верно, что<ref name=":3" />:
| |
|
| |
| {{Теорема|Левое расширение строки <math>\gamma</math> может быть представлено в виде <math>\overleftarrow{\gamma} = \beta \gamma</math>, где <math>\beta</math> — самое длинное слово, такое что любому вхождению слова <math>\gamma</math> в <math>S</math> предшествует слово <math>\beta</math>.|макс-ширина=100%}}
| |
|
| |
| ''Суффиксной ссылкой'' <math>link(q)</math> от состояния <math>q=[\alpha]_R</math> называют указатель на состояние <math>p</math>, содержащее наибольший суффикс <math>\alpha</math>, который ''не'' принимается состоянием <math>q</math>.
| |
|
| |
| В таких обозначениях можно сказать, что состояние <math>q=[\alpha]_R</math> принимает в точности все суффиксы <math>\overset{\scriptstyle{\leftarrow}}{\alpha}</math>, которые длиннее <math>len(link(q))</math> и не длиннее <math>len(q)</math>. Кроме того, верно следующее<ref name=":3" />:
| |
|
| |
| {{Теорема|Суффиксные ссылки образуют [[Дерево (информатика)|дерево]] <math>\mathcal T(V, E)</math>, которое можно задать явно следующим образом:
| |
| # [[Вершина (теория графов)|Вершинам]] <math>V</math> соответствуют левые расширения <math>\overleftarrow{\omega}</math> всех подстрок <math>S</math>,
| |
| # [[Ребро (теория графов)|Рёбра]] <math>E</math> соединяют вершины <math>(\overleftarrow{\omega},\overleftarrow{\alpha\omega})</math>, такие что <math>\alpha \in \Sigma</math> и <math>\overleftarrow{\omega} \neq \overleftarrow{\alpha\omega}</math>.|макс-ширина=100%}}
| |
|
| |
| === Связь с суффиксным деревом ===
| |
| [[Файл:Suffix structures diamond (rus).svg|мини|260x260px|Преобразования суффиксных структур]]{{Основная статья|Суффиксное дерево}}''[[Префиксное дерево|Префиксным деревом]]'' (или ''бором'') называют корневое ориентированное [[Дерево (теория графов)|дерево]], дуги которого помечены [[Символьный тип|символами]] таким образом, что из любой [[Вершина (теория графов)|вершины]] <math>v</math> этого дерева исходит не больше одной [[Дуга (теория графов)|дуги]], помеченной данным символом. Некоторые вершины в префиксном дереве помечены. Говорят, что префиксное дерево задаёт множество слов, определяемое путями из корня дерева в помеченные вершины. Таким образом, префиксные деревья представляют собой особую разновидность конечных автоматов, если рассматривать корень как начальное состояние, а помеченные вершины — как финальные состояния<ref>{{Sfn-текст|Rubinchik, Shur|2018|pp=1—2}}</ref>. ''Суффиксным бором'' слова <math>S</math> называют префиксное дерево, задающее язык суффиксов этого слова. ''[[Суффиксное дерево|Суффиксным деревом]]'' называют дерево, получаемое из суффиксного бора процедурой сжатия, при которой последовательно идущие рёбра склеиваются если между ними находится нефинальная вершина, [[Степень вершины (теория графов)|степень]] которой равна 2<ref name=":3" />.
| |
|
| |
| По определению, суффиксный автомат может быть получен [[Минимизация ДКА|минимизацией]] суффиксного бора. Кроме того, сжатый суффиксный автомат может быть получен как минимизацией суффиксного дерева (если считать, что символы алфавита — это слова на рёбрах дерева), так и сжатием обычного автомата<ref name=":0" />. Однако, помимо очевидной связи между суффиксным автоматом и суффиксным деревом одной и той же строки, можно также установить некоторое соответствие между суффиксным автоматом строки <math>S=s_1 s_2 \dots s_n</math> и суффиксным деревом ''обращённой'' строки <math>S^R = s_n s_{n-1} \dots s_1</math><ref name=":11" />.
| |
|
| |
| Аналогично правым контекстам можно ввести ''левые контексты'' <math>[\omega]_L = \{\beta \in \Sigma^* : \beta \omega \in L\}</math> и ''правые расширения'' <math>\overset{\scriptstyle{\rightarrow}}{\omega~}</math>, соответствующие самым длинным строкам, имеющим заданный левый контекст, а также отношение эквивалентности <math>[\alpha]_L = [\beta]_L</math>. Если рассматривать правые расширения относительно языка <math>L</math> ''префиксов'' строки <math>S</math>, то можно получить, что<ref name=":3">{{Sfn-текст|Inenaga et al.|2005|loc=|pp=159—162}}</ref>:{{Теорема|Суффиксное дерево строки <math>S</math> может быть задано в явном виде следующим образом:
| |
| * Вершинам <math>V</math> соответствуют правые расширения <math>\overrightarrow{\omega}</math> всех подстрок <math>S</math>,
| |
| * Рёбрам <math>E</math> соответствуют тройки <math>(\overrightarrow{\omega},x\alpha, \overrightarrow{\omega x})</math> такие что <math>x \in \Sigma</math> и <math>\overrightarrow{\omega x}=\overrightarrow{\omega} x \alpha</math>.
| |
|
| |
| Здесь тройка <math>(v_1, \omega, v_2) \in E</math> значит, что на ребре из <math>v_1</math> в <math>v_2</math> записана строка <math>\omega</math>.|макс-ширина=100%}}
| |
|
| |
| Из чего следует, что дерево суффиксных ссылок для автомата строки <math>S</math> и суффиксное дерево строки <math>S^R</math> [[Изоморфизм графов|изоморфны]]<ref name=":11">{{sfn-текст|Fujishige et al.|2016|loc=|pp=1—3}}</ref>:
| |
| <center>
| |
| {| class="wikitable mw-collapsible mw-collapsed"
| |
| |-
| |
| ! Суффиксные структуры слов ''abbcbc'' и ''cbcbba''
| |
| |-
| |
| | <gallery widths="380" heights="320" class="center">
| |
| Файл:Suffix automaton for abbcbc.svg|Суффиксный автомат для слова ''abbcbc''
| |
| Файл:Suffix structures.svg|Суффиксный бор, суффиксное дерево и сжатый суффиксный автомат для слова ''abbcbc''. Номера вершин соответствуют состояниям, в которые они переходят при минимизации или сжатии
| |
| Файл:Suffix tree for cbcbba.svg|Суффиксное дерево для слова ''cbcbba''<br>(дерево суффиксных ссылок для автомата слова ''abbcbc'')
| |
| </gallery>
| |
| |}
| |
| </center>
| |
|
| |
| Аналогично левым расширениям, для правых расширений также может быть сформулирована структурная лемма<ref name=":3" />:
| |
|
| |
| {{Теорема|Правое расширение строки <math>\gamma</math> может быть представлено в виде <math>\overrightarrow{\gamma} = \gamma\alpha</math>, где <math>\alpha</math> — самое длинное слово, такое что за любым вхождением <math>\gamma</math> в <math>S</math> сразу следует слово <math>\beta</math>.|макс-ширина=100%}}
| |
|
| |
| === Размер ===
| |
| В суффиксном автомате строки <math>S</math> длины <math>n>1</math> не больше <math>2n-1</math> состояний и не больше <math>3n-4</math> переходов, причём данные оценки достигаются на строках <math>abb\dots bb=ab^{n-1}</math> и <math>abb\dots bc=ab^{n-2}c</math> соответственно<ref name=":9">{{Sfn-текст|Blumer et al.|1984|loc=|pp=111—114}}</ref>. Можно также сформулировать более сильное утверждение о связи числа состояний и переходов в автомате: <math>|\delta| \leq |Q| + n - 2</math>, где <math>|\delta|</math> и <math>|Q|</math> — это число переходов и состояний соответственно<ref name=":10" />.
| |
| <center>
| |
| {| class="wikitable mw-collapsible mw-collapsed"
| |
| |-
| |
| ! Максимальные суффиксные автоматы
| |
| |-
| |
| | <gallery widths="380" heights="320" class="center">
| |
| Файл:DAWG for abb...b.svg|Суффиксный автомат для <math>ab^{n-1}</math>
| |
| Файл:DAWG for abb...bc.svg|Суффиксный автомат для <math>ab^{n-2}c</math>
| |
| </gallery>
| |
| |}
| |
| </center>
| |
|
| |
| == Построение ==
| |
| Суффиксный автомат строки <math>S=s_1s_2 \dots s_n</math> строится последовательным наращиванием слова, для которого он построен. Изначально имеется тривиальный автомат, построенный для пустого слова, а затем на каждом шаге к текущему слову добавляется один символ, что влечёт за собой перестройку состояний и переходов автомата<ref name=":12" />.
| |
|
| |
| === Изменение состояний ===
| |
| После приписывания нового символа к слову, некоторые классы эквивалентности изменятся. Пусть <math>[\alpha]_{R_\omega}</math> — правый контекст слова <math>\alpha</math> относительно языка суффиксов слова <math>\omega</math>. Тогда переход от <math>[\alpha]_{R_\omega}</math> к <math>[\alpha]_{R_{\omega x}}</math> при приписывании символа <math>x</math> к слову <math>\omega</math> описывается следующей леммой<ref name=":10" />:
| |
| {{Теорема|Пусть <math>\alpha, \omega \in \Sigma^*</math> — некоторые слова над алфавитом <math>\Sigma</math> и <math>x \in \Sigma</math> — некоторый символ этого алфавита. Тогда между правыми контекстами <math>[\alpha]_{R_\omega}</math> и <math>[\alpha]_{R_{\omega x} }</math> слова <math>\alpha</math> относительно языков суффиксов слов <math>\omega</math> и <math>\omega x</math> соответственно имеет место следующая связь:
| |
| * <math>[\alpha]_{R_{\omega x} } = [\alpha]_{R_\omega}x \cup \{\varepsilon\}</math> если <math>\alpha</math> — суффикс <math>\omega x</math>;
| |
| * <math>[\alpha]_{R_{\omega x} } = [\alpha]_{R_\omega}x</math> в противном случае.|макс-ширина=100%}}
| |
| То есть при добавлении одного символа <math>x</math> к текущему слову <math>\omega</math> правый контекст слова <math>\alpha</math> может измениться только в том случае, если <math>\alpha</math> является суффиксом слова <math>\omega x</math>. Из этого следует, что разбиение всех слов на классы эквивалентности по <math>\equiv_{R_{\omega x} }</math> является измельчением разбиения на классы эквивалентности по <math>\equiv_{R_\omega}</math>. Другими словами, если <math>[\alpha]_{R_{\omega x} } = [\beta]_{R_{\omega x} }</math>, то <math>[\alpha]_{R_{\omega} } = [\beta]_{R_{\omega} }</math>. Кроме того, при добавлении очередного символа к слову расщепление произойдёт у не более чем двух состояний. В первую очередь будет расщеплено состояние, которому соответствует пустой правый контекст (то есть то, которое принимает язык слов, не входящих в <math>\omega</math> в качестве подслова). Из этого состояния будет выделено новое состояние, содержащее всё слово <math>\omega x</math>, а также все его суффиксы, которые встречаются в <math>\omega x</math>, но не встречались в <math>\omega</math>. Соответственно, правый контекст этих слов, который ранее был пустым, теперь будет состоять только из пустого слова<ref name=":10" />.
| |
|
| |
| Учитывая связь между состояниями суффиксного автомата и вершинами суффиксного дерева, можно отследить и второе состояние, которое может расщепиться при добавлении очередного символа. Так как переход от слова <math>\omega</math> к <math>\omega x</math> соответствует переходу от <math>\omega^R</math> к <math>x \omega^R</math> для обращённой строки, приписывание символа <math>x</math> к строке <math>\omega</math> соответствует внесению одного нового (самого длинного) суффикса <math>x\omega^R</math> в суффиксное дерево строки <math>\omega^R</math>. При этом появляется не более двух вершин: одна из них будет соответствовать всему слову <math>x \omega^R</math>, а другая может появиться в том месте, где происходит ответвление от дерева. Таким образом, одно новое состояние соответствует правому контексту всей строки <math>\omega x</math>, а другое (если оно есть) может соответствовать только суффиксной ссылке этого состояния. Данные наблюдения можно обобщить теоремой<ref name=":10" />:
| |
|
| |
| {{Теорема|Пусть <math>\omega \in \Sigma^*</math> и <math>x \in \Sigma</math>. Пусть также <math>\alpha</math> является самым длинным суффиксом <math>\omega x</math>, который встречается в <math>\omega</math>, а <math>\beta=\overset{\scriptstyle{\leftarrow} }{\alpha}</math> — его левое расширение относительно <math>\omega</math>, то есть самое длинное подслово слова <math>\omega</math> такое что <math>[\alpha]_{R_\omega} = [\beta]_{R_\omega}</math>. Тогда для любых подслов <math>u,v</math> слова <math>\omega</math> верно следующее:
| |
| * Если <math>[u]_{R_\omega} = [v]_{R_\omega}</math> и <math>[u]_{R_\omega} \neq [\alpha]_{R_\omega}</math>, то <math>[u]_{R_{\omega x} } = [v]_{R_{\omega x} }</math>;
| |
| * Если <math>[u]_{R_\omega} = [\alpha]_{R_\omega}</math> и <math>\vert u\vert \leq \vert \alpha\vert </math>, то <math>[u]_{R_{\omega x} } = [\alpha]_{R_{\omega x} }</math>;
| |
| * Если <math>[u]_{R_\omega} = [\alpha]_{R_\omega}</math> и <math>\vert u\vert > \vert \alpha\vert </math>, то <math>[u]_{R_{\omega x} } = [\beta]_{R_{\omega x} }</math>.|макс-ширина=100%}}
| |
|
| |
| В частности, если <math>\alpha=\beta</math> (например, когда <math>x</math> вообще не встречается в <math>\omega</math> и <math>\alpha=\beta=\varepsilon</math>), расщепления второго состояния не происходит<ref name=":10" />.
| |
|
| |
| Помимо суффиксных ссылок, в новом автомате также нужно определить финальные состояния. Из структурных свойств автомата следует, что суффиксы любого слова <math>\alpha</math> расположены таким образом, что если <math>q=[\alpha]_R</math>, то суффиксы <math>\alpha</math>, чья длина превышает <math>len(link(q))</math>, лежат в <math>q</math>, суффиксы, чья длина больше <math>len(link(link(q))</math>, но не больше <math>len(link(q))</math>, лежат в <math>link(q)</math> и так далее. Иными словами, для любого суффикса <math>\alpha</math> найдётся вершина в ''суффиксном пути'' состояния <math>q</math>, который задаётся последовательностью <math>(q, link(q), link^2(q), \dots)</math>. Соответственно если обозначить состояние, принимающее в текущий момент всю строку <math>\omega</math>, как <math>last</math>, то терминальными (принимающими суффиксы <math>\omega</math>) состояниями будут те и только те состояния, которые входят в суффиксный путь <math>(last, link(last), link^2(last), \dots)</math><ref name=":12">{{Sfn-текст|Crochemore, Hancart|1997|loc=|pp=31—36}}</ref>.
| |
|
| |
| === Изменение переходов и суффиксных ссылок ===
| |
| Какие-либо изменения при добавлении очередного символа затрагивают не более чем два новых состояния, поэтому изменения в переходах автомата тоже будут затрагивать только эти состояния. После приписывания <math>x</math> к слову <math>\omega</math> образуется новое состояние <math>[\omega x]_{R_{\omega x} }</math>, а также, возможно, состояние <math>[\alpha]_{R_{\omega x} }</math>. Суффиксная ссылка из <math>[\omega x]_{R_{\omega x} }</math> будет вести в <math>[\alpha]_{R_{\omega x} }</math>, а из <math>[\alpha]_{R_{\omega x} }</math> — в <math>link([\alpha]_{R_{\omega} })</math>. Слова из <math>[\omega x]_{R_{\omega x} }</math> встречаются в <math>\omega x</math> только в виде суффиксов, поэтому из <math>[\omega x]_{R_{\omega x}}</math> не должно быть переходов, а ведущие в него переходы должны вести по символу <math>x</math> из суффиксов <math>\omega</math> с длиной хотя бы <math>|\alpha|</math>. Состояние <math>[\alpha]_{R_{\omega x}}</math> отщепляется от <math>[\alpha]_{R_\omega}</math>, поэтому переходы из этого состояния будут дублировать таковые у <math>[\alpha]_{R_\omega}</math>. А ведущие в него переходы будут вести по символу <math>x</math> из состояний, соответствующим суффиксам <math>\omega</math> длины меньше <math>|\alpha|</math> и не меньше <math>len(link([\alpha]_{R_{\omega} }))</math>, так как ранее эти переходы вели в <math>[\alpha]_{R_\omega}</math> и соответствовали отделившейся части состояния. Состояния, принимающие данные слова, можно определить по суффиксному пути состояния <math>[\omega]_{R_\omega}</math><ref name=":12" />.
| |
|
| |
| <center>
| |
| {| class="wikitable mw-collapsible mw-collapsed"
| |
| |-
| |
| ! colspan="2" | Построение суффиксного автомата для слова ''abbcbc''
| |
| |-
| |
| | style="vertical-align:top;width:50%" align="center" |
| |
| {|style="text-align:center;width:600px"
| |
| |+'''''∅ → a'''''
| |
| |style="background:#D8FBD8;width:50%"|[[Файл:single letter SA.svg|280x150px]]
| |
| |style="background:#FFF8CC;width:50%"|[[Файл:single letter SA.svg|280x150px]]
| |
| |-
| |
| |style="vertical-align:top;"|<small>При добавлении первого символа в автомате создаётся единственное новое состояние.</small>
| |
| |style="vertical-align:top;"|<small>Аналогичным образом в суффиксном дереве добавляется единственный лист.</small>
| |
| |}
| |
| | style="vertical-align:top;width:50%" align="center" |
| |
| {|style="text-align:center;width:600px"
| |
| |+'''''a → ab'''''
| |
| |style="background:#D8FBD8;width:50%"|[[Файл:ab SA.svg|280x150px]]
| |
| |style="background:#FFF8CC;width:50%"|[[Файл:ba ST.svg|280x150px]]
| |
| |-
| |
| |style="vertical-align:top;"|<small>Новые переходы проводятся из всех финальных состояний, так как новый символ раньше не встречался.</small>
| |
| |style="vertical-align:top;"|<small>По той же причине в дереве суффиксных ссылок новая вершина подвешивается к корню.</small>
| |
| |}
| |
| |-
| |
| | style="vertical-align:top;" align="center" |
| |
| {|style="text-align:center;width:600px"
| |
| |+'''''ab → abb'''''
| |
| |style="background:#D8FBD8;width:50%"|[[Файл:abb SA.svg|280x180px]]
| |
| |style="background:#FFF8CC;width:50%"|[[Файл:bba ST.svg|280x180px]]
| |
| |-
| |
| |style="vertical-align:top;"|<small>Состояние 2 принимает слова ''ab'' и ''b'', но только ''b'' станет суффиксом, поэтому это слово выделяется в состояние 4.</small>
| |
| |style="vertical-align:top;"|<small>В суффиксном дереве развёрнутого слова это соответствует расщеплению ребра, ведущего в вершину 2.</small>
| |
| |}
| |
| | style="vertical-align:top;" align="center" |
| |
| {|style="text-align:center;width:600px"
| |
| |+'''''abb → abbc'''''
| |
| |style="background:#D8FBD8;width:50%"|[[Файл:abbc SA.svg|280x180px]]
| |
| |style="background:#FFF8CC;width:50%"|[[Файл:cbba ST.svg|280x180px]]
| |
| |-
| |
| |style="vertical-align:top;"|<small>Новый символ раньше не встречался, переходы в него проводятся из всех финальных.</small>
| |
| |style="vertical-align:top;"|<small>В дереве суффиксных ссылок добавляется новый лист, подвешенный к корню.</small>
| |
| |}
| |
| |-
| |
| | style="vertical-align:top;" align="center" |
| |
| {|style="text-align:center;width:600px"
| |
| |+'''''abbc → abbcb'''''
| |
| |style="background:#D8FBD8;width:50%"|[[Файл:abbcb SA.svg|280x210px]]
| |
| |style="background:#FFF8CC;width:50%"|[[Файл:bcbba ST.svg|280x210px]]
| |
| |-
| |
| |style="vertical-align:top;"|<small>В состоянии 4 только слово ''b'' и оно является суффиксом, поэтому расщепления не происходит.</small>
| |
| |style="vertical-align:top;"|<small>Соответственно, в дереве суффиксных ссылок новый лист подвешивается к вершине 4.</small>
| |
| |}
| |
| | style="vertical-align:top;" align="center" |
| |
| {|style="text-align:center;width:600px"
| |
| |+'''''abbcb → abbcbc'''''
| |
| |style="background:#D8FBD8;width:50%"|[[Файл:Suffix Automaton extension.svg|280x210px]]
| |
| |style="background:#FFF8CC;width:50%"|[[Файл:Suffix Tree extension.svg|280x210px]]
| |
| |-
| |
| |style="vertical-align:top;"|<small>Состояние 5 принимает слова ''abbc'', ''bbc'', ''bc'' и ''c'', но только последние два являются суффиксами нового слова, поэтому они отделяются в отдельное состояние 8.</small>
| |
| |style="vertical-align:top;"|<small>Соответственно, в дереве суффиксных ссылок происходит расщепление ребра, ведущего в вершину 5.</small>
| |
| |}
| |
| |}
| |
| </center>
| |
|
| |
|
| |
| === Алгоритм построения автомата ===
| |
| Теоретические результаты выше приводят к следующему алгоритму, который принимает символ <math>x</math> и перестраивает суффиксный автомат слова <math>\omega</math> в суффиксный автомат слова <math>\omega x</math><ref name=":12" />:
| |
|
| |
| # Поддерживается номер состояния <math>last</math>, соответствующего всей строке <math>\omega</math>;
| |
| # При добавлении символа <math>x</math>, номер <math>last</math> запоминается в переменной <math>p</math>, а в <math>last</math> записывается номер нового состояния, соответствующего слову <math>\omega x</math>;
| |
| # Из состояний, соответствующих суффиксам <math>\omega</math>, проставляются переходы в <math>last</math>. Для этого идёт обход суффиксного пути <math>p, link(p), link^2(p),\dots</math>, пока не встретится состояние, из которого уже есть переход по <math>x</math>;
| |
| # Дальнейшие действия соответствуют одному из трёх случаев:
| |
| ## Если на всём суффиксном пути ни из одного состояния нет перехода по <math>x</math>, то <math>x</math> раньше не встречался в <math>\omega</math> и суффиксная ссылка из <math>last</math> ведёт в <math>q_0</math>;
| |
| ## Если переход по <math>x</math> нашёлся и ведёт из состояния <math>p</math> в состояние <math>q</math>, такое что <math>len(p)+1=len(q)</math>, то необходимости расщеплять <math>q</math> нет и достаточно провести суффиксную ссылку из <math>last</math> в <math>q</math>;
| |
| ## Если же <math>len(q) > len(p)+1</math>, то слова из состояния <math>q</math>, чья длина не превосходит <math>len(p)+1</math> должны быть выделены в отдельное состояние <math>cl</math>;
| |
| # Если на прошлом шаге было выделено отдельное состояние <math>cl</math>, то переходы и суффиксная ссылка из него должны дублировать оные в <math>q</math>, при этом <math>cl</math> станет общей суффиксной ссылкой состояний <math>q</math> и <math>last</math>;
| |
| # Переходы, которые вели в <math>q</math>, но соответствовали словам длины не больше <math>len(p)+1</math>, перенаправляются в <math>cl</math>. Для этого можно продолжать идти по суффиксному пути <math>p</math>, пока не найдётся состояние, переход из которого ведёт не в <math>q</math>.
| |
|
| |
| Процедура, реализующая этот алгоритм, может быть описана следующим псевдокодом:
| |
|
| |
| '''функция''' {{mvar|add_letter(x)}}:
| |
| '''определить''' {{mvar|p {{=}} last}}
| |
| '''присвоить''' {{mvar|last {{=}} new_state()}}
| |
| '''присвоить''' {{mvar|len(last) {{=}} len(p) + 1}}
| |
| '''пока''' {{mvar|δ(p, x)}} не определено:
| |
| '''присвоить''' {{mvar|δ(p, x) {{=}} last, p {{=}} link(p)}}
| |
| '''определить''' {{mvar|q {{=}} δ(p, x)}}
| |
| '''если''' {{mvar|q {{=}} last}}:
| |
| '''присвоить''' {{mvar|link(last) {{=}} q<sub>0</sub>}}
| |
| '''иначе если''' {{mvar|len(q) {{=}} len(p) + 1}}:
| |
| '''присвоить''' {{mvar|link(last) {{=}} q}}
| |
| '''иначе''':
| |
| '''определить''' {{mvar|cl {{=}} new_state()}}
| |
| '''присвоить''' {{mvar|len(cl) {{=}} len(p) + 1}}
| |
| '''присвоить''' {{mvar|δ(cl) {{=}} δ(q), link(cl) {{=}} link(q)}}
| |
| '''присвоить''' {{mvar|link(last) {{=}} link(q) {{=}} cl}}
| |
| '''пока''' {{mvar|δ(p, x) {{=}} q}}:
| |
| '''присвоить''' {{mvar|δ(p, x) {{=}} cl, p {{=}} link(p)}}
| |
|
| |
| Здесь <math>q_0</math> — начальное состояние автомата, <math>new\_state()</math> — функция, добавляющая в автомат новое состояние. Предполагается, что <math>last</math>, <math>len</math>, <math>link</math> и <math>\delta</math> хранятся в виде глобальных переменных.
| |
|
| |
| === Вычислительная сложность ===
| |
| В зависимости от используемых структур, детерминированная версия описанного выше алгоритма может быть реализована за время <math>O(n \log |\Sigma|)</math> с <math>O(n)</math> памяти или за время <math>O(n)</math> с <math>O(n |\Sigma|)</math> памяти, если считать, что выделение памяти происходит за <math>O(1)</math>. При этом для получения такой оценки времени работы необходимо провести [[амортизационный анализ]] внутренних циклов алгоритма. Если рассмотреть, как меняется параметр <math>len(p)</math> ''после'' первой итерации первого цикла, то можно увидеть, что с каждой итерацией цикла он строго уменьшается. При этом если на последней итерации предыдущего шага эта величина была равна <math>k</math>, то на второй итерации на следующем шаге эта величина будет равна <math>k+1</math>. То, что <math>len(p)</math> ни в какой момент времени не превосходит <math>n</math> и что между циклами эта величина увеличивается только на единицу, даёт требуемое утверждение. Аналогичным анализом может быть показана линейность суммарного времени исполнения второго цикла алгоритма<ref name=":12" />.
| |
|
| |
| == Вариации и обобщения ==
| |
| Суффиксный автомат тесно связан с другими суффиксными структурами и [[Индекс подстрок|индексами подстрок]]. Имея суффиксный автомат некоторой строки, возможно сжатием и рекурсивным обходом данного автомата построить суффиксное дерево этой строки за линейное время<ref>{{sfn-текст|Паращенко|2007|loc=|с=19—22}}</ref>. Аналогичные преобразования в обе стороны возможны между суффиксным автоматом строки <math>S</math> и суффиксным деревом обращённой строки <math>S^R</math><ref name=":11" />. Помимо этого был разработан ряд модификаций алгоритма, позволяющих строить автомат для множества строк, заданных префиксным деревом<ref name=":8" />, применять к нему сжатие<ref name=":7" />, поддерживать его структуру в режиме скользящего окна<ref>{{sfn-текст|Blumer|1987|loc=|p=451}}</ref>, а также перестраивать при добавлении символов как с конца, так и с начала строки<ref>{{sfn-текст|Inenaga|2003|loc=|p=1}}</ref>.
| |
|
| |
| === Сжатый суффиксный автомат ===
| |
| Как было сказано выше, сжатый суффиксный автомат может быть получен из обычного суффиксного автомата сжатием (удалением состояний, которые не являются финальными и из которых ведёт ровно один переход), а также минимизацией суффиксного дерева, если считать, что алфавит образуют слова, записанные на рёбрах дерева. Кроме того, состояния сжатого автомата могут быть описаны явно, аналогично тому, как это было сделано для несжатого автомата. ''Двусторонним расширением'' <math>\overset{\scriptstyle{\longleftrightarrow}}{\gamma}</math> слова <math>\gamma</math> называют самое длинное слово <math>\omega = \beta \gamma \alpha</math>, такое что любому вхождение <math>\gamma</math> в <math>S</math> предшествует слово <math>\beta</math>, а сразу за ним следует слово <math>\alpha</math>. В терминах левых и правых расширений это значит, что двустороннее расширение является левым расширением от правого расширения или, что эквивалентно, правым расширением от левого расширения: <math display="inline">\overset{\scriptstyle\longleftrightarrow}{\gamma} = \overset{\scriptstyle\leftarrow}{\overset{\rightarrow}{\gamma}} = \overset{\rightarrow}{\overset{\scriptstyle\leftarrow}{\gamma}}</math>. В терминах двусторонних расширений сжатый суффиксный автомат можно описать следующим образом<ref name=":3" />:{{Теорема|Сжатый суффиксный автомат слова <math>S</math> может быть задан парой <math>(V, E)</math>, где:
| |
|
| |
| * <math>V = \{\overleftrightarrow \omega : \omega \in \Sigma^*\}</math> — множество состояний автомата;
| |
| * <math>E = \{(\overleftrightarrow \omega, x \alpha, \overleftrightarrow {\omega x}) : x \in \Sigma, \alpha \in \Sigma^*, \overleftrightarrow{\omega x} = \overleftrightarrow{\omega} x\alpha\}</math> — множество переходов автомата.|макс-ширина=100%}}
| |
|
| |
| Двусторонние расширения порождают отношение эквивалентности <math display="inline">\overset{\scriptstyle\longleftrightarrow}{\alpha} = \overset{\scriptstyle\longleftrightarrow}{\beta}</math>, описывающее слова, принимаемые одним и тем же состоянием сжатого автомата. Это отношение является [[Транзитивное замыкание|транзитивным замыканием]] отношения <math display="inline">(\overset{\scriptstyle{\rightarrow}}{\alpha\,}=\overset{\scriptstyle{\rightarrow}}{\beta\,}) \vee (\overset{\scriptstyle{\leftarrow}}{\alpha} = \overset{\scriptstyle{\leftarrow}}{\beta})</math>, что подчёркивает тот факт, что состояния сжатого суффиксного автомата могут быть получены как склеиванием вершин суффиксного дерева, эквивалентных по <math>\overset{\scriptstyle{\leftarrow}}{\alpha} = \overset{\scriptstyle{\leftarrow}}{\beta}</math> (минимизация суффиксного дерева), так и склеиванием состояний суффиксного автомата, эквивалентных по <math>\overset{\scriptstyle{\rightarrow}}{\alpha\,}=\overset{\scriptstyle{\rightarrow}}{\beta\,}</math> (сжатие суффиксного автомата)<ref name=":13">{{sfn-текст|Blumer et al.|1987|loc=|p=|pp=585—588}}</ref>. Если у слов <math>\alpha</math> и <math>\beta</math> совпадают правые расширения, а у слов <math>\beta</math> и <math>\gamma</math> — левые, то в совокупности у слов <math>\alpha</math>, <math>\beta</math> и <math>\gamma</math> совпадает двустороннее расширение. При этом может оказаться, что у слов <math>\alpha</math> и <math>\gamma</math> не совпадают ни левые, ни правые расширения. В случае <math>S=\beta=ab</math>, <math>\alpha=a</math> и <math>\gamma=b</math> левые и правые расширения таковы: <math>\overset{\scriptstyle{\rightarrow}}{\alpha\,}=\overset{\scriptstyle{\rightarrow}}{\beta\,}=ab=\overset{\scriptstyle{\leftarrow}}{\beta} = \overset{\scriptstyle{\leftarrow}}{\gamma}</math>, но <math>\overset{\scriptstyle{\rightarrow}}{\gamma\,}=b</math> и <math>\overset{\scriptstyle{\leftarrow}}{\alpha}=a</math>. В случае односторонних контекстов и расширений слова из одного и того же класса эквивалентности образовывали непрерывную цепочку вложенных друг в друга префиксов или суффиксов и могли быть однозначно определены длинами самого короткого и самого длинного слов в классе. В случае же двусторонних расширений наверняка можно сказать только то, что слова из одного и того же класса являются ''подсловами'' самого длинного слова из этого класса, а в остальном классы могут иметь достаточно сложную структуру. Общее число таких классов эквивалентности не превосходит <math>n+1</math>, из чего следует, что у сжатого суффиксного автомата строки длины <math>n</math> будет не больше <math>n+1</math> состояний. Количество переходов в таком автомате не превосходит <math>2n-2</math><ref name=":3" />.
| |
|
| |
| === Суффиксный автомат для набора строк ===
| |
| Пусть задан набор слов <math>T=\{S_1, S_2, \dots, S_k\}</math>. Аналогично автомату, построенному по единственному слову <math>S</math> можно рассмотреть обобщённый суффиксный автомат, который принимает язык слов, являющихся суффиксом хотя бы одного слова из <math>T</math>. При этом для числа состояний и переходов данного автомата будут выполняться все те же ограничения, которые были указаны выше, если положить <math>n = |S_1| + |S_2| + \dots + |S_k|</math><ref name=":13" />. Сам алгоритм построения по своей сути похож на алгоритм построения автомата для одной строки, но вместо указателя <math>last</math> на состояние соответствующее слову <math>\omega</math> при переходе к слову <math>\omega x</math> функция ''add_letter'' будет принимать указатель на состояние, принимающее слово <math>\omega_i</math>, подразумевая, что переход происходит от текущего набора слов <math>\{\omega_1, \dots, \omega_i, \dots, \omega_k\}</math> к набору <math>\{\omega_1, \dots, \omega_i x, \dots, \omega_k\}</math>. Помимо основных действий, которые уже заложены в алгоритм нужно будет отдельно разобрать случай когда строка <math>\omega_i x</math> уже присутствует в автомате — в таком случае, возможно, придётся расщепить состояние, которое её принимает, аналогично тому, как это происходило при формировании суффиксной ссылки в алгоритме для единичного слова<ref>{{sfn-текст|Blumer et al.|1987|loc=|p=|pp=588—589}}</ref><ref>{{sfn-текст|Blumer et al.|1987|loc=|p=593|pp=}}</ref>.
| |
|
| |
| Дальнейшим развитием этой идеи стало построение суффиксного автомата для случая когда набор <math>T</math> задан не в явном виде, а [[Префиксное дерево|префиксным деревом]] на <math>Q</math> вершинах. Мохри и другие показали, что такой автомат содержит не более <math>2Q-2</math> состояний и может быть построен за линейное от своего размера время. При этом количество переходов в таком автомате может достигать <math>O(Q|\Sigma|)</math> — например, если рассмотреть множество слов <math>T=\{\sigma_1, a\sigma_1, a^2\sigma_1, \dots, a^n \sigma_1, a^n \sigma_2, \dots, a^n \sigma_k \}</math> над алфавитом <math>\Sigma=\{a,\sigma_1,\dots,\sigma_k\}</math>, то суммарная длина слов из этого множества будет порядка <math display="inline">O(n^2+nk)</math>, число вершин в соответствующем префиксном дереве будет равна <math>O(n+k)</math>, а в суффиксном автомате будет порядка <math>O(n+k)</math> состояний и <math>O(nk)</math> переходов. Сам алгоритм, предложенный Мохри, во многом повторяет общий алгоритм построения автомата по набору строк, но вместо того, чтобы каждый раз дописывать символы слова из набора от начала до конца, алгоритм обходит префиксное дерево в порядке [[Обход в ширину|обхода в ширину]] и приписывает очередные символы в том порядке, в котором встречает их при обходе, что гарантирует амортизированно линейное время работы алгоритма<ref>{{sfn-текст|Mohri et al.|2009|loc=|страницы=|p=|pp=3558—3560}}</ref>.
| |
|
| |
| === Скользящее окно ===
| |
| В некоторых [[Сжатие данных|алгоритмах сжатия]], таких как [[LZ77]] и [[RLE]] может быть полезным хранить суффиксный автомат или подобную структуру не для всего считанного слова, а только для <math>k</math> последних символов. В первую очередь, такая необходимость всплывает из-за специфики задач сжатия данных, где сжимаемые строки обычно достаточно велики и использование <math>O(n)</math> памяти нежелательно. В 1985 году Джанет Блумер разработала алгоритм, поддерживающий суффиксный автомат на скользящем окне размера <math>k</math> и работающий за <math>O(nk)</math> в худшем случае и <math>O(n \log k)</math> в среднем, в предположении, что символы в сжимаемом слове распределены независимо и [[Равномерное распределение|равномерно]]. В той же работе было показано, что оценка <math>O(nk)</math> является неулучшаемой — если рассмотреть слова, полученные конкатенацией нескольких слов вида <math>(ab)^m c (ab)^m d</math>, где <math>k=6m+2</math>, то число состояний автомата, который соответствует подсловам длины <math>k</math> чередовалось бы с резкими прыжками порядка <math>m</math> по величине, что делает существование даже теоретического алгоритма, улучшающего оценку в <math>O(nk)</math> для суффиксного автомата невозможным<ref>{{sfn-текст|Blumer|1987|loc=|p=|pp=461—465}}</ref>.
| |
|
| |
| Казалось бы, то же самое должно быть верно и для [[Суффиксное дерево|суффиксного дерева]], так как вершины суффиксного дерева соответствуют состояниям суффиксного автомата развёрнутой строки. Однако, если в суффиксном дереве не выделять отдельную вершину для каждого суффикса, то таких резких скачков уже не будет и построение амортизированного алгоритма, поддерживающего суффиксное дерево на скользящем окне возможно. Соответствующий алгоритм для суффиксного дерева, основанный на алгоритме [[Маккрейт, Эдвард|Маккрейта]] и поддерживающий добавление нового символа справа и удаление символа слева, был предложен в 1989 году Эдвардом Фиала и Дэниелом Грином<ref>{{sfn-текст|Fiala, Greene|1989|p=490}}</ref>, а в 1996 году изложен в терминах [[Алгоритм Укконена|алгоритма Укконена]] Джеспером Ларссоном<ref>{{sfn-текст|Larsson|1996}}</ref><ref>{{sfn-текст|Brodnik, Jekovec|2018|p=1}}</ref>. В связи с этим долгое время оставался открытым вопрос о том, возможно ли поддержание быстрого скользящего окна для сжатого автомата, который объединяет в себе некоторые свойства как обычного суффиксного автомата, так и суффиксного дерева. Отрицательный ответ на этот вопрос был получен в 2008 Мартином Сенфтом и Томашем Двораком, показавшим, что если алфавит состоит из двух и более символов, то амортизированное время, требуемое для сдвига окна на один символ в худшем случае имеет порядок <math>O(k)</math><ref>{{sfn-текст|Senft, Dvořák|2008|p=109}}</ref>.
| |
|
| |
| В то же время, если ''точная'' ширина окна не важна и задача заключается лишь в том, чтобы поддерживать окно, чья ширина по порядку величины не превосходит <math>O(k)</math>, это можно сделать приближённым алгоритмом, предложенным Иненагой и другими в 2004 году. Особенностью алгоритма является то, что «окно», которое двигается по слову, имеет переменную длину, которая при этом в любой момент не меньше <math>k</math> и не больше <math>2k+1</math>, при этом суммарное время работы остаётся линейным<ref>{{sfn-текст|Inenaga et al.|2004}}</ref>.
| |
|
| |
| == Применения ==
| |
| Суффиксный автомат строки <math>S</math> может использоваться для решения таких задач, как<ref name=":4">{{Sfn-текст|Crochemore, Hancart|1997|страницы=|loc=|pp=39—41}}</ref><ref>{{Sfn-текст|Crochemore, Hancart|1997|pp=36—39|loc=}}</ref>:
| |
|
| |
| * Подсчёт количества различных подстрок <math>S</math> за время <math>O(|S|)</math> в режиме онлайн,
| |
| * Поиск самой длинной подстроки <math>S</math>, которая входит в неё хотя бы два раза, за время <math>O(|S|)</math>,
| |
| * Поиск наибольшей общей подстроки строк <math>S</math> и <math>T</math> за время <math>O(|T|)</math>,
| |
| * Подсчёт числа вхождений строки <math>T</math> в <math>S</math> в качестве подстроки за время <math>O(|T|)</math>,
| |
| * Поиск всех вхождений <math>T</math> в <math>S</math> за время <math>O(|T|+k)</math>, где <math>k</math> — количество вхождений.
| |
|
| |
| Здесь стоит считать, что некоторая строка <math>T</math> подаётся на вход, когда автомат уже построен и готов к использованию.
| |
|
| |
| Суффиксные автоматы также нашли своё применение в таких прикладных задачах, как сжатие данных<ref>{{sfn-текст|Yamamoto et al.|2014|loc=|p=675}}</ref>, идентификация музыки по записанным фрагментам<ref>{{sfn-текст|Crochemore et al.|2003|loc=|p=211}}</ref><ref>{{sfn-текст|Mohri et al.|2009|loc=|страницы=|p=3553}}</ref> и сопоставление геномных последовательностей<ref>{{sfn-текст|Faro|2016|loc=|p=145}}</ref>.
| |
|
| |
| == Примечания ==
| |
| {{Примечания|узкие}}
| |
|
| |
| == Литература ==
| |
| {{refbegin|2}}
| |
| * {{ВД-Источник|Q99428232|ref=Sgarbas et al.}}
| |
| * {{ВД-Источник|Q99428342|ref=Perrin}}
| |
| * {{ВД-Источник|Q29541479|ref=Weiner}}
| |
| * {{ВД-Источник|Q90300966|ref=Pratt}}
| |
| * {{ВД-Источник|Q90305414|ref=Slisenko}}
| |
| * {{ВД-Источник|Q90309073|ref=Blumer et al.}}
| |
| * {{ВД-Источник|Q90311855|ref=Blumer et al.}}
| |
| * {{ВД-Источник|Q90327976|ref=Blumer}}
| |
| * {{ВД-Источник|Q90329833|ref=Chen, Seiferas}}
| |
| * {{ВД-Источник|Q90335534|ref=Inenaga}}
| |
| * {{ВД-Источник|Q57518591|ref=Inenaga et al.}}
| |
| * {{ВД-Источник|Q90341606|ref=Inenaga et al.}}
| |
| * {{ВД-Источник|Q90345535|ref=Inenaga et al.}}
| |
| * {{ВД-Источник|Q90348192|ref=Yamamoto et al.}}
| |
| * {{ВД-Источник|Q90410044|ref=Fujishige et al.}}
| |
| * {{ВД-Источник|Q90410808|ref=Mohri et al.}}
| |
| * {{ВД-Источник|Q90412338|ref=Faro}}
| |
| * {{ВД-Источник|Q90413384|ref=Crochemore, Hancart}}
| |
| * {{ВД-Источник|Q90413885|ref=Crochemore, Vérin}}
| |
| * {{ВД-Источник|Q90414195|ref=Crochemore et al.}}
| |
| * {{ВД-Источник|Q90418603|ref=Hopcroft, Ullman}}
| |
| * {{ВД-Источник|Q90425560|ref=Fiala, Greene}}
| |
| * {{ВД-Источник|Q90426624|ref=Senft, Dvořák}}
| |
| * {{ВД-Источник|Q90427112|ref=Larsson}}
| |
| * {{ВД-Источник|Q90431196|ref=Brodnik, Jekovec}}
| |
| * {{ВД-Источник|Q90726647|ref=Rubinchik, Shur}}
| |
| * {{ВД-Источник|Q90432456|ref=Серебряков и др.}}
| |
| * {{ВД-Источник|Q90435728|ref=Рубцов}}
| |
| * {{ВД-Источник|Q90436837|ref=Паращенко}}
| |
| {{refend}}
| |
|
| |
| == Ссылки ==
| |
| {{Навигация}}
| |
| * {{Cite web|url=http://e-maxx.ru/algo/suffix_automata|title=Суффиксный автомат. Построение за O(N) и применения|author=|website=MAXimal|date=|publisher=}}
| |
| * {{Cite web|url=https://neerc.ifmo.ru/wiki/index.php?title=Суффиксный_автомат|title=Суффиксный автомат|author=|website=Викиконспекты ИТМО|date=|publisher=}}
| |
|
| |
| {{ВС}}
| |
| {{Строки}}
| |
| {{Формальные языки}}
| |
|
| |
| [[Категория:Строковые алгоритмы]]
| |
| [[Категория:Поиск подстроки]]
| |
| [[Категория:Структуры данных]] | | [[Категория:Структуры данных]] |
| {{Избранная статья|Математика}}
| |
