Алгоритм Ахо – Корасика - Aho–Corasick algorithm

В Информатика, то Алгоритм Ахо – Корасика это алгоритм поиска строки изобретен Альфред В. Ахо и Маргарет Дж. Корасик.[1] Это своего рода алгоритм сопоставления словарей, который находит элементы конечного набора строк («словарь») во входном тексте. Соответствует всем струнам одновременно. В сложность алгоритма является линейным по длине строк плюс длина искомого текста плюс количество выходных совпадений. Обратите внимание: поскольку все совпадения найдены, количество совпадений может быть квадратичным, если каждая подстрока совпадает (например, dictionary = а, аа, ааа, аааа и входная строка аааа).

Неформально алгоритм строит конечный автомат что напоминает три с дополнительными связями между различными внутренними узлами. Эти дополнительные внутренние ссылки позволяют быстро переходить между неудачными совпадениями строк (например, поиск Кот в дереве, не содержащем Кот, но содержит тележка, и, следовательно, выйдет из строя на узле с префиксом ок) в другие ветви дерева, которые имеют общий префикс (например, в предыдущем случае ветвь для атрибут может быть лучшим боковым переходом). Это позволяет автомату переходить между совпадениями строк без необходимости возврата.

Когда строковый словарь известен заранее (например, Компьютерный вирус базу данных), построение автомата может быть выполнено один раз в автономном режиме, а скомпилированный автомат сохранен для дальнейшего использования. В этом случае время его выполнения линейно зависит от длины ввода плюс количества совпадающих записей.

Алгоритм сопоставления строк Ахо – Корасика лег в основу оригинальной Команда Unix fgrep.

пример

В этом примере мы рассмотрим словарь, состоящий из следующих слов: {a, ab, bab, bc, bca, c, caa}.

На приведенном ниже графике представлена ​​структура данных Ахо – Корасика, построенная на основе указанного словаря, где каждая строка в таблице представляет узел в дереве, а путь столбца указывает (уникальную) последовательность символов от корня до узла.

В структуре данных есть один узел для каждого префикса каждой строки в словаре. Итак, если (bca) есть в словаре, тогда будут узлы для (bca), (bc), (b) и (). Если узел есть в словаре, это синий узел. В противном случае это серый узел.

Есть черная направленная «дочерняя» дуга от каждого узла к узлу, имя которого находится путем добавления одного символа. Итак, есть черная дуга от (bc) до (bca).

От каждого узла к узлу проходит дуга «суффикса» с синим направлением, которая является самым длинным возможным строгим суффиксом этого узла в графе. Например, для узла (caa) его строгими суффиксами являются (aa), (a) и (). Самый длинный из них в графе - (а). Итак, есть синяя дуга от (caa) до (a). Синие дуги можно вычислить за линейное время, выполнив поиск в ширину, начиная с корня. Цель для синей дуги посещенного узла можно найти, проследив за синей дугой его родителя до самого длинного суффиксного узла и отыскав дочерний узел суффиксного узла, чей символ совпадает с символом посещаемого узла.

От каждого узла к следующему узлу в словаре есть зеленая дуга «суффикса словаря», к которой можно добраться, следуя синим дугам. Например, есть зеленая дуга от (bca) до (a), потому что (a) - это первый узел в словаре (т.е. синий узел), который достигается при следовании по синим дугам до (ca), а затем до ( а). Зеленые дуги можно вычислить за линейное время, многократно пересекая синие дуги, пока не будет найден синий узел, и запоминание эта информация.

Визуализация дерева для словаря справа. Суффиксные ссылки выделены синим цветом; ссылки на суффикс словаря выделены зеленым цветом. Узлы, соответствующие словарным статьям, выделены синим цветом.
Словарь {a, ab, bab, bc, bca, c, caa}
ДорожкаВ словареСуффиксная ссылкаDict суффикс ссылка
()–
(а)+()
(ab)+(б)
(б)–()
(ба)–(а)(а)
(детка)+(ab)(ab)
(до н.э)+(c)(c)
(BCA)+(ок)(а)
(c)+()
(ок)–(а)(а)
(CAA)+(а)(а)

На каждом шаге текущий узел расширяется путем нахождения его дочернего элемента, и если он не существует, нахождения дочернего элемента его суффикса, а если это не работает, нахождения дочернего элемента суффикса суффикса и т. Д., Наконец, заканчивая в корневом узле, если ничего раньше не видел.

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

Выполнение на входной строке abccab дает следующие шаги:

Анализ входной строки abccab
УзелОставшаяся строкаВыход: конечное положениеПереходВывод
()abccab начать с корня
(а)bccabа: 1() ребенку (а)Текущий узел
(ab)ccabab: 2(а) ребенку (ab)Текущий узел
(до н.э)таксиbc: 3, c: 3(ab) к суффиксу (b) к потомку (bc)Текущий узел, узел суффикса Dict
(c)abс: 4(bc) к суффиксу (c) к суффиксу () к дочернему (c)Текущий узел
(ок)ба: 5(c) ребенку (ca)Узел суффикса Dict
(ab)ab: 6(ca) к суффиксу (a) к ребенку (ab)Текущий узел

Список динамического поиска

Исходный алгоритм Ахо-Корасика предполагает, что набор строк поиска фиксирован. Он не применяется напрямую к приложениям, в которых новые строки поиска добавляются во время применения алгоритма. Примером является интерактивная программа индексации, в которой пользователь просматривает текст и выделяет новые слова или фразы для индексации, как он или она их видит. Бертран Мейер представила инкрементную версию алгоритма, в которой набор строк поиска может быть постепенно расширен во время поиска, сохраняя алгоритмическую сложность оригинала.[2]

Смотрите также

Рекомендации

  1. ^ Ахо, Альфред В.; Корасик, Маргарет Дж. (Июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске». Коммуникации ACM. 18 (6): 333–340. Дои:10.1145/360825.360855. Г-Н  0371172.
  2. ^ Мейер, Бертран (1985). «Пошаговое сопоставление строк» (PDF). Письма об обработке информации. 21: 219–227. Дои:10.1016/0020-0190(85)90088-2.

внешняя ссылка