Изменения

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

2484 байта добавлено, 01:38, 30 августа 2018

→‎Алгоритм

__TOC__

==Описание==

~~Детерминированным конечным автоматом называется пятёрка (~~Рассмотрим конечный алфавит <tex>A</tex>. Пусть <tex>A^*</tex> {{---}} набор слов в алфавите <tex>A</tex>. Суффиксный автомат <tex>\mathcal{A}</tex> {{---}} это набор <tex>S\langle Q, sA, ~~\Sigma~~i, T, \delta~~, T)~~\rangle</tex>), где* <tex>SQ</tex> {{---}} ~~множество~~ конечный набор состояний,* <tex>~~s \in S~~i</tex> {{---}} начальное состояние,* <tex>~~\Sigma~~T</tex> {{---}} ~~конечный алфавит~~набор терминальных состояний,* <tex>\delta ~~: S \times \Sigma \to S~~</tex> {{---}} функция ~~переходов,~~перехода. * Для <tex>T q \~~subset S~~in Q</tex> ~~{{---}} множество терминальных состояний.~~ ~~Суффиксный автомат~~ и <tex>a \in A</tex> ~~для строки~~ , <tex>s\delta(q, a)</tex> ~~представляет собой ациклический ориентированный граф~~определена, ~~с начальной вершиной~~ если состояние достижимо из <tex>q</tex> переходом по символу <tex>a</tex>. Функция перехода распространяется на слова и ~~множеством терминальных вершин~~<tex>\delta(q, ~~рёбра которого помечены символами~~ x)</tex>sобозначает, что если она существует, то состояние достигнуто после чтения слова <tex>x</tex> из состояния <tex>q</tex>.Автомат <tex>\mathcal{A}</tex> распознает язык <tex>\{x \in A^* : \delta(i, x) \in T \}</tex>.

Суффиксный автомат <tex>\mathcal{A}</tex> для строки <tex>s</tex> представляет собой [[Основные_определения_теории_графов|ациклический ориентированный граф]], с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами <tex>s</tex>:

* вершины этого графа {{---}} состояния автомата, а рёбра {{---}} переходы,

* каждый переход в автомате {{---}} ребро в графе, помеченное некоторым символом и все рёбра, исходящие из одной вершины имеют разные метки,

* одно из состояний называется начальным, из него достижимы все остальные состояния,

* одно или несколько состояний помечены как терминальные {{---}} если пройти от начального состояния до терминального по какому-либо пути и выписывать при этом символы на переходах, то получим один из суффиксов строки <tex>s</tex>.

[[Файл:Suffix_automaton_ex.png|540px|frame|center|Пример суффиксного автомата для строки <tex>abbab</tex>.]]

}}

Таким образом, ДКА является минимальным тогда и только тогда, когда правые контексты всех его состояний попарно различны.

В случае суффиксного автомата правый контекст <tex>X_a</tex> строки <tex>a</tex> взаимнооднозначно соответствует множеству правых позиций вхождений строки <tex>a</tex> в строку <tex>s</tex>. Таким образом, каждое состояние автомата принимает строки с одинаковым множеством правых позиций их вхождений и обратно, все строки с таким множеством позиций принимается этим состоянием.

==Построение==

Обозначим состояние <tex>\mathrm{last}</tex>, соответствующее текущей строке до добавления символа <tex>c</tex> (изначально <tex>\mathrm{last} = 0</tex>). Создадим новое состояние <tex>\mathrm{cur}</tex>, <tex>\mathrm{len(cur)} = \mathrm{len(last)} + 1</tex>. Рассмотрим все переходы из <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>.

Допустим, что мы остановились в состоянии <tex>p</tex>, из которого существует переход с символом <tex>c</tex>. Обозначим состояние, куда ведёт переход, через <tex>q</tex>. Рассмотрим два случая:

# Если <tex>\mathrm{len(p)} + 1 = \mathrm{len(q)}</tex>, то <tex>\mathrm{link(qcur)} = \mathrm{~~cur~~q}</tex>.

# В противном случае, создадим новое состояние <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>.

Обновим значение <tex>\mathrm{last} = \mathrm{cur}</tex>.

===Пример построения===

{| class = "wikitable"

! Изображение !! Описание

|-

|Изначально автомат состоит из одного начального состояния. <tex>\mathrm{last} = 0, \mathrm{len(0)} = 0</tex>

|-

|Добавляем символ <tex>a</tex>. Создаем состояние <tex>1</tex>. Переходов из начального состояния по символу <tex>a</tex> нет, перейти по суффиксным ссылкам некуда, значит добавим суффиксную ссылку <tex>\mathrm{link_{1}} = 0</tex>. <tex>\mathrm{last} = 1, \mathrm{len(1)} = 1</tex>

|-

|Добавляем символ <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>

|-

|Аналогично добавим символ <tex>c</tex> и обновим автомат. <tex>\mathrm{last} = 3, \mathrm{len(3)} = 3</tex>

|-

|Добавляем символ <tex>b</tex>. Добавим переход из <tex>3</tex> и перейдем по суффиксной ссылке в начальное состояние. Из состояния <tex>0</tex> существует переход по символу <tex>b</tex>

|-

|Рассмотрим состояние <tex>2</tex>, куда существует переход. Имеем <tex>\mathrm{len(0)} + 1 \neq \mathrm{len(2)}</tex>.

# Создаем новое состояние <tex>5</tex>.

# Перенаправим суффиксную ссылку из <tex>2</tex> в <tex>5</tex> и добавим ссылку из <tex>4</tex> в <tex>5</tex>. Перенаправим переход <tex>0 \rightarrow 2</tex> в состояние <tex>5</tex>.

|-

|Построение автомата завершено. Чтобы пометить терминальные вершины, найдём состояние, которое принимает строку <tex>abcb</tex> и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.

|-

==Реализация==

В приведённой ниже реализации используются следующие переменные:* ~~Переходы хранятся в массиве~~ <tex>\mathrm{edges[]}</tex> {{---}} массив отображений (ключ {{---}} символ, значение {{---}} номер состояния) ~~<tex>\mathrm{edges}</tex>~~с переходами,* ~~Суффиксные ссылки хранятся в массиве~~ <tex>\mathrm{link[]}</tex>{{---}} массив суффиксных ссылок, * ~~Длины строк хранятся в массиве~~ <tex>\mathrm{len[]}</tex>{{---}} массив длин строк,* ~~Функция~~ <tex>\mathrm{newState()}</tex> {{---}} функция, которая создаёт новое состояние и возвращает его номер,* ~~Функция~~ <tex>\mathrm{clone()}</tex> {{---}} функция, которая копирует состояние и возвращает номер нового состояния,* <tex>\mathrm{last}</tex> {{---}} последнее состояние.

'''func''' addChar(c''': char''')''':''' '''int''' cur = newState() // создаём новое состояние и ~~возвращаем~~ получаем его номер

'''int''' p = last

'''while''' p >= 0 '''and''' edges[p].find(c) == ''null''

edges[p][c] = cur

'''if''' p != -1

'''int''' q = edges[p][c]

'''if''' len[p] + 1 == len[q]

link[cur] = q

'''else'''

'''int''' new = clone(q) // скопируем состояние <tex>q</tex>и получим номер нового состояния

len[new] = len[p] + 1

link[q] = link[cur] = new

Построим суффиксный автомат для строки <tex>s</tex>.

Пусть текущее состояние {{---}} <tex>\mathrm{cur}</tex>, изначально равно <tex>0</tex> (начальному состоянию).

Будем по очереди обрабатывать символы строки <tex>p</tex>. Если из состояния <tex>\mathrm{cur}</tex> есть переход в по текущему символу, но то перейдем в новое состояние и повторим процедуру. Если перехода не существует, то <tex>p</tex> не является подстрокой <tex>s</tex>. Если успешно обработали все символы <tex>p</tex>, то она является подстрокой <tex>s</tex>. Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.

===Позиция первого вхождения строки===

}}

Построим суффиксный автомат для строки <tex>s</tex>.

~~Пройдем~~ Пройдём по строке <tex>t</tex> и для текущего символа будем искать длину наибольшей общей подстроки, которая заканчивается в текущей позиции. Для этого будем поддерживать <tex>v</tex> {{---}} текущее состояние и <tex>l</tex> {{---}} текущую длину совпадающей части. Изначально <tex>v = 0</tex>, <tex>l = 0</tex> {{---}} совпадение пустое. Рассматриваем текущий символ <tex>t_i</tex>. Если в автомате существует переход из текущего состояния по данному символу, то перейдем в новое состояние и увеличим длину <tex>l</tex> на <tex>1</tex>. Если перехода не существует, то попробуем минимально уменьшить длину совпадающей подстроки: перейдем по суффиксной ссылке из <tex>v</tex> в новое состояние и примем <tex>l = \mathrm{len(v)}</tex>. Повторим операцию до тех пор, пока не ~~найдем~~ найдём переход. Если по суффиксным ссылкам мы дошли до состояния, в которое ~~ведет~~ ведёт суффиксная ссылка начальной вершины, то это значит, что символа <tex>t_i</tex> нет в строке <tex>s</tex>. В таком случае примем <tex>v = l = 0</tex>, после чего перейдем к следующему символу строки <tex>t</tex>. Длиной наибольшей общей подстроки будет <tex>\mathrm{~~maxPos~~maxLen}</tex> {{---}} максимум из всех значений <tex>l</tex>, полученных в ходе работы алгоритма. Тогда ответом на задачу будет являться подстрока <tex>t[(\mathrm{maxPos} - \mathrm{maxLen} + 1) .. \mathrm{maxPos}]</tex>, где <tex>\mathrm{maxPos}</tex> {{---}} позиция, в которой достигнут максимум.

==Сравнение с другими суффиксными структурами==

* [[Автомат для поиска образца в тексте]]

* [[Алгоритм Ахо-Корасик]]

* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]

==Источники информации==

* Maxime Crochemore, Christophe Hancart, Thierry Lecroq {{---}} Algorithms on Strings

* [http://codeforces.com/blog/entry/22420| А. Кульков {{---}} Лекция по суффиксным структурам]

* [http://e-maxx.ru/algo/suffix_automata MAXimal :: algo :: Суффиксный автомат]

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Структуры данных]]

[[Категория: Поиск подстроки в строке]]

[[Категория: Точный поиск]]

[[Категория: Автоматы и регулярные языки]]

Анонимный участник

176.241.103.106

Изменения

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты