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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оптимизации)
(Пример автомата Ахо-Корасик: Replace back to tex, to the same style as in the beginning of the article)
 
(не показаны 22 промежуточные версии 5 участников)
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст за время <tex>O(m)</tex> и <tex>O(mk)</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‎]]
  
Строка 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>5</tex> с соответствующей ей строкой <tex>"she"</tex> максимальным суффиксом является строка <tex>"she"</tex>, но такой строки больше в нашем автомате нет. Возьмем второй по длине суффикс <tex>"he"</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</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> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br />
+
   \end{cases}</tex>
Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии.
+
 
 +
где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.
  
 
== Использование автомата ==
 
== Использование автомата ==
Строка 48: Строка 56:
  
 
== Пример реализации ==
 
== Пример реализации ==
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br /><br />
+
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
 +
<tex>k</tex> {{---}} размер алфавита.
 +
 
 
'''Структура вершины:'''
 
'''Структура вершины:'''
 
  '''struct''' Node:
 
  '''struct''' Node:
     '''Node''' son[k]                                <font color=green>// массив сыновей; k {{---}} это размер алфавита</font>
+
     '''Node''' son[k]                                <font color=green>// массив сыновей</font>
     '''Node''' go[k]                                  <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии)</font>
+
     '''Node''' go[k]                                  <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font>
 
     '''Node''' parent                                <font color=green>// вершина родитель</font>
 
     '''Node''' parent                                <font color=green>// вершина родитель</font>
 
     '''Node''' suffLink                              <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
 
     '''Node''' suffLink                              <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
Строка 60: Строка 70:
 
     '''vector<int>''' leafPatternNumber              <font color=green>// номера строк, за которые отвечает терминал</font>
 
     '''vector<int>''' leafPatternNumber              <font color=green>// номера строк, за которые отвечает терминал</font>
  
'''Функция, для вычисления суффиксной ссылки:'''
+
'''Функция для вычисления суффиксной ссылки:'''
 
  '''Node''' getSuffLink('''Node''' v):
 
  '''Node''' getSuffLink('''Node''' v):
     '''if''' v.suffLink = '''null'''                        <font color=green>// если суффиксная ссылка ещё не вычислена</font>
+
     '''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''' '''not''' v.go[c]                               <font color=green>// если переход по символу c ещё не вычислен</font>
+
     '''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''' '''not''' v.up                                <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
+
     '''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''' s, '''int''' patternNumber):
 
  '''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
Строка 107: Строка 117:
 
     cur.isLeaf = ''true''
 
     cur.isLeaf = ''true''
 
     cur.leafPatternNumber.pushBack(patternNumber)
 
     cur.leafPatternNumber.pushBack(patternNumber)
'''Функция, для процессинга текста (поиск, встречается строка или нет):'''
+
'''Функция для процессинга текста (поиск, встречается строка или нет):'''
 
  '''fun''' processText('''string''' t):   
 
  '''fun''' processText('''string''' t):   
 
     '''Node''' cur = root
 
     '''Node''' cur = root
Строка 119: Строка 129:
  
 
== Оптимизации ==
 
== Оптимизации ==
# Сброс пометки терминальной вершины.
+
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
Если требуется найти только первое вхождение строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
+
 
# Cброс суперсуффиксных ссылок.
+
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.'''
Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин.
+
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
 +
# '''Сброс пометки терминальной вершины.'''
 +
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
  
 
== Поиск шаблонов с масками ==
 
== Поиск шаблонов с масками ==
Строка 129: Строка 141:
 
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
 
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
 
}}
 
}}
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>8</tex> строки <tex>xabvccababcax</tex>.  
+
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>7</tex> строки <tex>xabvccababcax</tex>.  
  
 
=== Алгоритм поиска ===
 
=== Алгоритм поиска ===

Текущая версия на 19:42, 19 января 2020

Задача:
Дан набор строк в алфавите размера [math]k[/math] суммарной длины [math]m[/math]. Необходимо найти для каждой строки все ее вхождения в текст.


Алгоритм[править]

Шаг 1. Построение бора[править]

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

Пример построенного бора[править]

Бор для набора строк [math] \{ \textbf{he},\ \textbf{she},\ \textbf{his},\ \textbf{hers}\} [/math]:
Бор.jpg

Шаг 2. Преобразование бора[править]

Обозначим за [math][u][/math] слово, приводящее в вершину [math]u[/math] в боре.
Узлы бора можно понимать как состояния автомата, а корень как начальное состояние.
Узлы бора, в которых заканчиваются строки, становятся терминальными.
Для переходов по автомату заведём в узлах несколько функций:

  • [math]\mathrm{parent}(u)[/math] — возвращает родителя вершины [math]u[/math];
  • [math]\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)[/math]суффиксная ссылка, и существует переход из [math]\mathrm{parent}(u)[/math] в [math]u[/math] по символу [math]c[/math];
  • [math]\delta(u, c) = \begin{cases} 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}[/math] — функция перехода.

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

Из определений выше можно заметить два следующих факта:

  • функция перехода определена через суффиксную ссылку, а суффиксная ссылка — через функию переходов;
  • для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.

Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.

Пример автомата Ахо-Корасик[править]

Axo.jpg
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.

Суффиксная ссылка для каждой вершины [math]u[/math] — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине [math]u[/math]. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины [math]5[/math] с соответствующей ей строкой [math]\textbf{she}[/math] максимальным подходящим суффиксом является строка [math]\textbf{he}[/math]. Видим, что такая строка заканчивается в вершине [math]2[/math]. Следовательно суффиксной ссылкой вершины для [math]5[/math] является вершина [math]2[/math].

Шаг 3. Построение сжатых суффиксных ссылок[править]

При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.

[math]up(u) = \begin{cases} \pi(u), &\text{if $\pi(u)$ is terminal;}\\ \varnothing,&\text{if $\pi(u)$ is root;}\\ up(\pi(u)), &\text{else.} \end{cases}[/math]

где [math]up[/math] — сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.

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

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

Пример реализации[править]

Ниже представлена реализация некоторых функций (используется ленивая рекурсия).
[math]k[/math] — размер алфавита.

Структура вершины:

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). Для вершины,
           обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
           и так до корня. */

Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.

Оптимизации[править]

Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:

  1. Сброс сжатых суффиксных ссылок для посещённых вершин.
    Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
  2. Сброс пометки терминальной вершины.
    В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.

Поиск шаблонов с масками[править]

Задача:
Пусть [math]\varphi[/math] — маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.

Например, шаблон [math]ab\varphi\varphi c\varphi[/math], который содержит в себе три маски, встречается на позициях [math]2[/math] и [math]7[/math] строки [math]xabvccababcax[/math].

Алгоритм поиска[править]

Для того чтобы найти все вхождения в текст заданного шаблона с масками [math]Q[/math], необходимо обнаружить вхождения в текст всех его безмасочных кусков.
Пусть [math]\{Q_1, \dots, Q_k \}[/math] — набор подстрок [math]Q[/math], разделенных масками, и пусть [math]\{ l_1, \dots, l_k \}[/math] — их стартовые позиции в [math]Q[/math]. Например, шаблон [math]ab\varphi\varphi c\varphi[/math] содержит две подстроки без масок [math]ab[/math] и [math]c[/math] и их стартовые позиции соответственно [math]1[/math] и [math]5[/math]. Для алгоритма понадобится массив [math]C[/math]. [math]C[i][/math] — количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции [math]i[/math]. Тогда появление подстроки [math]Q_i[/math] в тексте на позиции [math]j[/math] будет означать возможное появление шаблона на позиции [math]j - l_i + 1[/math].

  1. Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона [math]Q[/math]: когда находим [math]Q_i[/math] в тексте [math]T[/math] на позиции [math]j[/math], увеличиваем на единицу [math]C[j - l_i + 1][/math].
  2. Каждое [math]i[/math], для которого [math]C[i] = k[/math], является стартовой позицией появления шаблона [math]Q[/math] в тексте.

Рассмотрим подстроку текста [math]T[i \dots i+n-1][/math]. Равенство [math]C[i] = k[/math] будет означать, что подстроки текста [math] T[i + l_1 \dots i + l_1 + |Q_1| - 1], T[i + l_2 \dots i + l_2 + |Q_2| - 1][/math] и так далее будут равны соответственно безмасочным подстрокам шаблона [math]\{Q_1, \dots , Q_k \}[/math]. Остальная часть шаблона является масками, поэтому шаблон входит в текст на позиции [math]i[/math].
Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время [math]O(m+n+a)[/math], где [math]n[/math] — суммарная длина подстрок, то есть длина шаблона, [math]m[/math] — длина текста, [math]a[/math] — количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву [math]C[/math] и просмотреть значения ячеек за время [math]O (m)[/math].

См. также[править]

Источники информации[править]