http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Hx&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T09:54:47ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&diff=55576Суффиксный автомат2016-10-17T20:35:42Z<p>Hx: Опечатка: начальное состояние - это i, а не q</p>
<hr />
<div>{{Определение<br />
|definition =<br />
'''Суффиксный автомат''' (англ. ''suffix automaton'', ''directed acyclic word graph'') {{---}} минимальный [[Детерминированные_конечные_автоматы|ДКА]], который принимает все суффиксы строки и только их.<br />
}}<br />
<br />
__TOC__<br />
==Описание==<br />
Рассмотрим конечный алфавит <tex>A</tex>. Пусть <tex>A^*</tex> {{---}} набор слов в алфавите <tex>A</tex>. Суффиксный автомат <tex>\mathcal{A}</tex> {{---}} это набор <tex>\langle Q, A, i, T, \delta \rangle</tex>, где<br />
* <tex>Q</tex> {{---}} конечный набор состояний,<br />
* <tex>i</tex> {{---}} начальное состояние,<br />
* <tex>T</tex> {{---}} набор терминальных состояний,<br />
* <tex>\delta</tex> {{---}} функция перехода. <br />
Для <tex>q \in Q</tex> и <tex>a \in A</tex>, <tex>\delta(q, a)</tex> определена, если состояние достижимо из <tex>q</tex> переходом по символу <tex>a</tex>. Функция перехода распространяется на слова и <tex>\delta(q, x)</tex> обозначает, что если она существует, то состояние достигнуто после чтения слова <tex>x</tex> из состояния <tex>q</tex>.<br />
Автомат <tex>\mathcal{A}</tex> распознает язык <tex>\{x \in A^* : \delta(i, x) \in T \}</tex>.<br />
<br />
Суффиксный автомат <tex>\mathcal{A}</tex> для строки <tex>s</tex> представляет собой [[Основные_определения_теории_графов|ациклический ориентированный граф]], с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами <tex>s</tex>:<br />
* вершины этого графа {{---}} состояния автомата, а рёбра {{---}} переходы,<br />
* каждый переход в автомате {{---}} ребро в графе, помеченное некоторым символом и все рёбра, исходящие из одной вершины имеют разные метки,<br />
* одно из состояний называется начальным, из него достижимы все остальные состояния,<br />
* одно или несколько состояний помечены как терминальные {{---}} если пройти от начального состояния до терминального по какому-либо пути и выписывать при этом символы на переходах, то получим один из суффиксов строки <tex>s</tex>.<br />
<br><br />
[[Файл:Suffix_automaton_ex.png|540px|frame|center|Пример суффиксного автомата для строки <tex>abbab</tex>.]]<br />
<br />
{{Определение<br />
|definition = <br />
Состояние <tex>q</tex> '''принимает строку''' <tex>s</tex>, если существует путь из начального состояния в <tex>q</tex>, такой, что если последовательно выписать буквы на рёбрах на пути, получим строку <tex>s</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition = <br />
Автомат '''принимает строку''' <tex>s</tex>, если её принимает хотя бы одно из финальных состояний.<br />
}}<br />
<br />
Так как автомат детерминированный, то каждому пути соответствует строка. <br />
<br />
Если две строки <tex>a</tex> и <tex>b</tex> принимаются одним состоянием <tex>q</tex> произвольного автомата, то для любой строки <tex>x</tex> строки <tex>ax</tex> и <tex>bx</tex> принимаются или не принимаются автоматом одновременно. Действительно, независимо от того, как мы пришли в состояние <tex>q</tex>, если мы пройдём из него по пути, соответствующему строке <tex>x</tex>, мы сможем точно сказать, в какое состояние мы попадём (в частности, будет ли оно финальным). Значит, любому состоянию <tex>q</tex> соответствует множество строк <tex>X_q</tex>, которые переводят его в одно из конечных состояний. <br />
{{Определение<br />
|definition = <br />
Множество <tex>X_q</tex> называют '''правым контекстом''' состояния.<br />
}}<br />
<br />
Правый контекст определен не только для состояния, но и для строк, которые оно принимает {{---}} правый контекст строк совпадает с правым контекстом состояния.<br />
<br />
{{Утверждение<br />
|statement=Состояний в автомате не меньше, чем различных правых контекстов у подстрок строки, для которой он построен, причём в минимальном автомате достигается нижняя оценка.<br />
|proof=Допустим, что в автомате есть два состояния <tex>q_1</tex> и <tex>q_2</tex> такие что <tex>X_{q_1} = X_{q_2}</tex>. Мы можем удалить состояние <tex>q_2</tex> и перевести переходы, ведущие в него в состояние <tex>q_1</tex>. Множество принимаемых строк от этого не изменится, следовательно, мы можем продолжать, пока количество состояний не будет равно числу попарно различных правых контекстов. <br />
}}<br />
Таким образом, ДКА является минимальным тогда и только тогда, когда правые контексты всех его состояний попарно различны.<br />
В случае суффиксного автомата правый контекст <tex>X_a</tex> строки <tex>a</tex> взаимнооднозначно соответствует множеству правых позиций вхождений строки <tex>a</tex> в строку <tex>s</tex>. Таким образом, каждое состояние автомата принимает строки с одинаковым множеством правых позиций их вхождений и обратно, все строки с таким множеством позиций принимается этим состоянием.<br />
<br />
==Построение==<br />
===Алгоритм===<br />
{{Определение<br />
|definition = <br />
Пусть длина самой короткой строки, которая принимается состоянием <tex>q</tex> равно <tex>k</tex>, тогда '''суффиксная ссылка''' <tex>\mathrm{link_q}</tex> будет вести из этого состояния в состояние, которое принимает эту же строку без первого символа.<br />
}}<br />
Будем обозначать длину самой длинной строки, которая принимается состоянием <tex>q</tex> как <tex>\mathrm{len_q}</tex>. Длина самой короткой строки из <tex>q</tex> в таком случае будет равна <tex>\mathrm{len(link_q)} + 1</tex>. <br />
Суффиксный автомат может быть построен за линейное время (при константном размере алфавита) online-алгоритмом. Будем добавлять символы строки <tex>s</tex> по одному, перестраивая при этом автомат. <br />
Изначально автомат состоит из одного состояния, для которого <tex>\mathrm{len(0)} = 0</tex>, а <tex>\mathrm{link_0} = -1</tex>.<br />
<br>Обозначим состояние <tex>\mathrm{last}</tex>, соответствующее текущей строке до добавления символа <tex>c</tex> (изначально <tex>\mathrm{last} = 0</tex>). <br>Создадим новое состояние <tex>\mathrm{cur}</tex>, <tex>\mathrm{len(cur)} = \mathrm{len(last)} + 1</tex>. <br>Рассмотрим все переходы из <tex>\mathrm{last}</tex> по текущему символу <tex>c</tex>. Если перехода нет, то добавляем переход в <tex>\mathrm{cur}</tex>, переходим по суффиксной ссылке и повторяем процедуру снова. Если переход существует, то остановимся и обозначим текущее состояние за <tex>p</tex>. Если перехода не нашлось и по суффиксным ссылкам мы дошли до фиктивного состояния (на которое указывает <tex>\mathrm{link_0}</tex>), то <tex>\mathrm{link_{cur}} = 0</tex>.<br><br />
Допустим, что мы остановились в состоянии <tex>p</tex>, из которого существует переход с символом <tex>c</tex>. Обозначим состояние, куда ведёт переход, через <tex>q</tex>. Рассмотрим два случая:<br><br />
# Если <tex>\mathrm{len(p)} + 1 = \mathrm{len(q)}</tex>, то <tex>\mathrm{link(q)} = \mathrm{cur}</tex>.<br><br />
# В противном случае, создадим новое состояние <tex>\mathrm{new}</tex>, скопируем в него <tex>q</tex> вместе с суффиксными ссылками и переходами. <tex>\mathrm{len(new)}</tex> присвоим значение <tex>\mathrm{len(p)} + 1</tex>. Перенаправим суффиксную ссылку из <tex>q</tex> в <tex>\mathrm{new}</tex> и добавим ссылку из <tex>\mathrm{cur}</tex> в <tex>\mathrm{new}</tex>. Пройдём по всем суффиксным ссылкам из состояния <tex>p</tex> и все переходы в состояние <tex>q</tex> по символу <tex>c</tex> перенаправим в <tex>\mathrm{new}</tex>.<br />
Обновим значение <tex>\mathrm{last} = \mathrm{cur}</tex>.<br />
===Пример построения===<br />
{| class = "wikitable"<br />
! Изображение !! Описание<br />
|-<br />
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s1.png|x180px|center|Шаг 1.]]<br />
|Изначально автомат состоит из одного начального состояния. <tex>\mathrm{last} = 0, \mathrm{len(0)} = 0</tex><br />
|-<br />
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s2.png|x180px|center|Шаг 2.]]<br />
|Добавляем символ <tex>a</tex>. Создаем состояние <tex>1</tex>. Переходов из начального состояния по символу <tex>a</tex> нет, перейти по суффиксным ссылкам некуда, значит добавим суффиксную ссылку <tex>\mathrm{link_{1}} = 0</tex>. <tex>\mathrm{last} = 1, \mathrm{len(1)} = 1</tex><br />
|-<br />
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s3.png|x180px|center|Шаг 3.]]<br />
|Добавляем символ <tex>b</tex>. Создаем состояние <tex>2</tex>. Добавим переход из <tex>1</tex>, откатимся по суффиксной ссылке и добавим переход из <tex>0</tex>. Добавим суффиксную ссылку <tex>\mathrm{link_{2}} = 0</tex>. <tex>\mathrm{last} = 2, \mathrm{len(2)} = 2</tex><br />
|-<br />
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s4.png|x180px|center|Шаг 4.]]<br />
|Аналогично добавим символ <tex>c</tex> и обновим автомат. <tex>\mathrm{last} = 3, \mathrm{len(3)} = 3</tex><br />
|-<br />
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s5.png|x180px|center|Шаг 5.]]<br />
|Добавляем символ <tex>b</tex>. Добавим переход из <tex>3</tex> и перейдем по суффиксной ссылке в начальное состояние. Из состояния <tex>0</tex> существует переход по символу <tex>b</tex><br />
|-<br />
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s6.png|x180px|center|Шаг 6.]]<br />
|Рассмотрим состояние <tex>2</tex>, куда существует переход. Имеем <tex>\mathrm{len(0)} + 1 \neq \mathrm{len(2)}</tex>.<br />
# Создаем новое состояние <tex>5</tex>.<br />
# Копируем в него все суффиксные ссылки и переходы из <tex>2</tex> и присвоим <tex>\mathrm{len(5)} = \mathrm{len(0)} + 1 = 1</tex>.<br />
# Перенаправим суффиксную ссылку из <tex>2</tex> в <tex>5</tex> и добавим ссылку из <tex>4</tex> в <tex>5</tex>. Перенаправим переход <tex>0 \rightarrow 2</tex> в состояние <tex>5</tex>.<br />
|-<br />
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s7.png|x180px|center|Шаг 7.]]<br />
|Построение автомата завершено. Чтобы пометить терминальные вершины, найдём состояние, которое принимает строку <tex>abcb</tex> и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.<br />
|-<br />
|}<br />
<br />
==Реализация==<br />
В приведённой ниже реализации используются следующие переменные:<br />
* <tex>\mathrm{edges[]}</tex> {{---}} массив отображений (ключ {{---}} символ, значение {{---}} номер состояния) с переходами,<br />
* <tex>\mathrm{link[]}</tex> {{---}} массив суффиксных ссылок, <br />
* <tex>\mathrm{len[]}</tex> {{---}} массив длин строк,<br />
* <tex>\mathrm{newState()}</tex> {{---}} функция, которая создаёт новое состояние и возвращает его номер,<br />
* <tex>\mathrm{clone()}</tex> {{---}} функция, которая копирует состояние и возвращает номер нового состояния,<br />
* <tex>\mathrm{last}</tex> {{---}} последнее состояние.<br />
<br />
'''func''' addChar(c ''': char''')''':'''<br />
'''int''' cur = newState() <font color="green">// создаём новое состояние и получаем его номер</font> <br />
<br />
'''int''' p = last<br />
'''while''' p >= 0 '''and''' edges[p].find(c) == ''null''<br />
edges[p][c] = cur<br />
p = link[p]<br />
<br />
'''if''' p != -1<br />
'''int''' q = edges[p][c]<br />
'''if''' len[p] + 1 == len[q]<br />
link[cur] = q<br />
'''else'''<br />
'''int''' new = clone(q) <font color="green">// скопируем состояние <tex>q</tex> и получим номер нового состояния</font><br />
len[new] = len[p] + 1<br />
link[q] = link[cur] = new<br />
'''while''' p >= 0 '''and''' edges[p][c] == q<br />
edges[p][c] = new<br />
p = link[p]<br />
last = cur<br />
<br />
==Применение==<br />
===Проверка вхождения строки===<br />
{{Задача<br />
|definition =<br />
Даны строки <tex>s</tex> и <tex>p</tex>. Требуется проверить, является ли строка <tex>p</tex> подстрокой <tex>s</tex>.<br />
}}<br />
Построим суффиксный автомат для строки <tex>s</tex>.<br><br />
Пусть текущее состояние {{---}} <tex>\mathrm{cur}</tex>, изначально равно <tex>0</tex> (начальному состоянию).<br><br />
Будем по очереди обрабатывать символы строки <tex>p</tex>. Если из состояния <tex>\mathrm{cur}</tex> есть переход в по текущему символу, но перейдем в новое состояние и повторим процедуру. Если перехода не существует, то <tex>p</tex> не является подстрокой <tex>s</tex>. Если успешно обработали все символы <tex>p</tex>, то она является подстрокой <tex>s</tex>.<br>Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.<br />
<br />
===Позиция первого вхождения строки===<br />
{{Задача<br />
|definition =<br />
Даны строки <tex>s</tex> и <tex>p</tex>. Требуется найти позицию первого вхождения строки <tex>p</tex> в <tex>s</tex>.<br />
}}<br />
Построим суффиксный автомат для строки <tex>s</tex>.<br><br />
В процессе построения для каждого состояния <tex>q</tex> будем хранить значение <tex>\mathrm{first(q)}</tex> {{---}} позицию окончания первого вхождения строки.<br />
Поддерживать позицию <tex>\mathrm{first}</tex> можно следующим образом: при добавлении нового состояния <tex>\mathrm{first(cur)} = \mathrm{len(cur)} - 1</tex>, а при клонировании вершины <tex>\mathrm{first(new)} = \mathrm{first(q)}</tex>.<br><br />
Для поиска вхождения обойдём автомат, как в предыдущей задаче. Пусть состояние <tex>p'</tex> в автомате соответствует строке <tex>p</tex>. Тогда ответ на задачу <tex>\mathrm{first(p')} - |p| + 1</tex>.<br />
<br>Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.<br />
===Количество различных подстрок===<br />
{{Задача<br />
|definition =<br />
Дана строка <tex>s</tex>. Найти количество различных подстрок строки <tex>s</tex>.<br />
}}<br />
Построим суффиксный автомат для строки <tex>s</tex>.<br><br />
Каждой подстроке в суффиксном автомате соответствует путь, тогда ответ на задачу {{---}} количество различных путей из начальной вершины. Так как суфавтомат представляет собой ациклический граф, мы можем найти [[Задача_о_числе_путей_в_ациклическом_графе|количество путей в графе методом динамического программирования]].<br />
===Наибольшая общая подстрока двух строк===<br />
{{Задача<br />
|definition=<br />
Даны строки <tex>s</tex> и <tex>t</tex>. Требуется найти наибольшую общую подстроку двух строк.<br />
}}<br />
Построим суффиксный автомат для строки <tex>s</tex>.<br><br />
Пройдем по строке <tex>t</tex> и для текущего символа будем искать длину наибольшей общей подстроки, которая заканчивается в текущей позиции. Для этого будем поддерживать <tex>v</tex> {{---}} текущее состояние и <tex>l</tex> {{---}} текущую длину совпадающей части.<br><br />
Изначально <tex>v = 0</tex>, <tex>l = 0</tex> {{---}} совпадение пустое. Рассматриваем текущий символ <tex>t_i</tex>. Если в автомате существует переход из текущего состояния по данному символу, то перейдем в новое состояние и увеличим длину <tex>l</tex> на <tex>1</tex>.<br>Если перехода не существует, то попробуем минимально уменьшить длину совпадающей подстроки: перейдем по суффиксной ссылке из <tex>v</tex> в новое состояние и примем <tex>l = \mathrm{len(v)}</tex>. Повторим операцию до тех пор, пока не найдем переход. Если по суффиксным ссылкам мы дошли до состояния, в которое ведет суффиксная ссылка начальной вершины, то это значит, что символа <tex>t_i</tex> нет в строке <tex>s</tex>. В таком случае примем <tex>v = l = 0</tex>, после чего перейдем к следующему символу строки <tex>t</tex>.<br><br />
Длиной наибольшей общей подстроки будет <tex>\mathrm{maxLen}</tex> {{---}} максимум из всех значений <tex>l</tex>, полученных в ходе работы алгоритма. Тогда ответом на задачу будет являться подстрока <tex>t[(\mathrm{maxPos} - \mathrm{maxLen} + 1) .. \mathrm{maxPos}]</tex>, где <tex>\mathrm{maxPos}</tex> {{---}} позиция, в которой достигнут максимум.<br />
<br />
==Сравнение с другими суффиксными структурами==<br />
Пусть <tex>s</tex> {{---}} строка, для которой строим соответствующую структуру, <tex>n = |s|</tex>, <tex>\Sigma</tex> {{---}} [[Основные_определения:_алфавит,_слово,_язык,_конкатенация,_свободный_моноид_слов;_операции_над_языками|алфавит]].<br />
<br />
{| class="wikitable"<br />
|-<br />
|<br />
| align="center" | '''Время работы'''<br />
| align="center" | '''Память'''<br />
|-<br />
| align="center" | [[Суффиксный бор]]<br />
| align="center" | <tex>O(n ^ 2)</tex><br />
| align="center" | <tex>O(n^2 + n |\Sigma|)</tex><br />
|-<br />
| align="center" | [[Сжатое суффиксное дерево]]<br />
| align="center" | <tex>O(n \log{|\Sigma|})</tex><br />
| align="center" | <tex>O(n |\Sigma|)</tex><br />
|-<br />
| align="center" | [[Суффиксный массив]]<br />
| align="center" | <tex>O((n + |\Sigma|) \log{n})</tex><br />
| align="center" | <tex>O(n + |\Sigma|)</tex><br />
|-<br />
| align="center" | Суффиксный автомат<br />
| align="center" | <tex>O(n \log{|\Sigma|})</tex><br />
| align="center" | <tex>O(n)</tex><br />
|}<br />
<br />
==См. также==<br />
* [[Автомат для поиска образца в тексте]]<br />
* [[Алгоритм Ахо-Корасик]]<br />
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]<br />
<br />
==Источники информации==<br />
* Maxime Crochemore, Christophe Hancart, Thierry Lecroq {{---}} Algorithms on Strings<br />
* [http://codeforces.com/blog/entry/22420| А. Кульков {{---}} Лекция по суффиксным структурам]<br />
* [http://e-maxx.ru/algo/suffix_automata MAXimal :: algo :: Суффиксный автомат]<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Структуры данных]]<br />
[[Категория: Поиск подстроки в строке]]<br />
[[Категория: Точный поиск]]<br />
[[Категория: Автоматы и регулярные языки]]</div>Hx