Введение
Алгоритм поиска строк в информатике — это алгоритм поиска строк, изобретенный Альфредом В. Ахо и Маргарет Дж. Корасик в 1975 году. Это разновидность алгоритма поиска по словарю, который находит элементы конечного набора строк ("словаря") в заданном тексте. Он осуществляет поиск всех строк одновременно. Временная сложность алгоритма линейна относительно суммарной длины строк, длины искомого текста и количества найденных совпадений. Следует отметить, что поскольку находятся все совпадения, их количество может быть квадратичным, если каждая подстрока соответствует одному из элементов словаря (например, словарь = "a", "aa", "aaa" и входная строка — "aaaa"). По сути, алгоритм строит конечный автомат, напоминающий префиксное дерево (trie) с дополнительными связями между различными внутренними узлами. Эти дополнительные связи позволяют быстро переходить от неудачных совпадений строк (например, при поиске "bc" в trie, который не содержит "bc", но содержит "abc", и, следовательно, поиск не удастся в узле, соответствующем префиксу "b"), к другим ветвям trie, имеющим общий суффикс (например, в предыдущем случае ветвь для "abc" может быть наилучшим переходом). Это позволяет автомату переходить между совпадениями строк без необходимости возврата. Если словарь строк известен заранее (например, база данных компьютерных вирусов), построение автомата можно выполнить однократно в автономном режиме, а скомпилированный автомат сохранить для последующего использования. В этом случае время его работы линейно относительно длины входного текста плюс количество найденных совпадений. Алгоритм поиска строк Ахо-Корасика лег в основу оригинальной команды Unix fgrep.
In computer science, the Aho—Corasick algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. It is a kind of dictionary matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e. g. dictionary = , , , and input string is ). Informally, the algorithm constructs a finite state machine that resembles a trie with additional links between the various internal nodes. These extra internal links allow fast transitions between failed string matches (e. g. a search for in a trie that does not contain , but contains , and thus would fail at the node prefixed by ), to other branches of the trie that share a common suffix (e. g., in the previous case, a branch for might be the best lateral transition). This allows the automaton to transition between string matches without the need for backtracking. When the string dictionary is known in advance (e. g. a computer virus database), the construction of the automaton can be performed once off line and the compiled automaton stored for later use. In this case, its run time is linear in the length of the input plus the number of matched entries. The Aho—Corasick string matching algorithm formed the basis of the original Unix command fgrep.
Динамический поисковый список
Оригинальный алгоритм Ахо-Корасика предполагает, что набор поисковых строк задан заранее и не изменяется. Он не применим напрямую к задачам, в которых поисковые строки добавляются в процессе работы алгоритма. Примером может служить интерактивная программа индексирования, в которой пользователь просматривает текст и выделяет новые слова или фразы для индексации по мере необходимости. Бертран Мейер предложил инкрементную версию алгоритма, позволяющую расширять набор поисковых строк в процессе поиска, сохраняя при этом алгоритмическую сложность исходного алгоритма.