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

Схема преобразования одних суффиксных структур в другие

Суффиксный автомат (англ. suffix automaton, directed acyclic word graph, DAWG) — детерминированный конечный автомат, принимающий все суффиксы данной строки $S$ и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Автомат был впервые описан Блумером и др. в 1983 г., в той же работе впервые было показано, что размер суффиксного автомата линеен по длине строки, а также был предложен онлайн-алгоритм для построения автомата с линейным временем работы.

В 1985 г. Чен и Сейферас показали, что алгоритм Вайнера, предложенный в 1973 г. для построения суффиксного дерева строки $S$, также строит суффиксный автомат для развёрнутой строки $S$ в качестве вспомогательной структуры. В 1987 г. Блумер и др. по аналогии с суффиксным деревом описали сжатый суффикный автомат (англ. compact directed acyclic word graph, CDAWG), получаемый из суффиксного автомата удалением состояний с полустепенью исхода, равной единице, а в 1997 г. Крошемор и Верин разработали линейный алгоритм для его непосредственного построения. В 2001 г. Иненага и др. разработали линейный онлайн-алгоритм для построения сжатого суффиксного автомата, а также линейный алгоритм для построения сжатого суффиксного автомата для набора строк, заданного бором.

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

Как и любой конечный автомат, суффиксный автомат, заданный формальной пятёркой ${\mathcal {A}}=(\Sigma ,Q,q_{0},F,\delta )$ может быть представлен в виде ориентированного графа такого что:

• Множество вершин графа соответствует множеству состояний автомата $Q$,
• В графе выеделена некоторая вершина, соответствующая начальному состоянию $q_{0}\in Q$,
• В графе выделен набор вершин, соответствующих множеству финальных состояний $F\subset Q$,
• Множество дуг в графе соответствует множеству переходов $\delta \subset Q\times \Sigma \times Q$,
• При этом переходу $(q_{1},\sigma ,q_{2})\in \delta$ соответствует дуга из $q_{1}$ в $q_{2}$, помеченная символом алфавита $\sigma \in \Sigma$.

В таком графе вершины и дуги отождествляются с состояниями и переходами автомата соответственно. В таком естественном представлении автомат принимает строку $S=s_{1}s_{2}\dots s_{n}$ в том и только том случае если существует путь из начального состояния $q_{0}$ в некоторое финальное состояние $q\in F$ такой что если последовательно выписать символы, которые встретились на этом пути, то получится последовательность $s_{1},s_{2},\dots ,s_{n}$.

Контексты строк и состояний

Правым контекстом слова $\omega$ относительно языка $L$ называют множество $[\omega ]_{R}=\{\alpha |\omega \alpha \in L\}$. То есть, это множество строк $\alpha$, при приписывании которых к слову $\omega$ справа получается слово из языка $L$. Аналогичным образом определяется левый контекст $[\omega ]_{L}=\{\beta |\beta \omega \in L\}$. Также для каждого состояния автомата $q\in Q$ можно определить его правый контекст как множество слов $\alpha$, которые переводят $q$ в некоторое финальное состояние. Другими словами, это такие строки $\alpha$, что существует путь из $q$ в некоторое финальное состояние такой что символы, встретившиеся на этом пути образуют строку $\alpha$.

Если автомат ${\mathcal {A}}$ детерминированный, то каждому слову $\omega \in \Sigma ^{*}$ соответствует единственное состояние автомата $q(\omega )$ такое что из $q_{0}$ в $q(\omega )$ есть путь, символы на котором образуют слово $\omega$. При этом правые контексты $\omega$ и $q(\omega )$ по определению совпадают, откуда следует, что если $q(\alpha )=q(\beta )$, то $[\alpha ]_{R}=[\beta ]_{R}$. То есть, правые контексты слов, принимаемых одним и тем же состоянием совпадают.

В случае суффиксных автоматов из этого также следует, что строки, принимаемые одним и тем же состоянием, являются суффиксами друг друга.

Суффиксные ссылки

Пусть строка $\omega$ является самой длинной из строк, принимаемых состоянием суффиксного автомата $q$. Тогда суффиксная ссылка $link(q)$ от состояния $q$ указывает на состояние $q'$, которое принимает самый длинный суффикс $\omega$, который не принимается состоянием $q$. Суффиксные ссылки образуют дерево с корнем в начальном состоянии и несут важную роль при построении суффиксного автомата. Более того, дерево суффиксных ссылок суффиксного автомата для строки $S$ изоморфно суффиксному дереву для развёрнутой строки $S^{T}$, что наглядно демонстрирует следующая иллюстрация:

• Суффиксные структуры
• 
  Суффиксный автомат для строки abbcbc
• 
  Суффиксное дерево для строки cbcbba
  (дерево суффиксных ссылок для автомата строки abbcbc)

Применения

Суффиксный автомат строки $S$ строится за время $O(|S|)$ и может использоваться для решения таких задач как:

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

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