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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Ахо — Корасик — алгоритм поиска подстроки, разработанный Альфредом Ахо и Маргарет Корасик. Алгоритм реализует поиск множества подстрок из словаря в данной строке.

Принцип работы[править | править вики-текст]

Недетерминированный автомат для словаря {a, ab, bc, bca, c, caa}. Серые вершины промежуточные, белые конечные. Синие стрелки — суффиксные ссылки, зелёные — конечные.

Алгоритм строит конечный автомат, которому затем передаёт строку поиска. Автомат получает по очереди все символы строки и переходит по соответствующим рёбрам. Если автомат пришёл в конечное положение, соответствующая строка словаря присутствует в строке поиска.

Несколько строк поиска можно объединить в дерево поиска, так называемый бор. Бор является конечным автоматом, распознающим одну строку из m — правда, при условии, что начало строки известно. Первое, что мы сделаем — научим автомат «самовосстанавливаться», если подстрока не совпала. Заманчиво при любой неподходящей букве переводить автомат в начальное состояние, однако это может привести к пропуску подстроки. Например: ищем строку aabab, попадается aabaabab. После считывания пятого символа переводим автомат в исходное состояние и пропускаем подстроку — верно было бы перейти в состояние a (а потом снова обработать пятый символ).

Чтобы автомат самовосстанавливался, добавим к нему суффиксные ссылки, нагруженные пустым символом ⌀ (так что детерминированный автомат превращается в недетерминированный). А именно: пусть, например, разобрана строка aaba. Пробуем «скормить» бору суффиксы aba, ba, a. Суффиксная ссылка — это ссылка на узел, соответствующий самому длинному суффиксу, который не заводит бор в тупик (в данном случае a).

Для корневого узла суффиксная ссылка — петля. Для остальных правило таково. Пусть последний распознанный символ — c. Проходимся по суффиксной ссылке родителя. Если оттуда есть дуга, нагруженная символом c, направляем суффиксную ссылку в тот узел, куда эта дуга ведёт. Иначе — проходимся по суффиксной ссылке ещё и ещё раз, пока либо не пройдём по корневой ссылке-петле, либо не найдём дугу, нагруженную символом c.

 * ···Ø···> * ···Ø···> * ···Ø···> *
 |                                |
 c                                c
 ↓                                ↓
[*] ·············Ø··············> *
     новая суффиксная ссылка

Этот автомат недетерминированный. Преобразование недетерминированного конечного автомата в детерминированный в общем случае приводит к значительному увеличению количества вершин. Но этот автомат можно превратить в детерминированный, не создавая новых вершин. А именно: если для вершины v некуда идти по символу c, проходимся по суффиксной ссылке ещё и ещё раз — пока либо не попадём в корень, либо будет куда идти по символу c.

Всю детерминизацию удобно делать рекурсивно. Например, для суффиксной ссылки:

 алг СуффСсылка(v)
   если v.кэшСуффСсылка ≠ Ø      // для корня изначально корень.кэшСуффСсылка = корень
     вернуть v.кэшСуффСсылка
   u := v.родитель
   c := v.символ
   повторять
     u := СуффСсылка(u)
   до (u = корень) или (существует путь u —c→ w)
   если существует переход u —c→ w
     то v.кэшСуффСсылка := w
     иначе v.кэшСуффСсылка := корень
   вернуть v.кэшСуффСсылка

Детерминизация увеличивает количество конечных вершин. А именно: если суффиксные ссылки из вершины v ведут в конечную u, сама v тоже объявляется конечной. Для этого устроим так называемые конечные ссылки: конечная ссылка ведёт на ближайшую по суффиксным ссылкам конечную вершину. Пройдя по конечным ссылкам, находим все совпавшие строки.

 алг ВывестиРезультат(v, i)
   напечатать "Найдено " + v.иголка + " в позиции " + (i - v.глубина + 1)
 алг ОсновнаяЧастьПоиска
   состояние := корень
   цикл i=1..|стогСена|
     состояние := Переход(состояние, стогСена[i]);
     если состояние.иголка ≠ Ø
       ВывестиРезультат(состояние, i)
     времСост := состояние
     пока КонечнаяСсылка(времСост) ≠ Ø
       времСост := КонечнаяСсылка(времСост);
       ВывестиРезультат(времСост, i)

Ну и наконец: суффиксные и конечные ссылки в автомате можно рассчитывать по мере надобности уже на фазе поиска. Побочные переходы — можно вычислять на месте, никак не кэшируя, можно кэшировать для всех узлов, можно — для важнейших (на асимптотическую оценку алгоритма всё это не влияет).

Вычислительная сложность[править | править вики-текст]

Время работы зависит от организации данных. Например:

  • Если таблицу переходов автомата хранить как индексный массив — расход памяти O(nσ), вычислительная сложность O(nσ + H + k), где H — длина текста, в котором ищем, n — общая длина всех слов в словаре, σ — размер алфавита, k — общая длина всех совпадений.
  • Если таблицу переходов автомата хранить как красно-чёрное дерево — расход памяти снижается до O(n), однако вычислительная сложность поднимается до O((H + n) log σ + k).

Применение[править | править вики-текст]

Самое впечатляющее применение алгоритму Ахо-Корасик — антивирусы. Вирусная база может занимать сотни мегабайт, однако разница в скорости между 2- и 200-мегабайтной базой совсем невелика. Также метод применяется в обработке текстов, дешифровке ДНК.[источник не указан 446 дней]

Ссылки[править | править вики-текст]