Изменения

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

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

1145 байт добавлено, 19:42, 19 января 2020
Пример автомата Ахо-Корасик: Replace back to tex, to the same style as in the beginning of the article
====Пример построенного бора====
Бор для набора строк <tex> \{ \textbf{he}, \ \textbf{she}, \ \textbf{his}, \ \textbf{hers}\} </tex>:<br />
[[Файл:Бор.jpg‎]]
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
 
Из определений выше можно заметить два следующих факта:
* функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;
* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.
Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.
==== Пример автомата Ахо-Корасик ====
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора; : для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <tex>"\textbf{she"}</tex> максимальным подходящим суффиксом является строка <tex>"she"</tex>, но такой строки больше в нашем автомате нет. Возьмем второй по длине суффикс <tex>"\textbf{he"}</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex> .
===Шаг 3. Построение сжатых суффиксных ссылок ===
При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.
 
<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 />Сжатые Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут отыскиваться быть найдены при помощи ленивой рекурсии.
== Использование автомата ==
== Пример реализации ==
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
<tex>k</tex> {{---}} это размер алфавита.
'''Структура вершины:'''
'''struct''' Node:
'''Node''' son[k] <font color=green>// массив сыновей</font>
'''Node''' go[k] <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font>
'''Node''' parent <font color=green>// вершина родитель</font>
'''Node''' suffLink <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
'''vector<int>''' leafPatternNumber <font color=green>// номера строк, за которые отвечает терминал</font>
'''Функция, для вычисления суффиксной ссылки:'''
'''Node''' getSuffLink('''Node''' v):
'''if''' v.suffLink == ''null'' <font color=green>// если суффиксная ссылка ещё не вычислена</font>
'''return''' v.suffLink
'''Функция, для вычисления перехода:'''
'''Node''' getLink('''Node''' v, '''char''' c):
'''if''' v.go[c] == ''null'' <font color=green>// если переход по символу c ещё не вычислен</font>
'''return''' v.go[c]
'''Функция, для вычисления сжатой суффиксной ссылки:'''
'''Node''' getUp('''Node''' v):
'''if''' v.up == ''null'' <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
'''return''' v.up
'''Функция, для добавление добавления строки в бор:'''
'''fun''' addString('''string''' s, '''int''' patternNumber):
'''Node''' cur = root
cur.isLeaf = ''true''
cur.leafPatternNumber.pushBack(patternNumber)
'''Функция, для процессинга текста (поиск, встречается строка или нет):'''
'''fun''' processText('''string''' t):
'''Node''' cur = root
== Оптимизации ==
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст: # '''Сброс сжатых суффиксных ссылок для посещённых вершин. Если требуется найти только первое вхождение строки в текст, то существенно ''' #: Существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.# '''Сброс пометки терминальной вершины. ''' #: В изначальном множестве образцов могут быть дублирующиеся строки. Если же таких строк будет многоМы можем хотеть из различать, то наш алгоритм будет очень долго работатьесли с одинаковыми строками связана разная мета-информация. Если же мы будем делать Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, когда обнаруживаем ее что сэкономит время на обновлении информации о вхождении образцов в первый разтекст. Тривиальным примером, то таким образом ускорим время работыв котором возникает ситуация долгой обработки, так как нас будет интересовать служит огромное множество образцов из одинаковых символов и текст только первое вхождениеиз этих символов.
== Поиск шаблонов с масками ==
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
}}
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>87</tex> строки <tex>xabvccababcax</tex>.
=== Алгоритм поиска ===
Анонимный участник

Навигация