Су́ффиксный автома́т () — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой, что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин.
Суффиксный автомат был впервые описан группой учёных из Денверского и Колорадского университетов в 1983 году, они же показали, что размер автомата линейно зависит от длины , а также предложили для его построения с линейным временем работы. В дальнейших работах на эту тему была обнаружена тесная связь суффиксного автомата с суффиксными деревьями, а сама концепция суффиксного автомата получила различные обобщения. Так были введены сжатый суффиксный автомат, получаемый из исходного процедурой, аналогичной той, которая применяется к суффиксному бору для получения суффиксного дерева, а также обобщённый суффиксный автомат, который строится для набора слов и принимает слова, являющиеся суффиксами хотя бы одного из данных.
С помощью суффиксного автомата можно эффективно решать такие задачи как поиск подстроки в строке, определение наибольшей общей подстроки двух и более строк, и другие.
История Концепция суффиксного автомата была представлена группой учёных из Денверского и Колорадского университетов Ансельмом Блумером, , , Россом МакКоннеллом и Джанет Блумер в 1983 году, хотя связанные с ним структуры встречались ранее в работах Питера Вайнера, Вона Пратта и Анатолия Олесьевича Слисенко, посвящённых алгоритмам построения суффиксных деревьев. В той же работе Блумер и другие показали, что построенный по слову длины больше автомат содержит не больше состояний и не больше переходов, а также привели линейный алгоритм построения автомата.
В 1983 году Му Тянь Чэнь и Джоэл Сейферас независимо разработали алгоритм построения суффиксного автомата, показывающий, что алгоритм Вайнера, предложенный в 1973 году для построения суффиксного дерева слова , также строит суффиксный автомат для обращённого слова в качестве вспомогательной структуры. В 1987 году Блумер и другие, по аналогии с суффиксным деревом, описали сжатый суффикный автомат, получаемый из суффиксного автомата удалением нефинальных состояний с полустепенью исхода, равной единице, а в 1997 году и Рено Верин разработали линейный алгоритм для его прямого построения. В 2001 году Сюнсукэ Инэнага и другие разработали линейный онлайн-алгоритм для построения сжатого суффиксного автомата, а также линейный алгоритм для построения сжатого суффиксного автомата для набора слов, заданного префиксным деревом.
В своей исходной работе Блумер с коллегами определили описанную ими структуру как минимальный автомат, распознающий все подстроки (а не суффиксы) данного слова. Данную структуру они назвали ориентированным ациклическим графом слов (). Впоследствии данное название также использовалось как синоним — минимального автомата, распознающего произвольный конечный набор слов (не обязательно составляющих множество суффиксов или подстрок некоторой строки).
Обозначения При описании суффиксных автоматов и связанных с ними фактов и теорем часто используются обозначения из теории формальных языков в целом и теории автоматов в частности:
Алфавит — конечное множество , из которого могут состоять слова. Его элементы называются символами; Слово — конечная последовательность символов алфавита . Длина слова обозначается как ; Формальный язык — некоторое множество слов над заданным алфавитом; Язык всех слов обозначается как (здесь символ «*» несёт смысл звезды Клини), пустое слово (слово нулевой длины) — символом ; Конкатенация (произведение) слов и обозначается как или и равна слову, получаемому приписыванием к справа, то есть, ; Конкатенация языков и обозначается как или и равна множеству попарных конкатенаций ; Если слово представимо в виде , где , то слова , и называют префиксом, суффиксом и подсловом (подстрокой) слова соответственно; Если , то говорят, что слово входит (встречается) в как подслово. При этом и называются левой и правой позициями вхождения в соответственно.
Структура автомата Формально, детерминированный конечный автомат определяется набором из пяти элементов , где:
— алфавит, из которого состоят слова, распознаваемые автоматом, — множество состояний автомата, — начальное состояние автомата, — множество финальных состояний автомата, — функция переходов автомата, такая что для и либо не определена, либо указывает на состояние, в которое может быть произведён переход из по .
Чаще всего на практике конечные автоматы представляются в виде ориентированного графа (диаграммы), такого, что:
Множество вершин графа соответствует множеству состояний , В графе выделена некоторая вершина, соответствующая начальному состоянию , В графе выделен набор вершин, соответствующих множеству финальных состояний , Множество дуг в графе соответствует множеству переходов , При этом переходу соответствует дуга из в , помеченная символом алфавита . Такой переход также обозначают как .
В таком графе вершины и дуги отождествляются с состояниями и переходами автомата соответственно. Автомат принимает слово в том и только том случае, если существует путь из начального состояния в некоторое финальное состояние , такой что если сконкатенировать символы, встретившиеся на этом пути, то получится слово . Множество слов, которые принимает автомат, образуют язык этого автомата.
Состояния автомата Правым контекстом слова относительно языка называют множество . То есть это множество слов , при приписывании которых к слову справа получается слово из языка . Правые контексты индуцируют естественное отношение эквивалентности на множестве всех слов. Если язык может быть задан некоторым детерминированным конечным автоматом, то для него существует единственный, с точностью до изоморфизма, автомат, обладающий при этом наименьшим возможным числом состояний. Такой автомат называется минимальным для данного языка , теорема Майхилла — Нероуда позволяет задать его в явном виде:
В таких обозначениях, суффиксный автомат — это минимальный ДКА, принимающий язык суффиксов слова . Правый контекст слова относительно данного языка состоит из слов таких что — суффикс . Это позволяет сформулировать следующую лемму, определяющую взаимно-однозначное соответствие между правым контекстом слова и множеством позиций его вхождений в в качестве подслова:
Например, для слова и его подслова выполнено и . Неформально, состоит из слов, которые следуют за вхожениями до конца слова, а — из позиций этих вхождений. В этом примере, элементу соответствует слово . В то же время, слову соответствует элемент .
Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть , тогда:
Если у и есть хотя бы один общий элемент , то общий элемент также есть у и . Это, в свою очередь, значит, что — суффикс и потому и . В приведённом выше примере, и, как следствие, — суффикс , а также и ; Если , то , то есть встречается в только в качестве суффикса . Это видно на примере слов и , для которых и ; Если и — суффикс , такой что , то . В приведённом выше примере, , а «промежуточным» суффиксом является . И действительно, .
Таким образом, любое состояние суффиксного автомата принимает некоторую непрерывную цепочку вложенных друг в друга суффиксов наибольшей строки из этого состояния.
Левым расширением строки называют самую длинную строку , имеющую тот же правый контекст, что и . Длину самой длинной строки, принимаемой состоянием , обозначают как . Для него верно, что:
Суффиксной ссылкой от состояния называют указатель на состояние , содержащее наибольший суффикс , который не принимается состоянием .
В таких обозначениях можно сказать, что состояние принимает в точности все суффиксы , которые длиннее и не длиннее . Кроме того, верно следующее:
Связь с суффиксным деревом Префиксным деревом (или бором) называют корневое ориентированное дерево, дуги которого помечены символами таким образом, что из любой вершины этого дерева исходит не больше одной дуги, помеченной данным символом. Некоторые вершины в префиксном дереве помечены. Говорят, что префиксное дерево задаёт множество слов, определяемое путями из корня дерева в помеченные вершины. Таким образом, префиксные деревья представляют собой особую разновидность конечных автоматов, если рассматривать корень как начальное состояние, а помеченные вершины — как финальные состояния. Суффиксным бором слова называют префиксное дерево, задающее язык суффиксов этого слова. Суффиксным деревом называют дерево, получаемое из суффиксного бора процедурой сжатия, при которой последовательно идущие рёбра склеиваются если между ними находится нефинальная вершина, степень которой равна 2.
По определению, суффиксный автомат может быть получен минимизацией суффиксного бора. Кроме того, сжатый суффиксный автомат может быть получен как минимизацией суффиксного дерева (если считать, что символы алфавита — это слова на рёбрах дерева), так и сжатием обычного автомата. Однако, помимо очевидной связи между суффиксным автоматом и суффиксным деревом одной и той же строки, можно также установить некоторое соответствие между суффиксным автоматом строки и суффиксным деревом обращённой строки .
Аналогично правым контекстам можно ввести левые контексты и правые расширения , соответствующие самым длинным строкам, имеющим заданный левый контекст, а также отношение эквивалентности . Если рассматривать правые расширения относительно языка префиксов строки , то можно получить, что:
Из чего следует, что дерево суффиксных ссылок для автомата строки и суффиксное дерево строки изоморфны: Суффиксные структуры слов abbcbc и cbcbba
Аналогично левым расширениям, для правых расширений также может быть сформулирована структурная лемма:
Размер В суффиксном автомате строки длины не больше состояний и не больше переходов, причём данные оценки достигаются на строках и соответственно. Можно также сформулировать более сильное утверждение о связи числа состояний и переходов в автомате: , где и — это число переходов и состояний соответственно. Максимальные суффиксные автоматы
Построение Суффиксный автомат строки строится последовательным наращиванием слова, для которого он построен. Изначально имеется тривиальный автомат, построенный для пустого слова, а затем на каждом шаге к текущему слову добавляется один символ, что влечёт за собой перестройку состояний и переходов автомата.
Изменение состояний После приписывания нового символа к слову некоторые классы эквивалентности изменятся. Пусть — правый контекст слова относительно языка суффиксов слова . Тогда переход от к при приписывании символа к слову описывается следующей леммой: