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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Схема преобразования одних суффиксных структур в другие[1]

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

В дальнейших работах на эту тему была обнаружена тесная связь суффиксного автомата с суффиксными деревьями[1][3], а сам концепт суффиксного автомата подвергся различным обобщениям. Так были введены сжатый суффиксный автомат, получаемый из исходного процедурой сжатия, аналогичной той, которая применяется к суффиксному бору для получения суффиксного дерева[4], а также обобщённый суффиксный автомат, который строится для набора слов и принимает слова, являющиеся суффиксами хотя бы одного из данных[5].

С помощью суффиксного автомата можно эффективно решать такие задачи как поиск подстроки в строке, определение наибольшей общей подстроки двух и более строк и другие[6]. Суффиксные автоматы нашли своё применение в таких прикладных задачах, как сжатие данных[7], идентификация музыки по записанным фрагментам[8][9] и сопоставление геномных последовательностей[10].

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

Дэвид Хаусслер
Ансельм Блумер, на доске изображён CDAWG для строк ababc и abcab

Концепция суффиксного автомата была представлена группой учёных из денверского и колорадского университетов Ансельмом Блумером, Анджеем Эренфехтом[en], Дэвидом Хаусслером[en], Россом МакКоннеллом и Джанет Блумер в 1983 г., хотя связанные с ним структуры встречались ранее в работах Вайнера[11], Пратта[12] и Слисенко[en][13], посвящённых алгоритмам построения суффиксных деревьев. В той же работе Блумер и др. показали, что построенный по слову автомат содержит не больше состояний и не больше переходов, а также привели линейный алгоритм для его построения[2].

В 1983 г. Чен и Сейферас независимо разработали алгоритм построения суффиксного автомата, показывающий, что алгоритм Вайнера[11], предложенный в 1973 г. для построения суффиксного дерева слова , также строит суффиксный автомат для развёрнутого слова в качестве вспомогательной структуры[3]. В 1987 г. Блумер и др. по аналогии с суффиксным деревом описали сжатый суффикный автомат (англ. compact directed acyclic word graph, CDAWG)[4], получаемый из суффиксного автомата удалением состояний с полустепенью исхода, равной единице, а в 1997 г. Крошемор и Верин разработали линейный алгоритм для его непосредственного построения[14]. В 2001 г. Иненага и др. разработали линейный онлайн-алгоритм для построения сжатого суффиксного автомата[1], а также линейный алгоритм для построения сжатого суффиксного автомата для набора слов, заданного префиксным деревом[5].

Основные обозначения[править | править код]

При описании суффиксных автоматов и связанных с ними фактов и теорем часто используются обозначения из теории формальных языков в целом и теории автоматов в частности[15]:

  • Алфавит — конечное множество , из которого могут состоять слова. Его элементы называются символами;
  • Слово — конечная последовательность символов алфавита: , где для . Длина слова обозначается как ;
  • Множество всех слов обозначается как (здесь символ «*» несёт смысл звезды Клини), пустое слово (слово нулевой длины) — символом ;
  • Конкатенация (произведение) слов и обозначается как или и равна слову, получаемому приписыванию к справа, то есть, ;
  • Конкатенация копий слова обозначается как . В частности,  — нейтральный элемент для конкатенации, то есть, ;
  • Если слово представимо в виде , где то слова , и называют префиксом, суффиксом и подсловом (подстрокой) слова соответственно;
  • Если , то выражения и обозначают слова и соответственно;
  • Правым контекстом слова относительно языка называют множество . То есть, это множество слов , при приписывании которых к слову справа получается слово из языка ;
  • Соответственно, левым контекстом слова относительно называют множество . Правые и левые контексты иногда обозначают и соответственно;
  • Правые контексты индуцируют естественное отношение эквивалентности на множестве всех слов такое что . Если , то про них говорят, что они правоэквивалентны.

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

Как и любой конечный автомат, суффиксный автомат, заданный формальной пятёркой , может быть представлен в виде ориентированного графа (диаграммы) такого что[16]:

  • Множество вершин графа соответствует множеству состояний автомата ,
  • В графе выделена некоторая вершина, соответствующая начальному состоянию ,
  • В графе выделен набор вершин, соответствующих множеству финальных состояний ,
  • Множество дуг в графе соответствует множеству переходов , которое состоит из троек , где и (см. декартово произведение),
  • При этом переходу соответствует дуга из в , помеченная символом алфавита . Такой переход также обозначают как .

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

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

Основная статья: Минимизация ДКА

Для конечных автоматов имеет место утверждение, следующее из теоремы Майхилла — Нероуда[17][18]:

Минимальный автомат, распознающий язык может быть задан в явном виде следующим образом:

  • Алфавит остаётся без изменений,
  • Состояниям соответствуют правые контексты всех слов ,
  • Начальному состоянию соответствует правый контекст пустого слова ,
  • Финальным состояниям соответствуют правые контексты слов из языка ,
  • Переходы имеют вид , где и .

Полученный таким образом минимальный автомат определён однозначно с точностью до изоморфизма.

В случае суффиксного автомата язык состоит из суффиксов , поэтому правый контекст состоит из слов таких что — суффикс . Это позволяет сформулировать следующую лемму[19][20]:

Пусть — множество правых концов вхождений в .

Между элементами множеств и есть следующее взаимно однозначное соответствие:

  • Если , то ;
  • Если , то .

Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть , тогда[20]:

  • Если у и есть хотя бы один общий элемент , то  — суффикс и, как следствие, и ;
  • Если , то , то есть, встречается в только в качестве суффикса ;
  • Если и  — суффикс , такой что , то .

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

Левым расширением строки называют самую длинную строку , имеющую тот же правый контекст, то есть, [21]. Длину самой длинной строки, принимаемой состоянием обозначают как .

Cуффиксной ссылкой от состояния называют указатель на состояние , содержащее наибольший суффикс , который не принимается состоянием .

В таких обозначениях можно сказать, что состояние принимает в точности все суффиксы , которые длиннее и не длиннее . Кроме того верно следующее[22]:

Суффиксные ссылки образуют дерево , которое можно задать явно следующим образом:

  1. Вершинам соответствуют левые расширения всех подстрок ,
  2. Рёбра соединяют вершины такие что и .

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

Основная статья: Суффиксное дерево

Аналогично правым контекстам можно ввести левые контексты и правые расширения , соответствующие самым длинным строкам, имеющим заданный левый контекст.

Если рассматривать их относительно языка префиксов строки , то можно получить, что[22]:

Суффиксное дерево строки может быть задано в явном виде следующим образом:

  • Вершинам соответствуют правые расширения всех подстрок ,
  • Рёбрам соответствуют тройки такие что и .

Здесь тройка значит, что на ребре из в записана строка .

Из чего непосредственно следует, что дерево суффиксных ссылок для автомата строки и суффиксное дерево строки изоморфны:

Размер[править | править код]

В суффиксном автомате строки не больше вершин и не больше рёбер, причём данные оценки достигаются на строках и соответственно[19].

Построение[править | править код]

Применения[править | править код]

Суффиксный автомат строки строится за время и может использоваться для решения таких задач как[6][23]:

  • Подсчёт количества различных подстрок за время в режиме онлайн,
  • Поиск самой длинной подстроки , которая входит в неё хотя бы два раза за время ,
  • Поиск наибольшей общей подстроки строк и за время ,
  • Подсчёт числа вхождений строки в в качестве подстроки за время ,
  • Поиск всех вхождений в за время , где  — количество вхождений.

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

Примечания[править | править код]

  1. 1 2 3 Иненага и др., 2005, Введение, с. 156—158
  2. 1 2 Блумер и др., 1984, Аннотация, с. 109
  3. 1 2 Чен, Сейферас, 1985, Аннотация, с. 97
  4. 1 2 Блумер и др., 1987, Аннотация, с. 578
  5. 1 2 Иненага и др., 2001, Аннотация, с. 1
  6. 1 2 Крошемор, Ханкарт, 1997, Суффиксные автоматы как автоматы для сопоставления образцов, с. 39—41
  7. Ямамото и др., 2014, Введение, с. 675
  8. Крошемор и др., 2003, Аннотация, с. 211
  9. Мохри и др., 2009, Аннотация, с. 3553
  10. Фаро, 2016, Аннотация, с. 145
  11. 1 2 Вайнер, 1973
  12. Пратт, 1973
  13. Слисенко, 1983
  14. Крошемор, Верин, 1997, Аннотация, с. 192
  15. 1 2 Крошемор, Ханкарт, 1997, Условные обозначения, с. 3—6
  16. Серебряков и др., 2006, Конечные автоматы, с. 50—54
  17. Рубцов, 2019, Теорема Майхилла–Нероуда, с. 89—94
  18. Хопкрофт, Ульман, 1979, Свойства регулярных множеств, с. 65—68
  19. 1 2 Блумер и др., 1984, Минимальный автомат, с. 111—114
  20. 1 2 Крошемор, Ханкарт, 1997, Размеры и свойства, с. 27—31
  21. Иненага и др., 2005, Отношения эквивалентности на строках, с. 158—159
  22. 1 2 Иненага и др., 2005, Индексные структуры для строк, с. 159—162
  23. Крошемор, Ханкарт, 1997, Суффиксные автоматы как индексы подстрок, с. 36—39

Литература[править | править код]