В информатике алгоритм Ахо–Корасик — это алгоритм поиска строк, изобретенный Альфредом В. Ахо и Маргарет Дж. Корасик в 1975 году. [1] Это своего рода алгоритм сопоставления словарей , который находит элементы конечного набора строк («словарь») во входном тексте. Он сопоставляет все строки одновременно. Сложность алгоритма линейна по длине строк плюс длина искомого текста плюс количество выходных совпадений. Обратите внимание, что поскольку все совпадения найдены, для одного местоположения строки будет возвращено несколько совпадений, если сопоставляются несколько подстрок (например, словарь = a , aa , aaa , aaaa и входная строка — aaaa ).
Неформально, алгоритм создает конечный автомат , который напоминает trie с дополнительными связями между различными внутренними узлами. Эти дополнительные внутренние связи позволяют осуществлять быстрые переходы между неудавшимися строковыми соответствиями (например, поиск cart в trie, который не содержит cart , но содержит art , и, таким образом, не будет выполнен в узле с префиксом car ), к другим ветвям trie, которые имеют общий суффикс (например, в предыдущем случае ветвь attribute могла бы быть наилучшим боковым переходом). Это позволяет автомату переходить между строковыми соответствиями без необходимости возврата назад.
Когда словарь строк известен заранее (например, база данных компьютерных вирусов ), построение автомата может быть выполнено один раз в автономном режиме, а скомпилированный автомат сохранен для последующего использования. В этом случае время его выполнения линейно зависит от длины ввода плюс количество совпавших записей.
Алгоритм сопоставления строк Ахо—Корасика лег в основу оригинальной команды 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) и затем до (a). Зеленые дуги можно вычислить за линейное время, многократно проходя синие дуги, пока не будет найден синий узел, и запоминая эту информацию.
На каждом шаге текущий узел расширяется путем поиска его дочернего узла, и если такового не существует, то путем поиска дочернего узла его суффикса, и если это не срабатывает, то путем поиска дочернего узла его суффикса и т. д., в конце концов, если ничего не было обнаружено, то процесс завершается корневым узлом.
Когда алгоритм достигает узла, он выводит все записи словаря, которые заканчиваются на текущей позиции символа во входном тексте. Это делается путем печати каждого узла, достигнутого путем следования по суффиксным ссылкам словаря, начиная с этого узла и продолжая до тех пор, пока не будет достигнут узел без суффиксной ссылки словаря. Кроме того, печатается сам узел, если это запись словаря.
Выполнение входной строки abccab приводит к следующим шагам:
Исходный алгоритм Ахо–Корасика предполагает, что набор строк поиска фиксирован. Он не применяется напрямую к приложениям, в которых новые строки поиска добавляются во время применения алгоритма. Примером является интерактивная программа индексации, в которой пользователь просматривает текст и выделяет новые слова или фразы для индексации по мере их появления. Бертран Мейер представил инкрементную версию алгоритма, в которой набор строк поиска может быть инкрементно расширен во время поиска, сохраняя алгоритмическую сложность оригинала. [2]
