Войти
В информатике алгоритм Ахо – Корасика представляет собой алгоритм поиска по строке, изобретенный Альфред В. Ахо и Маргарет Дж. Корасик. Это своего рода алгоритм сопоставления словарей, который находит элементы конечного набора строк («словарь») во входном тексте. Соответствует всем струнам одновременно. Сложность алгоритма линейна по длине строк плюс длина искомого текста плюс количество выходных совпадений. Обратите внимание: поскольку все совпадения найдены, количество совпадений может быть квадратичным, если каждая подстрока совпадает (например, dictionary = a, aa, aaa, aaaa, а входная строка - aaaa).
Неформально алгоритм конструирует конечный автомат, который напоминает дерево с дополнительными связями между различными внутренними узлами. Эти дополнительные внутренние ссылки позволяют быстро переходить между неудачными совпадениями строк (например, поиск cat в дереве, которое не содержит cat, но содержит cart, и, таким образом, не удастся на узле с префиксом 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), а затем до ( а). Зеленые дуги можно вычислить за линейное время, многократно проходя синие дуги до тех пор, пока не будет найден синий узел, и запомнив эту информацию.
Визуализация дерева для словаря справа. Суффиксные ссылки выделены синим цветом; ссылки на суффикс словаря выделены зеленым цветом. Узлы, соответствующие словарным статьям, выделены синим. | Путь | В словаре | Суффиксная ссылка | Диктовка суффиксная ссылка |
|---|---|---|---|
| () | – | ||
| (a) | + | () | |
| (ab) | + | (b) | |
| (b) | – | () | |
| (ba) | – | (a) | (a) |
| (bab) | + | (ab) | (ab) |
| (bc) | + | (c) | (c) |
| (bca) | + | (ca) | (a) |
| (c) | + | () | |
| (ca) | – | (a) | (a) |
| (caa) | + | (a) | (a) |
На каждом шаге текущий узел расширяется путем нахождения его дочернего элемента, а если он не существует, нахождения дочернего элемента его суффикса, а если этого не происходит работа, поиск дочернего суффикса суффикса и т. д., в конце концов, заканчивающийся корневым узлом, если раньше ничего не было видно.
Когда алгоритм достигает узла, он выводит все словарные статьи, которые заканчиваются на текущей позиции символа во входном тексте. Это делается путем печати каждого узла, достигнутого путем перехода по ссылкам суффикса словаря, начиная с этого узла и продолжая, пока он не достигнет узла без ссылки суффикса словаря. Кроме того, печатается сам узел, если это словарная статья.
Выполнение входной строки abccab приводит к следующим шагам:
| Узел | Оставшаяся строка | Вывод: конечная позиция | Переход | Вывод |
|---|---|---|---|---|
| () | abccab | начало с корня | ||
| (a) | bccab | a: 1 | () в дочерний (a) | Текущий узел |
| (ab) | ccab | ab: 2 | (a) к дочернему (ab) | Текущий узел |
| (bc) | cab | bc: 3, c: 3 | (ab) до суффикса (b) в дочерний (bc) | Current Node, суффиксный узел Dict |
| (c) | ab | c: 4 | (bc) до суффикса (c) до суффикса () в дочерний (c) | Текущий узел |
| (ca) | b | a: 5 | (c) в дочерний (ca) | Узел суффикса Dict |
| (ab) | ab: 6 | (ca) до суффикса (a) к дочернему (ab) | Текущий узел |
оригинальный алгоритм Aho-Corasick предполагает, что набор строк поиска фиксирован. Он не применяется напрямую к приложениям, в которых новые строки поиска добавляются во время применения алгоритма. Примером может служить интерактивная программа индексации, в которой пользователь просматривает текст и выделяет новые слова или фразы для индексации, как он или она их видит. Бертран Мейер представил инкрементную версию алгоритма. в котором набор строк поиска можно постепенно расширять во время поиска, сохраняя алгоритмическую сложность оригинала.
 | На Викискладе есть материалы, связанные с алгоритмом Ахо – Корасика. |
