В информатике , то алгоритм Ахо-Corasick является строка-поиска алгоритм придуман Альфредом В. Ахо и Маргарет Дж Corasick. [1] Это своего рода алгоритм сопоставления словарей, который находит элементы конечного набора строк («словарь») во входном тексте. Соответствует всем струнам одновременно. Сложность алгоритма линейно по длине строки плюс длина искомой текста плюс количество выходных матчей. Обратите внимание: поскольку все совпадения найдены, может быть квадратичное количество совпадений, если каждая подстрока совпадает (например, dictionary = a , aa , aaa, aaaa, а входная строка - aaaa ).
Неформально алгоритм конструирует конечный автомат, который напоминает дерево с дополнительными связями между различными внутренними узлами. Эти дополнительные внутренние ссылки позволяют быстро переходить между неудачными совпадениями строк (например, поиск кота в дереве, которое не содержит кота , но содержит корзину , и, таким образом, не удастся на узле с префиксом ca ), к другим ветвям дерева, которые совместно используют общий префикс (например, в предыдущем случае ветвь для атрибута могла бы быть лучшим боковым переходом). Это позволяет автомату переходить между совпадениями строк без необходимости поиска с возвратом.
Когда строковый словарь известен заранее (например, база данных компьютерных вирусов ), построение автомата может быть выполнено один раз в автономном режиме, а скомпилированный автомат сохранен для дальнейшего использования. В этом случае время его выполнения линейно зависит от длины ввода плюс количества совпавших записей.
Алгоритм сопоставления строк Ахо – Корасика лег в основу исходной команды Unix fgrep .
Пример
В этом примере мы рассмотрим словарь, состоящий из следующих слов: {a, ab, bab, bc, bca, c, caa}.
На приведенном ниже графике представлена структура данных Ахо – Корасика, построенная на основе указанного словаря, где каждая строка в таблице представляет узел в дереве, а путь столбца указывает (уникальную) последовательность символов от корня до узла.
В структуре данных есть один узел для каждого префикса каждой строки в словаре. Итак, если (bca) есть в словаре, тогда будут узлы для (bca), (bc), (b) и (). Если узел есть в словаре, это синий узел. В противном случае это серый узел.
Существует черная направленная «дочерняя» дуга от каждого узла к узлу, имя которого находится путем добавления одного символа. Итак, есть черная дуга от (bc) до (bca).
От каждого узла к узлу проходит дуга «суффикса» с синим направлением, которая является самым длинным из возможных суффиксов этого узла в графе. Например, для узла (caa) его строгими суффиксами являются (aa), (a) и (). Самый длинный из них в графе - (а). Итак, есть синяя дуга от (caa) до (a). Синие дуги можно вычислить за линейное время, выполнив поиск в ширину, начиная с корня. Цель для синей дуги посещенного узла можно найти, проследив за синей дугой его родительского узла до самого длинного суффиксного узла и отыскав дочерний узел суффиксного узла, чей символ совпадает с символом посещаемого узла. Если персонаж не существует как ребенок, мы можем найти следующий самый длинный суффикс (снова по синей дуге), а затем выполнить поиск персонажа. Мы можем делать это до тех пор, пока не найдем символ (как дочерний элемент узла) или не достигнем корня (который всегда будет суффиксом каждой строки).
От каждого узла к следующему узлу в словаре есть зеленая дуга «суффикса словаря», к которой можно добраться, следуя синим дугам. Например, есть зеленая дуга от (bca) до (a), потому что (a) - это первый узел в словаре (т.е. синий узел), который достигается, если следовать по синим дугам до (ca), а затем до ( а). Зеленые дуги можно вычислить за линейное время, многократно проходя синие дуги, пока не будет найден синий узел, и запомнив эту информацию.
Дорожка | В словаре | Суффиксная ссылка | Ссылка на суффикс Dict |
---|---|---|---|
() | - | ||
а) | + | () | |
(ab) | + | (б) | |
(б) | - | () | |
(ба) | - | а) | а) |
(баб) | + | (ab) | (ab) |
(до н.э) | + | (c) | (c) |
(BCA) | + | (ок) | а) |
(c) | + | () | |
(ок) | - | а) | а) |
(CAA) | + | а) | а) |
На каждом шаге текущий узел расширяется, находя его дочерний элемент, и если он не существует, находит его дочерний суффикс, а если это не работает, находит дочерний элемент суффикса своего суффикса и т. Д., Наконец, заканчивая корнем узел, если раньше ничего не было видно.
Когда алгоритм достигает узла, он выводит все словарные статьи, которые заканчиваются на текущей позиции символа во входном тексте. Это делается путем печати каждого узла, достигнутого путем перехода по ссылкам суффикса словаря, начиная с этого узла и продолжая до тех пор, пока не достигнет узла без ссылки суффикса словаря. Кроме того, печатается сам узел, если это словарная статья.
Выполнение на входной строке abccab выполняет следующие шаги:
Узел | Оставшаяся строка | Выход: конечное положение | Переход | Выход |
---|---|---|---|---|
() | abccab | начать с корня | ||
а) | bccab | а: 1 | () ребенку (а) | Текущий узел |
(ab) | ccab | ab: 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) | Текущий узел |
Список динамического поиска
Исходный алгоритм Aho-Corasick предполагает, что набор строк поиска фиксирован. Он не применяется напрямую к приложениям, в которых новые строки поиска добавляются во время применения алгоритма. Примером может служить интерактивная программа индексации, в которой пользователь просматривает текст и выделяет новые слова или фразы для индексации, как он или она их видит. Бертран Мейер представил инкрементную версию алгоритма, в которой набор строк поиска может быть постепенно расширен во время поиска, сохраняя алгоритмическую сложность оригинала. [2]
Смотрите также
Рекомендации
- ^ Ахо, Альфред В .; Корасик, Маргарет Дж. (Июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске». Коммуникации ACM . 18 (6): 333–340. DOI : 10.1145 / 360825.360855 . Руководство по ремонту 0371172 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Мейер, Бертран (1985). «Инкрементное сопоставление строк» (PDF) . Письма об обработке информации . 21 : 219–227. DOI : 10.1016 / 0020-0190 (85) 90088-2 . CS1 maint: обескураженный параметр ( ссылка )