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

Курс "Алгоритмы на последовательностях молекул", весна 2004.
Лекция 4: Сопоставление множеств и алгоритм Ахо-Корасик.
Изложение: Пекка Килпеляйнен, Университет Куопио, Факультет Информатики.
Перевод с английского: Михаил Дворкин, Школа Стайвесант, Нью-Йорк.

Сопоставление множеств и алгоритм Ахо-Корасик*

* Маргарет Корасик - женщина, ее фамилию склонять не следует. Название "Алгоритм Ахо-Корасика" неверно.

Задача точного сопоставления множеств

В задаче точного сопоставления множеств (exact set matching problem) требуется обнаружить все появления шаблонов из множества P = {P₁,...,P_k} в тексте T[1..m].
Пусть n = Σ_i=1^k |P_i|.
Задача точного сопоставления множеств может быть решена за время
O (|P₁| + m + ... + |P_k| + m) = O (n + km),
если применить k раз любой алгоритм, работающий за линейное время.
Алгоритм Ахо-Корасик (АК) (Aho-Corasick algorithm) (AC) - классическое решение задачи точного сопоставления множеств. Он работает за время O (n + m + z) , где z - количество появлений шаблонов в T.
АК основан на структуре данных "дерево ключевых слов" (keyword tree).

Дерево ключевых слов (бор)

Дерево ключевых слов (или "бор") (keyword tree, trie) для множества шаблонов P - это дерево с корнем K, такое что:
1. Каждое ребро e в K отмечено одним символом.
2. Всякие два ребра, исходящие из одной вершины, имеют разные метки.
Определим метку вершины v как конкатенацию меток ребер, составляющих путь из корня в v, и обозначим ее L (v).
3. Для каждого шаблона P_i из множества P есть вершина v, такая что L (v) = P_i.
4. Метка каждой вершины-листа является шаблоном из множества P.

Пример дерева ключевых слов (бора)

Дерево ключевых слов для P = {he, she, his, hers}:

Бор - хороший способ хранения словаря строк.

Построение бора

Начинаем с дерева из одной вершины (корня); добавляем шаблоны P_i один за другим:
Следуем из корня по ребрам, отмеченным буквами из P_i, пока возможно.
Если P_i заканчивается в v, сохраняем идентификатор P_i (например, i) в v.
Если ребра, отмеченного очередной буквой P_i нет, то создаем новые ребра и вершины для всех оставшихся символов P_i.
Это занимает, очевидно, O (|P₁| + ... + |P_k|) = O (n) времени.

Поиск строки в бору

Поиск строки S в бору: начинаем в корне, идем по ребрам, отмеченным символами S, пока возможно.
Если с последним символом S мы приходим в вершину с сохраненным идентификатором, то S - слово из словаря.
Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки S в словаре нет.
Ясно, что это занимает O (|S|) времени. Таким образом, бор - это эффективный способ хранить словарь и искать в нем слова.
Теперь перейдем от бора к автомату (automaton), чтобы добиться поиска шаблонов в тексте за линейное время.

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

Состояния: узлы бора.
Начальное состояние: корень, обозначим его 0.
Действия автомата определяются тремя функциями, определенными для всех состояний:
1. Функция goto g (s, a) указывает, в какое состояние переходить из данного состояния s при просмотре символа a.
Если ребро (u, v) отмечено символом a, то g (u, a) = v;
g (0, a) = 0 для всех символов a, которыми не отмечено ни одно ребро, выходящее из корня.
~>Автомат остается в корне, пока просматриваются побочные символы.
При всех остальных аргументах g пусть выдает -1.
2. Функция неудачи f (s) указывает, в какое состояние переходить при просмотре неподходящего символа.
Рассмотрим метку вершины s и найдем самый длинный суффикс этой метки, такой, что с него начинается некоторый шаблон из множества P. Тогда f (s) пусть указывает на вершину, метка которой - этот суффикс.
3. Выходная функция out (s) выдает множество шаблонов, которые обнаруживаются при переходе в состояние s.

Пример автомата АК

Пунктиром обозначены переходы при неудаче (значения функции f); те, которые не показаны, ведут в корень.

Поиск шаблонов с помощью автомата АК

  q := 0; // начальное состояние - корень.
  for i := 1 to m do
    while g (q, T [i]) = -1 do
      q := f (q);
    q := g (q, T [i]);
    if out (q) ≠ 0 then print i, out (q);
  endfor;

Пример:
Поищите шаблоны в тексте "ushers" с помощью приведенного выше автомата.

Эффективность поиска АК

Теорема. Поиск шаблонов в тексте T [1..m] с помощью автомата АК занимает O (m + z) времени, где z - количество появлений шаблонов.
Доказательство. При просмотре каждого символа мы совершаем один переход по функции goto и, возможно, несколько переходов по функции неудачи.
После каждого goto мы либо остаемся в корне, либо переходим в очередное состояние, глубина которого на 1 больше глубины предыдущего состояния.
~>Глубина состояния увеличивается не более m раз.
Каждый переход по функции неудачи приближает нас к корню (длина метки вершины заведомо уменьшается), значит, количество таких переходов не может превосходить m.
z появлений шаблонов могут быть отслежены за суммарное время O (z) (если о каждом из них сообщать за константное время, например, сохраняя его номер и позицию в тексте).

Построение автомата АК

Автомат АК строится в два этапа.

Этап I:

1. Строим бор для словаря P.
При добавлении каждого слова P_i из P, вершине v с меткой P_i, сопоставим out (v) := {P_i}
2. Закончим построение функции goto, добавив несуществующие переходы из корня: g (0, a) = 0 для всех символов a, не отмечающих ни одного ребра, выходящего из корня. Это также можно сделать неявно.
Если алфавит фиксирован, этап I занимает O (n) времени.

Результат этапа I:

Этап II:

  Q := пустая очередь
  для каждого символа a, отмечающего хоть одно ребро из корня [g (0, a) ≠ 0]
     f (g (0, a)) := 0
    добавить в очередь Q вершину g (0, a)
  пока очередь Q не пуста
    взять вершину r из очереди Q
    для каждого символа a, отмечающего хоть одно ребро из вершины r [g (r, a) ≠ -1]
      u := g (r, a)
      добавить в очередь Q вершину u
      v := f (r)
      пока g (v, a) = -1
        v := f (v)
       f (u) := g (v, a)
      out (u) := out (u)∪out (f (u))

Как же это работает?
Функция неудачи и выходная функция вычисляются для всех вершин в порядке обхода в ширину.
~>Когда мы работаем с вершиной, все вершины, находящиеся ближе, чем она, к корню (в т. ч. все те, метки которых короче, чем метка данной), уже обработаны.
Рассмотрим узлы r и u = g (r, a), т. е. r - родитель u, и L (u) = L (r) a.
Теперь нужно, чтобы f (u) указывало на ту вершину, метка которой является самым длинным суффиксом L (u), являющимся также началом некоторого шаблона из множества P. Эта вершина ищется путем просматривания вершин, метки которых являются все более и более короткими суффиксами L (r), пока не находится вершина v, для которой g (v, a) определено; тогда g (v, a) и присваивается f (u).
Кстати, и v, и g (v, a) могут быть корнем.
Теперь разберемся с out (u) := out (u)∪out (f (u)).
Это делается потому, что все шаблоны, распознаваемые при переходе в состояние f (u) (и только они) являются надлежащими суффиксами L (u) и должны быть отслежены при переходе в состояние u.

Время работы этапа II

Этап II тоже может быть выполнен за время O (n):
Обход в ширину сам по себе занимает время пропорциональное размеру дерева, т. е. O (n).
Сколько же времени требуется на переходы по функции f в самом внутреннем цикле?
Рассмотрим вершины u₁, ..., u_l, проходимые при введении в бор шаблона a₁, ..., a_l, и глубины вершин, на которые указывают их функции неудачи, обозначенные df(u₁), ..., df(u_l).
При этом df(u_i+1) ≤ df(u_i) + 1. Это значит, что значения df могут увеличиваться не более l раз за весь путь. С другой стороны каждое выполнение v := f (v) уменьшает значение df(u) как минимум на 1.
~>Итого при просчете функций f для вершин шаблона длины l совершается не более l переходов.
~>Для всех вершин будет совершено не более n переходов.
А много ли времени нужно на выполнение out (u) := out (u)∪out (f (u))?
Нет: множества обнаруживаемых шаблонов можно хранить в виде связных списков, так что операция объединения выполняется за константное время.
(Все шаблоны в out (f (u)) короче, чем L (u), которая (возможно) является единственным членом out (u) перед объединением).

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

Пусть φ - маска, обозначающая любой одиночный символ.
Например, шаблон abφφcφ встречается на позициях 2 и 8 строки xabvccababcax.
Если количество φ ограничено сверху константой, то шаблоны с масками могут быть выявлены за линейное время. Для этого надо обнаружить безмасочные куски шаблона Q:
Пусть {Q₁, ..., Q_k} - набор подстрок Q, разделенных масками, и пусть l₁, ..., l_k - их стартовые позиции в Q.
1. for i := 1 to m do C [i] := 0;
2. Используя АК, находим подстроки Q: когда находим Q_i в тексте T на позиции j, увеличиваем на единицу C [j - l_i + 1].
3. Каждое i, для которого C [i] = k, является стартовой позицией появления шаблона Q.

Сложность поиска шаблонов с масками алгоритмом АК

Предобработка: O (m + n) (Σ_i=1^k|Q_i| ≤ |Q| = n)
Поиск: O (m + z), где z - количество появлений.
Каждое появление подстроки Q увеличивает значение одной ячейки C на 1, и значение каждой ячейки может увеличиваться до k раз.
~>Может быть не более km появлений. ( = O (m), если k ограничено константой.)
Итого, если количество φ ограничено константой, поиск шаблонов с масками выполняется за время O (n + m).

Сайт создан в системе uCoz