Редактирование: Суффиксный автомат

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 6: Строка 6:
 
__TOC__
 
__TOC__
 
==Описание==
 
==Описание==
Рассмотрим конечный алфавит <tex>A</tex>. Пусть <tex>A^*</tex> {{---}} набор слов в алфавите <tex>A</tex>. Суффиксный автомат <tex>\mathcal{A}</tex> {{---}} это набор <tex>\langle Q, A, i, T, \delta \rangle</tex>, где
+
Детерминированным конечным автоматом называется пятёрка (<tex>S, s, \Sigma, \delta, T)</tex>), где
* <tex>Q</tex> {{---}} конечный набор состояний,
+
* <tex>S</tex> {{---}} множество состояний,
* <tex>i</tex> {{---}} начальное состояние,
+
* <tex>s \in S</tex> {{---}} начальное состояние,
* <tex>T</tex> {{---}} набор терминальных состояний,
+
* <tex>\Sigma</tex> {{---}} конечный алфавит,
* <tex>\delta</tex> {{---}} функция перехода.
+
* <tex>\delta : S \times \Sigma \to S</tex> {{---}} функция переходов,
Для <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>.
+
* <tex>T \subset S</tex> {{---}} множество терминальных состояний.
Автомат <tex>\mathcal{A}</tex> распознает язык <tex>\{x \in A^* : \delta(i, x) \in T \}</tex>.
+
 
 +
Суффиксный автомат <tex>A</tex> для строки <tex>s</tex> представляет собой ациклический ориентированный граф, с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами <tex>s</tex>.  
  
Суффиксный автомат <tex>\mathcal{A}</tex> для строки <tex>s</tex> представляет собой [[Основные_определения_теории_графов|ациклический ориентированный граф]], с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами <tex>s</tex>:
 
* вершины этого графа {{---}} состояния автомата, а рёбра {{---}} переходы,
 
* каждый переход в автомате {{---}} ребро в графе, помеченное некоторым символом и все рёбра, исходящие из одной вершины имеют разные метки,
 
* одно из состояний называется начальным, из него достижимы все остальные состояния,
 
* одно или несколько состояний помечены как терминальные {{---}} если пройти от начального состояния до терминального по какому-либо пути и выписывать при этом символы на переходах, то получим один из суффиксов строки <tex>s</tex>.
 
<br>
 
 
[[Файл:Suffix_automaton_ex.png|540px|frame|center|Пример суффиксного автомата для строки <tex>abbab</tex>.]]
 
[[Файл:Suffix_automaton_ex.png|540px|frame|center|Пример суффиксного автомата для строки <tex>abbab</tex>.]]
  
Строка 47: Строка 42:
 
}}
 
}}
 
Таким образом, ДКА является минимальным тогда и только тогда, когда правые контексты всех его состояний попарно различны.
 
Таким образом, ДКА является минимальным тогда и только тогда, когда правые контексты всех его состояний попарно различны.
В случае суффиксного автомата правый контекст <tex>X_a</tex> строки <tex>a</tex> взаимнооднозначно соответствует множеству правых позиций вхождений строки <tex>a</tex> в строку <tex>s</tex>. Таким образом, каждое состояние автомата принимает строки с одинаковым множеством правых позиций их вхождений и обратно, все строки с таким множеством позиций принимается этим состоянием.
+
В случае суффиксного автомата правый контекст <tex>X_a</tex> строки <tex>a</tex> взаимнооднозначно соответствует множеству правых позиций вхождений строки <tex>a</tex> в строку <tex>s</tex>. Таким образом, каждое состояние автомата принимает строки с одинаковым множеством правых позиций их вхождений и обратно, все строки с таким множеством позиций принимается этим состоянием.  
  
 
==Построение==
 
==Построение==
Строка 60: Строка 55:
 
<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>\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>
 
Допустим, что мы остановились в состоянии <tex>p</tex>, из которого существует переход с символом <tex>c</tex>. Обозначим состояние, куда ведёт переход, через <tex>q</tex>. Рассмотрим два случая:<br>
 
Допустим, что мы остановились в состоянии <tex>p</tex>, из которого существует переход с символом <tex>c</tex>. Обозначим состояние, куда ведёт переход, через <tex>q</tex>. Рассмотрим два случая:<br>
# Если <tex>\mathrm{len(p)} + 1 = \mathrm{len(q)}</tex>, то <tex>\mathrm{link(cur)} = \mathrm{q}</tex>.<br>
+
# Если <tex>\mathrm{len(p)} + 1 = \mathrm{len(q)}</tex>, то <tex>\mathrm{link(q)} = \mathrm{cur}</tex>.<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>.
 
# В противном случае, создадим новое состояние <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>.
 
Обновим значение <tex>\mathrm{last} = \mathrm{cur}</tex>.
 
 
===Пример построения===
 
===Пример построения===
 
{| class = "wikitable"
 
{| class = "wikitable"
Строка 95: Строка 89:
  
 
==Реализация==
 
==Реализация==
В приведённой ниже реализации используются следующие переменные:
+
* Переходы хранятся в массиве отображений (ключ {{---}} символ, значение {{---}} номер состояния) <tex>\mathrm{edges}</tex>,
* <tex>\mathrm{edges[]}</tex> {{---}} массив отображений (ключ {{---}} символ, значение {{---}} номер состояния) с переходами,
+
* Суффиксные ссылки хранятся в массиве <tex>\mathrm{link}</tex>,  
* <tex>\mathrm{link[]}</tex> {{---}} массив суффиксных ссылок,  
+
* Длины строк хранятся в массиве <tex>\mathrm{len}</tex>,
* <tex>\mathrm{len[]}</tex> {{---}} массив длин строк,
+
* Функция <tex>\mathrm{newState}</tex> создаёт новое состояние и возвращает его номер,
* <tex>\mathrm{newState()}</tex> {{---}} функция, которая создаёт новое состояние и возвращает его номер,
+
* Функция <tex>\mathrm{clone}</tex> копирует состояние и возвращает номер нового состояния.
* <tex>\mathrm{clone()}</tex> {{---}} функция, которая копирует состояние и возвращает номер нового состояния,
 
* <tex>\mathrm{last}</tex> {{---}} последнее состояние.
 
  
  '''func''' addChar(c ''': char''')''':'''
+
  '''func''' addChar(c)''':'''
     '''int''' cur = newState()                                      <font color="green">// создаём новое состояние и получаем его номер</font>  
+
     cur = newState()                                      <font color="green">// создаём новое состояние и возвращаем его номер</font>  
 
   
 
   
     '''int''' p = last
+
     p = last
 
     '''while''' p >= 0 '''and''' edges[p].find(c) == ''null''
 
     '''while''' p >= 0 '''and''' edges[p].find(c) == ''null''
 
         edges[p][c] = cur
 
         edges[p][c] = cur
Строка 112: Строка 104:
 
   
 
   
 
     '''if''' p != -1
 
     '''if''' p != -1
         '''int''' q = edges[p][c]
+
         q = edges[p][c]
 
         '''if''' len[p] + 1 == len[q]
 
         '''if''' len[p] + 1 == len[q]
 
             link[cur] = q
 
             link[cur] = q
 
         '''else'''
 
         '''else'''
             '''int''' new = clone(q)                                <font color="green">// скопируем состояние <tex>q</tex> и получим номер нового состояния</font>
+
             new = clone(q)                                <font color="green">// скопируем состояние <tex>q</tex></font>
 
             len[new] = len[p] + 1
 
             len[new] = len[p] + 1
 
             link[q] = link[cur] = new
 
             link[q] = link[cur] = new
Строка 132: Строка 124:
 
Построим суффиксный автомат для строки <tex>s</tex>.<br>
 
Построим суффиксный автомат для строки <tex>s</tex>.<br>
 
Пусть текущее состояние {{---}} <tex>\mathrm{cur}</tex>, изначально равно <tex>0</tex> (начальному состоянию).<br>
 
Пусть текущее состояние {{---}} <tex>\mathrm{cur}</tex>, изначально равно <tex>0</tex> (начальному состоянию).<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>.
+
Будем по очереди обрабатывать символы строки <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>.
  
 
===Позиция первого вхождения строки===
 
===Позиция первого вхождения строки===
Строка 157: Строка 149:
 
}}
 
}}
 
Построим суффиксный автомат для строки <tex>s</tex>.<br>
 
Построим суффиксный автомат для строки <tex>s</tex>.<br>
Пройдём по строке <tex>t</tex> и для текущего символа будем искать длину наибольшей общей подстроки, которая заканчивается в текущей позиции. Для этого будем поддерживать <tex>v</tex> {{---}} текущее состояние и <tex>l</tex> {{---}} текущую длину совпадающей части.<br>
+
Пройдем по строке <tex>t</tex> и для текущего символа будем искать длину наибольшей общей подстроки, которая заканчивается в текущей позиции. Для этого будем поддерживать <tex>v</tex> {{---}} текущее состояние и <tex>l</tex> {{---}} текущую длину совпадающей части.<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>
+
Изначально <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>
Длиной наибольшей общей подстроки будет <tex>\mathrm{maxLen}</tex> {{---}} максимум из всех значений <tex>l</tex>, полученных в ходе работы алгоритма. Тогда ответом на задачу будет являться подстрока <tex>t[(\mathrm{maxPos} - \mathrm{maxLen} + 1) .. \mathrm{maxPos}]</tex>, где <tex>\mathrm{maxPos}</tex> {{---}} позиция, в которой достигнут максимум.
+
Длиной наибольшей общей подстроки будет <tex>\mathrm{maxPos}</tex> {{---}} максимум из всех значений <tex>l</tex>, полученных в ходе работы алгоритма. Тогда ответом на задачу будет являться подстрока <tex>t[(\mathrm{maxPos} - \mathrm{maxLen} + 1) .. \mathrm{maxPos}]</tex>, где <tex>\mathrm{maxPos}</tex> {{---}} позиция, в которой достигнут максимум.
  
 
==Сравнение с другими суффиксными структурами==
 
==Сравнение с другими суффиксными структурами==
Строка 194: Строка 186:
 
==Источники информации==
 
==Источники информации==
 
* Maxime Crochemore, Christophe Hancart, Thierry Lecroq {{---}} Algorithms on Strings
 
* Maxime Crochemore, Christophe Hancart, Thierry Lecroq {{---}} Algorithms on Strings
* [http://codeforces.com/blog/entry/22420 А. Кульков {{---}} Лекция по суффиксным структурам]
+
* [http://codeforces.com/blog/entry/22420| А. Кульков {{---}} Лекция по суффиксным структурам]
 
* [http://e-maxx.ru/algo/suffix_automata MAXimal :: algo :: Суффиксный автомат]
 
* [http://e-maxx.ru/algo/suffix_automata MAXimal :: algo :: Суффиксный автомат]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Структуры данных]]
 
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Точный поиск]]
 
[[Категория: Точный поиск]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)