Изменения

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

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

4451 байт добавлено, 19 январь
Пример автомата Ахо-Корасик: Replace back to tex, to the same style as in the beginning of the article
{{Задача
|definition = Найти для каждого образца из заданного множества образцов, размером Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>, . Необходимо найти для каждой строки все его ее вхождения в текст за время <tex>O(m)</tex> и <tex>O(mk)</tex> памяти.
}}
==Алгоритм==
=== Шаг 1. Построение бора ===
Строим [[Бор|бор]] из строк.<br />
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина строк.
== Шаг 1 ==Строим [[Бор|бор]] из образцов.<br />Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина образцов. === Пример построенного бора ====Бор для набора образцов строк <tex> \{ \textbf{he}, \ \textbf{she}, \ \textbf{his}, \ \textbf{hers}\} </tex>:<br />
[[Файл:Бор.jpg‎]]
=== Шаг 2 . Преобразование бора ===Превращаем бор Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в автоматборе.<br />Узлы бора становятся состояниями можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата; ]], а корень {{---}} как начальное состояние.<br />Узлы бора, в которых заканчиваются образцыстроки, становятся терминаламитерминальными.<br /><br />
Для переходов по автомату заведём в узлах несколько функций:<br />
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />*<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка; здесь ''', и существует переход из <tex>\mathrm{parent}(u)</tex> {{---}} сын в <tex>parent(u)</tex> по символу <tex>c</tex>;<br />
*<tex>\delta(u, c) =
\begin{cases}
\delta(\pi(u), c), &\text{else.}
\end{cases}</tex> {{---}} функция перехода.
Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
<br> Суффиксная Из определений выше можно заметить два следующих факта:* функция перехода определена через суффиксную ссылку, а суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>через функию переходов;* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня. Обозначение: <tex>[u]</tex> {{---}} слово, приводящее в вершину <tex>u</tex> в боре.<br />Функции перехода Это позволяет реализовать функции поиска переходов по символу и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширинусуффиксных ссылок ленивым образом при помощи взаимной рекурсии==== Пример автомата Ахо-Корасик ====[[Файл:Aho-corasick2axo.jpg]]<br />
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <tex>\textbf{she}</tex> максимальным подходящим суффиксом является строка <tex>\textbf{he}</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex>. === Шаг 3 ==. Построение сжатых суффиксных ссылок===При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.<br /> 
<tex>up(u) =
\begin{cases}
\varnothing,&\text{if $\pi(u)$ is root;}\\
up(\pi(u)), &\text{else.}
\end{cases}</tex>  где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br />Сжатые Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут отыскиваться быть найдены при помощи ленивой рекурсии.
== Использование автомата ==
Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцыстроки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему образцы строки тоже отмечаем.<br />''Примечание.'' Если требуется найти только первое вхождение образца в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
== Пример реализации ==
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br /><tex>k<br /tex>{{---}} размер алфавита. 
'''Структура вершины:'''
'''struct''' Node: '''Node*''' son[SZk] <font color=green>// массив сыновей; SZ - это размер алфавита</font> '''Node*''' go[SZk] <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font> '''Node*''' parent <font color=green>// вершина родитель</font> '''Node*''' suffLink <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font> '''Node*''' up <font color=green>// сжатая суффиксная ссылка</font> '''char''' charToParent <font color=green>// символ, ведущий к родителю</font> '''bool''' leaf isLeaf <font color=green>// флаг, является ли вершина терминалом</font> '''vector <int>''' leafPatternNumber <font color=green>// номера образцовстрок, за которые отвечает терминал</font>
'''Функция, для вычисления суффиксной ссылки:''' '''Node*''' getSuffLink(v : '''Node*'''v) : '''if''' v.suffLink == '''notnull'''(v->suffLink) <font color=green>// если суффиксная ссылка ещё не вычислена</font> '''if''' v == root '''or''' v->.parent == root v->.suffLink = root '''else''' v->.suffLink = getGogetLink(getSuffLink(v->.parent), v->.charToParent) '''return''' v->.suffLink
'''Функция, для вычисления перехода:''' '''Node*''' getGogetLink(v : '''Node*'''v, c : '''char'''c) : '''if''' '''not'''(v->.go[c]) == ''null'' <font color=green>// если переход по символу c ещё не вычислен</font> '''if''' v->.son[c] v->.go[c] = v->.son[c] '''else''' '''if''' v == root v->.go[c] = root '''else''' v->.go[c] = getGogetLink(getSuffLink(v), c) '''return''' v->.go[c];
'''Функция, для вычисления сжатой суффиксной ссылки:''' '''Node*''' getUp(v : '''Node*'''v): '''if''' v.up == ''null'not'''(v->up) <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font> '''if''' getSuffLink(v)->leaf.isLeaf v->.up = getSuffLink(v) '''else''' '''if''' getSuffLink(v) == root v->.up = root '''else''' v->.up = getUp(getSuffLink(v)) '''return''' v->.up
'''Функция, для добавление образца добавления строки в бор:''' '''fun''' addString(s : '''string const&'''s, patternNumber : '''int'''patternNumber): '''Node*''' cur = root '''for''' i = 0..'''to''' s.length - 1 '''char''' c = s[i] - 'a' '''if''' cur->.son[c] == 0 cur->.son[c] = Node
<font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font>
cur->.son[c]->.suffLink = 0 cur->.son[c]->.up = 0 cur->.son[c]->.parent = cur cur->.son[c]->.charToParent = c cur->.son[c]->leaf .isLeaf = ''false'' cur = cur->.son[c] cur->leaf .isLeaf = ''true'' cur->.leafPatternNumber.push_backpushBack(patternNumber)'''Функция, для процессинга текста (поиск, встречается образец строка или нет):''' '''fun''' processText(t : '''string const&''', found t): '''vector<bool>&''') <font color=green>// found - это вектор, длина которого равна количеству образцов</font> found.assign(w, ''false'') <font color=green>// w - количество образцов</font> '''Node*''' cur = root '''for''' i = 0..'''to''' t.length - 1
'''char''' c = t[i] - 'a'
cur = getGogetLink(cur, c) '''for''' j = 0..cur->leafPatternNumber.size - 1 found[cur->leafPatternNumber[j]] = ''true''
<font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */</font>
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
 
== Оптимизации ==
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
 
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.'''
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
# '''Сброс пометки терминальной вершины.'''
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
== Поиск шаблонов с масками ==
 
{{Задача
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ.Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>8</tex> строки <tex>xabvccababcax</tex>. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
}}
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>7</tex> строки <tex>xabvccababcax</tex>.
=== Алгоритм поиска ===
 
Для того чтобы найти все вхождения в текст заданного шаблона с масками <tex>Q</tex>, необходимо обнаружить вхождения в текст всех его безмасочных кусков.<BR>
Пусть <tex>\{Q_1, \dots, Q_k \}</tex> {{---}} набор подстрок
*[http://e-maxx.ru/algo/aho_corasick MAXimal :: algo :: Алгоритм Ахо-Корасик]
*[http://aho-corasick.narod.ru Сопоставление множеств и алгоритм Ахо-Корасик]
*[http://codeforces.com/blog/entry/14854?locale=ru Codeforces :: Алгоритм Ахо-Корасик]
*[https://habrahabr.ru/post/198682/ Habr :: Алгоритм Ахо-Корасик]
*[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE_%E2%80%94_%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA Wiki :: Алгоритм Ахо-Корасик]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Точный поиск]]
Анонимный участник

Навигация