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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача алгоритма)
(Пример реализации)
Строка 47: Строка 47:
 
Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).<br /><br />
 
Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).<br /><br />
 
'''Структура вершины:'''
 
'''Структура вершины:'''
  struct Node {
+
  '''struct''' Node
     Node* son[SZ];        <font color=green>// массив сыновей; SZ - это размер алфавита</font>
+
     '''Node*''' son[SZ];        <font color=green>// массив сыновей; SZ - это размер алфавита</font>
     Node* go[SZ];        <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии)</font>
+
     '''Node*''' go[SZ];        <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>
     Node* up;            <font color=green>// сжатая суффиксная ссылка</font>
+
     '''Node*''' up;            <font color=green>// сжатая суффиксная ссылка</font>
     char charToParent;    <font color=green>// символ, ведущий к родителю</font>
+
     '''char''' charToParent;    <font color=green>// символ, ведущий к родителю</font>
     bool leaf;            <font color=green>// флаг, является ли вершина терминалом</font>
+
     '''bool''' leaf;            <font color=green>// флаг, является ли вершина терминалом</font>
     std::vector<int> leafPatternNumber;  <font color=green>// номера образцов, за которые отвечает терминал</font>
+
     '''vector <int>''' leafPatternNumber;  <font color=green>// номера образцов, за которые отвечает терминал</font>
};
+
 
 
'''Функция, для вычисления суффиксной ссылки:'''
 
'''Функция, для вычисления суффиксной ссылки:'''
  Node* getSuffLink(Node* v) {
+
  '''Node*''' getSuffLink(v : '''Node*''')  
     if (!v->suffLink) {   <font color=green>// если суффиксная ссылка ещё не вычислена</font>
+
     '''if''' ('''not'''(v->suffLink))   <font color=green>// если суффиксная ссылка ещё не вычислена</font>
        if (v == root || v->parent == root) {
+
        '''if''' (v = root '''or''' v->parent = root)
             v->suffLink = root;
+
             v->suffLink = root
        } else {
+
          '''else'''
             v->suffLink = getGo(getSuffLink(v->parent), v->charToParent);
+
             v->suffLink = getGo(getSuffLink(v->parent), v->charToParent)
        }
+
     '''return''' v->suffLink
    }
+
   
     return v->suffLink;
 
  }
 
 
'''Функция, для вычисления перехода:'''
 
'''Функция, для вычисления перехода:'''
  Node* getGo(Node* v, char c) {
+
  '''Node*''' getGo(v : '''Node*''', c : '''char''')  
    if (!v->go[c]) {      <font color=green>// если переход по символу c ещё не вычислен</font>
+
    '''if''' (not(v->go[c]))    <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];
        } else {
+
          '''else'''
 
             v->go[c] = (v == root) ? root : getGo(getSuffLink(v), c);
 
             v->go[c] = (v == root) ? root : getGo(getSuffLink(v), c);
        }
+
     '''return''' v->go[c];
    }
+
   
     return v->go[c];
 
  }
 
 
'''Функция, для вычисления сжатой суффиксной ссылки:'''
 
'''Функция, для вычисления сжатой суффиксной ссылки:'''
  Node* getUp(Node* v) {
+
  '''Node*''' getUp(c : '''Node*''')
     if (!v->up) {         <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
+
     '''if''' (not(v->up))         <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
         if (getSuffLink(v)->leaf) {
+
         '''if''' (getSuffLink(v)->leaf)  
             v->up = getSuffLink(v);
+
             v->up = getSuffLink(v)
        } else if (getSuffLink(v) == root) {
+
          '''else''' '''if''' (getSuffLink(v) = root)  
             v->up = root;
+
             v->up = root
        } else {
+
          '''else'''
             v->up = getUp(getSuffLink(v));
+
             v->up = getUp(getSuffLink(v))
        }
+
     '''return''' v->up
    }
+
 
     return v->up;
 
}
 
 
'''Функция, для добавление образца в бор:'''
 
'''Функция, для добавление образца в бор:'''
  void addString(std::string const& s, int patternNumber) {
+
  '''fun''' addString(s : '''string const&''', patternNumber : '''int''')
     Node* cur = root;
+
     '''Node*''' cur = root;
     for (int i = 0; i < s.length(); ++i) {
+
     '''for''' ('''int''' i = 0..s.length - 1)
         char c = s[i] - 'a';
+
         '''char''' c = s[i] - 'a';
         if (cur->son[c] == 0) {
+
         '''if''' (cur->son[c] = 0)  
 
             cur->son[c] = new Node;
 
             cur->son[c] = new Node;
 
             <font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font>
 
             <font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font>
             cur->son[c]->suffLink = 0;
+
             cur->son[c]->suffLink = 0
             cur->son[c]->up = 0;
+
             cur->son[c]->up = 0
             cur->son[c]->parent = cur;
+
             cur->son[c]->parent = cur
             cur->son[c]->charToParent = c;
+
             cur->son[c]->charToParent = c
             cur->son[c]->leaf = false;
+
             cur->son[c]->leaf = ''false''
        }
+
         cur = cur->son[c]
         cur = cur->son[c];
+
     cur->leaf = '''true'''
    }
+
     cur->leafPatternNumber.push_back(patternNumber)
     cur->leaf = true;
 
     cur->leafPatternNumber.push_back(patternNumber);
 
}
 
 
'''Функция, для процессинга текста (поиск, встречается образец или нет):'''
 
'''Функция, для процессинга текста (поиск, встречается образец или нет):'''
  void processText(std::string const& t, std::vector<bool>& found) {   <font color=green>// found - это вектор, длина которого равна количеству образцов</font>
+
  '''fun''' processText(t : '''string const&''', found : '''vector<bool>&''')  <font color=green>// found - это вектор, длина которого равна количеству образцов</font>
     found.assign(w, false);   <font color=green>// w - количество образцов</font>
+
     found.assign(w, '''false''')  <font color=green>// w - количество образцов</font>
     Node* cur = root;
+
     '''Node*''' cur = root
     for (int i = 0; i < t.length(); ++i) {
+
     '''for''' ('''int''' i = 0..t.length - 1)  
         char c = t[i] - 'a';
+
         '''char''' c = t[i] - 'a'
         cur = getGo(cur, c);
+
         cur = getGo(cur, c)
         for (int j = 0; j < cur->leafPatternNumber.size(); ++j) {
+
         '''for''' ('''int''' j = 0..cur->leafPatternNumber.size - 1)  
             found[cur->leafPatternNumber[j]] = true;
+
             found[cur->leafPatternNumber[j]] = '''true'''
        }
 
 
         <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
 
         <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
 
             обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
 
             обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
 
             и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */</font>
 
             и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */</font>
    }
 
}
 
 
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
 
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
 
  
 
== Поиск шаблонов с масками ==
 
== Поиск шаблонов с масками ==

Версия 22:24, 11 мая 2015

Задача алгоритма

Найти для каждого образца из заданного множества образцов, размером [math]k[/math] суммарной длины [math]m[/math], все его вхождения в текст за время [math]O(m)[/math] и [math]O(mk)[/math] памяти.

Шаг 1

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

Пример построенного бора

Бор для набора образцов [math]\{he,\ she,\ his,\ hers\}[/math]:
Aho-corasick1.jpg

Шаг 2

Превращаем бор в автомат.
Узлы бора становятся состояниями автомата; корень — начальное состояние.
Узлы бора, в которых заканчиваются образцы, становятся терминалами.

Для переходов по автомату заведём в узлах несколько функций:

  • [math]parent(u)[/math] — возвращает родителя вершины [math]u[/math];
  • [math]\pi(u) = \delta(\pi(parent(u)), c)[/math] — суффиксная ссылка; здесь [math]u[/math] — сын [math]parent(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]. Обозначение: [math][u][/math] — слово, приводящее в вершину [math]u[/math] в боре.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.

Пример автомата Ахо-Корасик

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

Шаг 3

Построение сжатых суффиксных ссылок.
[math]up(u) = \begin{cases} \pi(u)\text{, if $\pi(u)$ is terminal;}\\ \emptyset\text{, if $\pi(u)$ is root;}\\ up(\pi(u))\text{, else.} \end{cases}[/math] — сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.

Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии.

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

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

Пример реализации

Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).

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

struct Node
    Node* son[SZ];        // массив сыновей; SZ - это размер алфавита
    Node* go[SZ];         // массив переходов (запоминаем переходы в ленивой рекурсии)
    Node* parent;         // вершина родитель
    Node* suffLink;       // суффиксная ссылка (вычисляем в ленивой рекурсии)
    Node* up;             // сжатая суффиксная ссылка
    char charToParent;    // символ, ведущий к родителю
    bool leaf;            // флаг, является ли вершина терминалом
    vector <int> leafPatternNumber;   // номера образцов, за которые отвечает терминал

Функция, для вычисления суффиксной ссылки:

Node* getSuffLink(v : Node*) 
    if (not(v->suffLink))   // если суффиксная ссылка ещё не вычислена
       if (v = root or v->parent = root)
            v->suffLink = root
          else
            v->suffLink = getGo(getSuffLink(v->parent), v->charToParent)
    return v->suffLink

Функция, для вычисления перехода:

Node* getGo(v : Node*, c : char) 
   if (not(v->go[c]))    // если переход по символу c ещё не вычислен
        if (v->son[c]) 
            v->go[c] = v->son[c];
         else 
            v->go[c] = (v == root) ? root : getGo(getSuffLink(v), c);
    return v->go[c];

Функция, для вычисления сжатой суффиксной ссылки:

Node* getUp(c : Node*)
    if (not(v->up))         // если сжатая суффиксная ссылка ещё не вычислена
        if (getSuffLink(v)->leaf) 
            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&, patternNumber : int)
    Node* cur = root;
    for (int i = 0..s.length - 1)
        char c = s[i] - 'a';
        if (cur->son[c] = 0) 
            cur->son[c] = new Node;
            /* здесь также нужно обнулить указатели на переходы и сыновей */
            cur->son[c]->suffLink = 0
            cur->son[c]->up = 0
            cur->son[c]->parent = cur
            cur->son[c]->charToParent = c
            cur->son[c]->leaf = false
        cur = cur->son[c]
    cur->leaf = true
    cur->leafPatternNumber.push_back(patternNumber)

Функция, для процессинга текста (поиск, встречается образец или нет):

fun processText(t : string const&, found : vector<bool>&)   // found - это вектор, длина которого равна количеству образцов
    found.assign(w, false)   // w - количество образцов
    Node* cur = root
    for (int i = 0..t.length - 1) 
        char c = t[i] - 'a'
        cur = getGo(cur, c)
        for (int j = 0..cur->leafPatternNumber.size - 1) 
            found[cur->leafPatternNumber[j]] = true
        /* В этом месте кода должен выполняться переход по сжатой суффиксной ссылке getUp(cur). Для вершины,
           обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
           и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */

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

Поиск шаблонов с масками

Постановка задачи

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

Алгоритм поиска

Для того чтобы найти все вхождения в текст заданного шаблона с масками [math]Q[/math], необходимо обнаружить вхождения в текст всех его безмасочных кусков.
Пусть [math]\{[/math][math]Q_1[/math], ..., [math]Q_k[/math][math]\}[/math] — набор подстрок [math]Q[/math], разделенных масками, и пусть [math]l_1[/math], ..., [math]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]\{[/math][math]Q_1[/math], ..., [math]Q_k[/math][math]\}[/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].

См. также

Источники информации