Алгоритм Ахо – Корасика
 Схема автомата Ахо-Корасика. | |
| Сорт | Поиск строк, сопоставление строк |
|---|---|
| Структура данных | Конечный автомат струн |
В информатике алгоритм Ахо-Корасика — это алгоритм поиска строк, изобретенный Альфредом В. Ахо и Маргарет Дж. Корасик в 1975 году. [1] Это своего рода алгоритм сопоставления словарей , который находит элементы конечного набора строк («словаря») во входном тексте. Он соответствует всем строкам одновременно. Сложность алгоритма линейно зависит от длины строк плюс длина искомого текста плюс количество выходных совпадений. Обратите внимание: поскольку все совпадения найдены, может существовать квадратичное [ нужна ссылка ] количество совпадений, если совпадает каждая подстрока (например, словарь = а , аа , ааа , аааа и входная строка аааа ).
Неформально алгоритм создает конечный автомат , напоминающий дерево с дополнительными связями между различными внутренними узлами. Эти дополнительные внутренние ссылки позволяют быстро переходить между неудачными совпадениями строк (например, поиск корзина в списке, который не содержит корзина , но содержит art и, таким образом, произойдет сбой в узле с префиксом car ), к другим ветвям дерева, имеющим общий суффикс (например, в предыдущем случае ветвь для атрибут может быть лучшим боковым переходом). Это позволяет автомату переходить между совпадениями строк без необходимости возврата.
Когда словарь строк известен заранее (например, база данных компьютерных вирусов ), построение автомата может быть выполнено один раз в автономном режиме, а скомпилированный автомат сохранен для последующего использования. В этом случае время его выполнения линейно зависит от длины ввода плюс количества совпадающих записей.
Алгоритм сопоставления строк Ахо-Корасика лег в основу исходной команды Unix fgrep .
Пример
[ редактировать ]В этом примере мы рассмотрим словарь, состоящий из следующих слов: {a, ab, bab, bc, bca, c, caa}.
График ниже представляет собой структуру данных Ахо-Корасика, созданную на основе указанного словаря, где каждая строка таблицы представляет узел дерева, а путь столбца указывает (уникальную) последовательность символов от корня до узла.
Структура данных имеет один узел для каждого префикса каждой строки в словаре. Таким образом, если (bca) есть в словаре, то будут узлы для (bca), (bc), (b) и (). Если узел есть в словаре, то это синий узел. В противном случае это серый узел.
От каждого узла к узлу проходит черная направленная «дочерняя» дуга, имя которой можно найти путем добавления одного символа. Итак, есть черная дуга от (bc) до (bca).
Существует синяя направленная «суффиксная» дуга от каждого узла до узла, который является самым длинным из возможных строгих суффиксов в графе. Например, для узла (caa) его строгими суффиксами являются (aa), (a) и (). Самый длинный из них, который существует на графике, — это (a). Итак, есть синяя дуга от (caa) до (a). Синие дуги можно вычислить за линейное время, выполнив поиск в ширину [потенциальный суффиксный узел всегда будет на более низком уровне], начиная с корня. Цель синей дуги посещенного узла можно найти, проследив синюю дугу его родительского узла до самого длинного суффиксного узла и выполнив поиск дочернего узла суффиксного узла, символ которого соответствует символу посещенного узла. Если дочерний персонаж не существует, мы можем найти следующий самый длинный суффикс (снова следующий за синей дугой), а затем выполнить поиск символа. Мы можем делать это до тех пор, пока не найдем символ (как дочерний элемент узла) или не достигнем корня (который всегда будет суффиксом каждой строки).
От каждого узла к следующему узлу в словаре проходит зеленая дуга «суффикса словаря», к которой можно добраться, следуя синим дугам. Например, существует зеленая дуга от (bca) до (a), потому что (a) — это первый узел в словаре (т. е. синий узел), который достигается при следовании по синим дугам к (ca), а затем к ( а). Зеленые дуги можно вычислить за линейное время, многократно проходя синие дуги до тех пор, пока не будет найден синий узел, и запоминая эту информацию.
| Путь | В словаре | Суффиксная ссылка | Ссылка на суффикс Dict |
|---|---|---|---|
| () | – | ||
| (а) | + | () | |
| (аб) | + | (б) | |
| (б) | – | () | |
| (нет) | – | (а) | (а) |
| (глава) | + | (аб) | (аб) |
| (до н.э.) | + | (с) | (с) |
| (до н. э.) | + | (что) | (а) |
| (с) | + | () | |
| (что) | – | (а) | (а) |
| (каа) | + | (а) | (а) |
На каждом шаге текущий узел расширяется за счет поиска его дочернего элемента, а если он не существует, то поиска дочернего элемента его суффикса, а если это не работает, поиска дочернего элемента суффикса его суффикса и т. д., наконец, заканчивая корнем. node, если раньше ничего не видели.
Когда алгоритм достигает узла, он выводит все словарные записи, которые заканчиваются на текущей позиции символа во входном тексте. Это делается путем печати каждого узла, достигнутого путем следования суффиксным ссылкам словаря, начиная с этого узла и продолжая до тех пор, пока он не достигнет узла без суффиксной ссылки словаря. Кроме того, печатается сам узел, если это словарная статья.
Выполнение над входной строкой abccab дает следующие шаги:
| Узел | Оставшаяся строка | Выход: конечное положение | Переход | Выход |
|---|---|---|---|---|
| () | abccab | начать с корня | ||
| (а) | bccab | а:1 | () ребенку (а) | Текущий узел |
| (аб) | такси | аб:2 | (а) ребенку (аб) | Текущий узел |
| (до н.э.) | такси | бк:3, с:3 | (ab) к суффиксу (b) к ребенку (bc) | Текущий узел, узел суффикса Dict |
| (с) | аб | с:4 | (bc) к суффиксу (c) к суффиксу () к дочернему (c) | Текущий узел |
| (что) | б | а:5 | (в) ребенку (ок) | Узел суффикса Dict |
| (аб) | аб:6 | (ca) к суффиксу (a) к ребенку (ab) | Текущий узел |
Динамический список поиска
[ редактировать ]Исходный алгоритм Ахо-Корасика предполагает, что набор строк поиска фиксирован. Это не относится напрямую к приложениям, в которых новые строки поиска добавляются во время применения алгоритма. Примером является интерактивная программа индексирования, в которой пользователь просматривает текст и выделяет новые слова или фразы для индексации по мере их просмотра. Бертран Мейер представил инкрементную версию алгоритма, в которой набор поисковых строк может постепенно расширяться во время поиска, сохраняя алгоритмическую сложность оригинала. [2]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Ахо, Альфред В .; Корасик, Маргарет Дж. (июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске» . Коммуникации АКМ . 18 (6): 333–340. дои : 10.1145/360825.360855 . МР 0371172 . S2CID 207735784 .
- ^ Мейер, Бертран (1985). «Инкрементальное сопоставление строк» (PDF) . Письма об обработке информации . 21 (5): 219–227. дои : 10.1016/0020-0190(85)90088-2 .
Внешние ссылки
[ редактировать ]
- Ахо - Корасик NIST в Словаре алгоритмов и структур данных (15 июля 2019 г.)
- Визуализатор алгоритма Ахо-Корасика