Алгоритм Ахо-Корасик — различия между версиями
(→Шаг 2. Преобразование бора) |
(→Пример автомата Ахо-Корасик: Replace back to tex, to the same style as in the beginning of the article) |
||
(не показано 37 промежуточных версий 5 участников) | |||
Строка 1: | Строка 1: | ||
{{Задача | {{Задача | ||
− | |definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст | + | |definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст. |
}} | }} | ||
Строка 9: | Строка 9: | ||
====Пример построенного бора==== | ====Пример построенного бора==== | ||
− | Бор для набора строк <tex> \{ \textbf{he}, \textbf{she}, \textbf{his}, \textbf{hers}\} </tex>:<br /> | + | Бор для набора строк <tex> \{ \textbf{he},\ \textbf{she},\ \textbf{his},\ \textbf{hers}\} </tex>:<br /> |
[[Файл:Бор.jpg]] | [[Файл:Бор.jpg]] | ||
=== Шаг 2. Преобразование бора === | === Шаг 2. Преобразование бора === | ||
Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br /> | Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br /> | ||
− | Узлы бора можно понимать как состояния автомата, а корень как начальное состояние.<br /> | + | Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br /> |
− | Узлы бора, в которых заканчиваются | + | Узлы бора, в которых заканчиваются строки, становятся терминальными.<br /> |
Для переходов по автомату заведём в узлах несколько функций:<br /> | Для переходов по автомату заведём в узлах несколько функций:<br /> | ||
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br /> | *<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br /> | ||
− | *<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} суффиксная ссылка | + | *<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка''', и существует переход из <tex>\mathrm{parent}(u)</tex> в <tex>u</tex> по символу <tex>c</tex>;<br /> |
*<tex>\delta(u, c) = | *<tex>\delta(u, c) = | ||
\begin{cases} | \begin{cases} | ||
Строка 28: | Строка 28: | ||
<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>. | ||
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]]. | Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]]. | ||
+ | |||
+ | Из определений выше можно заметить два следующих факта: | ||
+ | * функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов; | ||
+ | * для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня. | ||
+ | Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии. | ||
==== Пример автомата Ахо-Корасик ==== | ==== Пример автомата Ахо-Корасик ==== | ||
Строка 33: | Строка 38: | ||
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень. | Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень. | ||
− | Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора | + | Суффиксная ссылка для каждой вершины <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. Построение сжатых суффиксных ссылок === | ===Шаг 3. Построение сжатых суффиксных ссылок === | ||
+ | При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки. | ||
+ | |||
<tex>up(u) = | <tex>up(u) = | ||
\begin{cases} | \begin{cases} | ||
Строка 41: | Строка 48: | ||
\varnothing,&\text{if $\pi(u)$ is root;}\\ | \varnothing,&\text{if $\pi(u)$ is root;}\\ | ||
up(\pi(u)), &\text{else.} | up(\pi(u)), &\text{else.} | ||
− | \end{cases}</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. | + | \end{cases}</tex> |
− | + | ||
+ | где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии. | ||
== Использование автомата == | == Использование автомата == | ||
− | По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.<br /> | + | Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.<br /> |
== Пример реализации == | == Пример реализации == | ||
− | Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />< | + | Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br /> |
+ | <tex>k</tex> {{---}} размер алфавита. | ||
+ | |||
'''Структура вершины:''' | '''Структура вершины:''' | ||
'''struct''' Node: | '''struct''' Node: | ||
− | '''Node''' son[k] | + | '''Node''' son[k] <font color=green>// массив сыновей</font> |
− | '''Node''' go[k] | + | '''Node''' go[k] <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font> |
− | '''Node''' parent | + | '''Node''' parent <font color=green>// вершина родитель</font> |
− | '''Node''' suffLink | + | '''Node''' suffLink <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font> |
− | '''Node''' up | + | '''Node''' up <font color=green>// сжатая суффиксная ссылка</font> |
− | '''char''' charToParent | + | '''char''' charToParent <font color=green>// символ, ведущий к родителю</font> |
− | '''bool''' isLeaf | + | '''bool''' isLeaf <font color=green>// флаг, является ли вершина терминалом</font> |
− | '''vector<int>''' leafPatternNumber | + | '''vector<int>''' leafPatternNumber <font color=green>// номера строк, за которые отвечает терминал</font> |
− | '''Функция | + | '''Функция для вычисления суффиксной ссылки:''' |
'''Node''' getSuffLink('''Node''' v): | '''Node''' getSuffLink('''Node''' v): | ||
− | '''if''' '' | + | '''if''' v.suffLink == ''null'' <font color=green>// если суффиксная ссылка ещё не вычислена</font> |
'''if''' v == root '''or''' v.parent == root | '''if''' v == root '''or''' v.parent == root | ||
v.suffLink = root | v.suffLink = root | ||
Строка 69: | Строка 79: | ||
'''return''' v.suffLink | '''return''' v.suffLink | ||
− | '''Функция | + | '''Функция для вычисления перехода:''' |
'''Node''' getLink('''Node''' v, '''char''' c): | '''Node''' getLink('''Node''' v, '''char''' c): | ||
− | '''if | + | '''if''' v.go[c] == ''null'' <font color=green>// если переход по символу c ещё не вычислен</font> |
'''if''' v.son[c] | '''if''' v.son[c] | ||
v.go[c] = v.son[c] | v.go[c] = v.son[c] | ||
Строка 80: | Строка 90: | ||
'''return''' v.go[c] | '''return''' v.go[c] | ||
− | '''Функция | + | '''Функция для вычисления сжатой суффиксной ссылки:''' |
'''Node''' getUp('''Node''' v): | '''Node''' getUp('''Node''' v): | ||
− | '''if''' '' | + | '''if''' v.up == ''null'' <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font> |
'''if''' getSuffLink(v).isLeaf | '''if''' getSuffLink(v).isLeaf | ||
v.up = getSuffLink(v) | v.up = getSuffLink(v) | ||
Строка 91: | Строка 101: | ||
'''return''' v.up | '''return''' v.up | ||
− | '''Функция | + | '''Функция для добавления строки в бор:''' |
− | '''fun''' addString('''string | + | '''fun''' addString('''string''' s, '''int''' patternNumber): |
'''Node''' cur = root | '''Node''' cur = root | ||
'''for''' i = 0 '''to''' s.length - 1 | '''for''' i = 0 '''to''' s.length - 1 | ||
− | '''char''' c = s[i] | + | '''char''' c = s[i] |
'''if''' cur.son[c] == 0 | '''if''' cur.son[c] == 0 | ||
cur.son[c] = Node | cur.son[c] = Node | ||
Строка 106: | Строка 116: | ||
cur = cur.son[c] | cur = cur.son[c] | ||
cur.isLeaf = ''true'' | cur.isLeaf = ''true'' | ||
− | cur.leafPatternNumber. | + | cur.leafPatternNumber.pushBack(patternNumber) |
− | '''Функция | + | '''Функция для процессинга текста (поиск, встречается строка или нет):''' |
− | '''fun''' processText('''string | + | '''fun''' processText('''string''' t): |
− | |||
'''Node''' cur = root | '''Node''' cur = root | ||
'''for''' i = 0 '''to''' t.length - 1 | '''for''' i = 0 '''to''' t.length - 1 | ||
'''char''' c = t[i] - 'a' | '''char''' c = t[i] - 'a' | ||
cur = getLink(cur, c) | cur = getLink(cur, c) | ||
− | |||
− | |||
<font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины, | <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины, | ||
обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки | обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки | ||
− | и так до корня | + | и так до корня. */</font> |
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет. | Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет. | ||
== Оптимизации == | == Оптимизации == | ||
+ | Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст: | ||
− | + | # '''Сброс сжатых суффиксных ссылок для посещённых вершин.''' | |
+ | #: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку. | ||
+ | # '''Сброс пометки терминальной вершины.''' | ||
+ | #: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов. | ||
== Поиск шаблонов с масками == | == Поиск шаблонов с масками == | ||
Строка 130: | Строка 141: | ||
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR> | |definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR> | ||
}} | }} | ||
− | Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex> | + | Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>7</tex> строки <tex>xabvccababcax</tex>. |
=== Алгоритм поиска === | === Алгоритм поиска === |
Текущая версия на 19:42, 19 января 2020
Задача: |
Дан набор строк в алфавите размера | суммарной длины . Необходимо найти для каждой строки все ее вхождения в текст.
Содержание
Алгоритм[править]
Шаг 1. Построение бора[править]
Строим бор из строк.
Построение выполняется за время , где — суммарная длина строк.
Пример построенного бора[править]
:Шаг 2. Преобразование бора[править]
Обозначим за
Узлы бора можно понимать как состояния автомата, а корень как начальное состояние.
Узлы бора, в которых заканчиваются строки, становятся терминальными.
Для переходов по автомату заведём в узлах несколько функций:
- — функция перехода.
Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.
Суффиксная ссылка , если — максимальный суффикс , .
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.
Из определений выше можно заметить два следующих факта:
- функция перехода определена через суффиксную ссылку, а суффиксная ссылка — через функию переходов;
- для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.
Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.
Пример автомата Ахо-Корасик[править]
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
Суффиксная ссылка для каждой вершины
— это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине . Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины с соответствующей ей строкой максимальным подходящим суффиксом является строка . Видим, что такая строка заканчивается в вершине . Следовательно суффиксной ссылкой вершины для является вершина .Шаг 3. Построение сжатых суффиксных ссылок[править]
При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.
где
— сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.Использование автомата[править]
Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа
Пример реализации[править]
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).
— размер алфавита.
Структура вершины:
struct Node: Node son[k] // массив сыновей Node go[k] // массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок Node parent // вершина родитель Node suffLink // суффиксная ссылка (вычисляем в ленивой рекурсии) Node up // сжатая суффиксная ссылка char charToParent // символ, ведущий к родителю bool isLeaf // флаг, является ли вершина терминалом vector<int> leafPatternNumber // номера строк, за которые отвечает терминал
Функция для вычисления суффиксной ссылки:
Node getSuffLink(Node v): if v.suffLink == null // если суффиксная ссылка ещё не вычислена 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 // если переход по символу c ещё не вычислен 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 // если сжатая суффиксная ссылка ещё не вычислена 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 /* здесь также нужно обнулить указатели на переходы и сыновей */ 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) /* В этом месте кода должен выполняться переход по сжатой суффиксной ссылке getUp(cur). Для вершины, обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки и так до корня. */
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
Оптимизации[править]
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
- Сброс сжатых суффиксных ссылок для посещённых вершин.
- Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
- Сброс пометки терминальной вершины.
- В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
Поиск шаблонов с масками[править]
Задача: |
Пусть | — маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.
Например, шаблон
, который содержит в себе три маски, встречается на позициях и строки .Алгоритм поиска[править]
Для того чтобы найти все вхождения в текст заданного шаблона с масками
Пусть — набор подстрок
, разделенных масками, и пусть — их стартовые позиции в . Например, шаблон содержит две подстроки без масок и и их стартовые позиции соответственно и . Для алгоритма понадобится массив . — количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции . Тогда появление подстроки в тексте на позиции будет означать возможное появление шаблона на позиции .
- Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона
- Каждое
Рассмотрим подстроку текста
Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время , где — суммарная длина подстрок, то есть длина шаблона, — длина текста, — количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву и просмотреть значения ячеек за время .