Алгоритм Ахо-Корасик — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Первая версия статьи (статья ещё не дописана))
 
(Продолжение статьи)
Строка 19: Строка 19:
 
     v\text{, if $v$ is son by symbol $c$ in trie;}\\
 
     v\text{, if $v$ is son by symbol $c$ in trie;}\\
 
     \delta(\pi(u), c)\text{, else.}
 
     \delta(\pi(u), c)\text{, else.}
   \end{cases}</tex> - функция перехода;<br />
+
   \end{cases}</tex> - функция перехода.<br /><br />
4) <tex>up(u) =  
+
Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> - максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> - слово, приводящее в вершину <tex>u</tex> в боре.<br />
 +
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.
 +
 
 +
== Шаг 3 ==
 +
Построение сжатых суффиксных ссылок.<br />
 +
<tex>up(u) =  
 
   \begin{cases}
 
   \begin{cases}
 
     \pi(u)\text{, if $\pi(u)$ is terminal;}\\
 
     \pi(u)\text{, if $\pi(u)$ is terminal;}\\
 
     \emptyset\text{, if $\pi(u)$ is root;}\\
 
     \emptyset\text{, if $\pi(u)$ is root;}\\
 
     up(\pi(u))\text{, else.}
 
     up(\pi(u))\text{, else.}
   \end{cases}</tex> - сжатая суффиксная ссылка.<br /><br />
+
   \end{cases}</tex> - сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.
Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> - максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> - слово, приводящее в вершину <tex>u</tex> в боре.
+
 
 +
== Использование автомата ==
 +
По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцы, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему образцы тоже отмечаем.

Версия 03:42, 14 марта 2011

Эта статья находится в разработке!

Задача алгоритма

Найти для каждого образца из заданного множества образцов все его вхождения в текст за время [math]O(m+n+a)[/math], где [math]m[/math] - суммарная длина образцов, [math]n[/math] - длина текста, [math]a[/math] - размер ответа (количество пар). В худшем случае [math]a=nk[/math], но он случается редко.

Шаг 1

Строим бор из образцов. См. Бор.
Построение выполняется за время [math]O(m)[/math], где [math]m[/math] - суммарная длина образцов.

Шаг 2

Превращаем бор в автомат.
Узлы бора становятся состояниями автомата; корень - начальное состояние.
Узлы бора, в которых заканчиваются образцы, становятся терминалами.

Для переходов по автомату заведём в узлах несколько функций:
1) [math]parent(u)[/math] - возвращает родителя вершины [math]u[/math];
2) [math]\pi(u) = \delta(\pi(parent(u)), c)[/math] - суффиксная ссылка; здесь [math]u[/math] - сын [math]parent(u)[/math] по символу [math]c[/math];
3) [math]\delta(u, c) = \begin{cases} v\text{, if $v$ is son by symbol $c$ in trie;}\\ \delta(\pi(u), c)\text{, else.} \end{cases}[/math] - функция перехода.

Суффиксная ссылка [math]\pi(u) = v[/math], если [math][v][/math] - максимальный суффикс [math][u][/math], [math][v]\neq[u][/math]. Обозначение: [math][u][/math] - слово, приводящее в вершину [math]u[/math] в боре.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.

Шаг 3

Построение сжатых суффиксных ссылок.
[math]up(u) = \begin{cases} \pi(u)\text{, if $\pi(u)$ is terminal;}\\ \emptyset\text{, if $\pi(u)$ is root;}\\ up(\pi(u))\text{, else.} \end{cases}[/math] - сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.

Использование автомата

По очереди просматриваем символы текста. Для очередного символа [math]c[/math] переходим из текущего состояния [math]u[/math] в состояние, которое вернёт функция [math]\delta(u, c)[/math]. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцы, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему образцы тоже отмечаем.