Изменения

== {{Задача алгоритма |definition ==Найти для каждого образца из заданного множества образцов все его вхождения Дан набор строк в текст за время алфавите размера <tex>O(m+n+a)k</tex>, где суммарной длины <tex>m</tex> - суммарная длина образцов, <tex>n</tex> - длина текста, <tex>a</tex> - размер ответа (количество пар). В худшем случае <tex>a=nk</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 />

1) *<tex>\mathrm{parent}(u)</tex> {{- --}} возвращает родителя вершины <tex>u</tex>;<br />2) *<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{- --}} '''суффиксная ссылка; здесь ''', и существует переход из <tex>\mathrm{parent}(u)</tex> - сын в <tex>parent(u)</tex> по символу <tex>c</tex>;<br />3) *<tex>\delta(u, c) =

v, &\text{, if $v$ is son by symbol $c$ in trie;}\\ root, &\text{if $u$ is root and $u$ has no child by symbol $c$ in trie}\\ \delta(\pi(u), c), &\text{, else.} \end{cases}</tex> {{--- }} функция перехода.Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.<br /><br />Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{--- }} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. ОбозначениеФункции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]]. Из определений выше можно заметить два следующих факта: * функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии. ==== Пример автомата Ахо-Корасик ====[[Файл:axo.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<br /tex>. Функции перехода ===Шаг 3. Построение сжатых суффиксных ссылок ===При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.

\pi(u), &\text{, if $\pi(u)$ is terminal;}\\ \emptysetvarnothing,&\text{, if $\pi(u)$ is root;}\\ up(\pi(u)), &\text{, else.} \end{cases}</tex>  где <tex>up</tex> {{- --}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.

Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцыстроки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему образцы строки тоже отмечаем.<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> '''Node''' up <font color=green>// сжатая суффиксная ссылка</font> '''char''' charToParent <font color=green>// символ, ведущий к родителю</font> '''bool''' isLeaf <font color=green>// флаг, является ли вершина терминалом</font> '''vector<int>''' leafPatternNumber <font color=green>// номера строк, за которые отвечает терминал</font> '''Функция для вычисления суффиксной ссылки:''' '''Node''' getSuffLink('''Node''' v): '''if''' v.suffLink == ''null'' <font color=green>// если суффиксная ссылка ещё не вычислена</font> '''if''' v == root '''or''' v.parent == root v.suffLink = root '''else''' v.suffLink = getLink(getSuffLink(v.parent), v.charToParent) '''return''' v.suffLink '''Функция для вычисления перехода:''' '''Node''' getLink('''Node''' v, '''char''' c): ''Примечание'if''' 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] = getLink(getSuffLink(v), c) '''return''' v.go[c] '''Функция для вычисления сжатой суффиксной ссылки:''' '''Node''' getUp('''Node''' v): '''if''' v.up == ''null'' <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font> '''if''' getSuffLink(v).isLeaf v.up = getSuffLink(v) '''else''' '''if''' getSuffLink(v) == root v.up = root '''else''' v.up = getUp(getSuffLink(v)) '''return''' v.up '''Функция для добавления строки в бор:''' '''fun''' addString('''string''' s, '''int''' patternNumber): '''Node''' cur = root '''for''' i = 0 '''to''' s.length - 1 '''char''' c = s[i] '''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].isLeaf = ''false'' cur = cur.son[c] cur.isLeaf = ''true'' cur.leafPatternNumber.pushBack(patternNumber)'''Функция для процессинга текста (поиск, встречается строка или нет):''' '''fun''' processText('''string''' t): '''Node''' cur = root '''for''' i = 0 '''to''' t.length - 1 '''char''' c = t[i] - 'a' cur = getLink(cur, c) <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины, обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки и так до корня. */</font>Кроме этих функций требуется найти инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет. == Оптимизации ==Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст, то существенно : # '''Сброс сжатых суффиксных ссылок для посещённых вершин.''' #: Существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.# '''Сброс пометки терминальной вершины.''' #: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов. == Поиск шаблонов с масками == {{Задача|definition = Пусть <tex>\varphi</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> {{---}} набор подстрок<tex>Q</tex>, разделенных масками, и пусть <tex>\{ l_1, \dots, l_k \}</tex> {{---}} их стартовые позиции в <tex>Q</tex>. Например, шаблон <tex>ab\varphi\varphi c\varphi</tex> содержит две подстроки без масок <tex>ab</tex> и <tex>c</tex> и их стартовые позиции соответственно <tex>1</tex> и <tex>5</tex>. Для алгоритма понадобится массив <tex>C</tex>. <tex>C[i]</tex> {{---}} количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции <tex>i</tex>. Тогда появление подстроки <tex>Q_i</tex> в тексте на позиции <tex>j</tex> будет означать возможное появление шаблона на позиции <tex>j - l_i + 1</tex>.<BR># Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона <tex>Q</tex>: когда находим <tex>Q_i</tex> в тексте <tex>T</tex> на позиции <tex>j</tex>, увеличиваем на единицу <tex>C[j - l_i + 1]</tex>.<BR># Каждое <tex>i</tex>, для которого <tex>C[i] = k</tex>, является стартовой позицией появления шаблона <tex>Q</tex> в тексте.<BR>Рассмотрим подстроку текста <tex>T[i \dots i+n-1]</tex>. Равенство <tex>C[i] = k</tex> будет означать, что подстроки текста <tex> T[i + l_1 \dots i + l_1 + |Q_1| - 1], T[i + l_2 \dots i + l_2 + |Q_2| - 1]</tex> и так далее будут равны соответственно безмасочным подстрокам шаблона <tex>\{Q_1, \dots , Q_k \}</tex>. Остальная часть шаблона является масками, поэтому шаблон входит в текст на позиции <tex>i</tex>.<BR>Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время <tex>O(m+n+a)</tex>, где <tex>n</tex> {{---}} суммарная длина подстрок, то есть длина шаблона, <tex>m</tex> {{---}} длина текста, <tex>a</tex> {{---}} количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву <tex>C</tex> и просмотреть значения ячеек за время <tex>O (m)</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 :: Алгоритм Ахо-Корасик] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Поиск подстроки в строке]][[Категория: Точный поиск]]