Русская Википедия:Алгоритм Ахо — Корасик
Алгоритм Ахо — Корасик — алгоритм поиска подстроки, разработанный Альфредом Ахо и Маргарет Корасик в 1975 году[1], реализует поиск множества подстрок из словаря в данной строке.
Широко применяется в системном программном обеспечении, например, используется в утилите поиска grep[2].
Принцип работы
Алгоритм строит конечный автомат, которому затем передаёт строку поиска. Автомат получает по очереди все символы строки и переходит по соответствующим рёбрам. Если автомат пришёл в конечное состояние, соответствующая строка словаря присутствует в строке поиска.
Несколько строк поиска можно объединить в дерево поиска, так называемый бор (префиксное дерево). Бор является конечным автоматом, распознающим одну строку из <math>m</math> — но при условии, что начало строки известно.
Первая задача в алгоритме — научить автомат «самовосстанавливаться», если подстрока не совпала. При этом перевод автомата в начальное состояние при любой неподходящей букве не подходит, так как это может привести к пропуску подстроки (например, при поиске строки aabab
, попадается aabaabab
, после считывания пятого символа перевод автомата в исходное состояние приведёт к пропуску подстроки — верно было бы перейти в состояние a
, а потом снова обработать пятый символ). Чтобы автомат самовосстанавливался, к нему добавляются суффиксные ссылки, нагруженные пустым символом ⌀ (так что детерминированный автомат превращается в недетерминированный). Например, если разобрана строка aaba
, то бору предлагаются суффиксы aba
, ba
, a
. Суффиксная ссылка — это ссылка на узел, соответствующий самому длинному суффиксу, который не заводит бор в тупик (в данном случае a
).
Для корневого узла суффиксная ссылка — петля. Для остальных правило таково: если последний распознанный символ — <math>c</math>, то осуществляется обход по суффиксной ссылке родителя, если оттуда есть дуга, нагруженная символом <math>c</math>, суффиксная ссылка направляется в тот узел, куда эта дуга ведёт. Иначе — алгоритм проходит по суффиксной ссылке ещё и ещё раз, пока либо не пройдёт по корневой ссылке-петле, либо не найдёт дугу, нагруженную символом <math>c</math>.
* ···Ø···> * ···Ø···> * ···Ø···> * | | Шаблон:Mvar Шаблон:Mvar ↓ ↓ [*] ·············Ø··············> * новая суффиксная ссылка
Этот автомат недетерминированный. Преобразование недетерминированного конечного автомата в детерминированный в общем случае приводит к значительному увеличению количества вершин. Но этот автомат можно превратить в детерминированный, не создавая новых вершин: если для вершины <math>v</math> некуда идти по символу <math>c</math>, проходимся по суффиксной ссылке ещё и ещё раз — пока либо не попадём в корень, либо будет куда идти по символу <math>c</math>.
Всю детерминизацию удобно делать рекурсивно. Например, для суффиксной ссылки:
алг СуффСсылка(v) если v.кэшСуффСсылка ≠ Ø // для корня изначально корень.кэшСуффСсылка = корень вернуть v.кэшСуффСсылка u := v.родитель c := v.символ повторять u := СуффСсылка(u) до (u = корень) или (существует путь u —c→ w) если существует переход u —c→ w то v.кэшСуффСсылка := w иначе v.кэшСуффСсылка := корень вернуть v.кэшСуффСсылка
Детерминизация увеличивает количество конечных вершин: если суффиксные ссылки из вершины <math>v</math> ведут в конечную <math>u</math>, сама <math>v</math> тоже объявляется конечной. Для этого создаются так называемые конечные ссылки: конечная ссылка ведёт на ближайшую по суффиксным ссылкам конечную вершину; обход по конечным ссылкам даёт все совпавшие строки.
алг ВывестиРезультат(v, i) напечатать "Найдено " + v.иголка + " в позиции " + (i - v.глубина + 1)
алг ОсновнаяЧастьПоиска состояние := корень цикл i=1..|стогСена| состояние := Переход(состояние, стогСена[i]); если состояние.иголка ≠ Ø ВывестиРезультат(состояние, i) времСост := состояние пока КонечнаяСсылка(времСост) ≠ Ø времСост := КонечнаяСсылка(времСост); ВывестиРезультат(времСост, i)
Суффиксные и конечные ссылки в автомате можно рассчитывать по мере надобности уже на фазе поиска. Побочные переходы — можно вычислять на месте, никак не кэшируя, можно кэшировать для всех узлов, можно — для важнейших (на асимптотическую оценку алгоритма всё это не влияет).
Вычислительная сложность
Вычислительная сложность работы алгоритма зависит от организации данных. Например:
- Если таблицу переходов автомата хранить как индексный массив — расход памяти <math>O(n\sigma)</math>, вычислительная сложность <math>O(n\sigma + H + k)</math>, где <math>H</math> — длина текста, в котором производится поиск, <math>n</math> — общая длина всех слов в словаре, <math>\sigma</math> — размер алфавита, <math>k</math> — общая длина всех совпадений.
- Если таблицу переходов автомата хранить как красно-чёрное дерево — расход памяти снижается до <math>O(n)</math>, однако вычислительная сложность поднимается до <math>O((H+n)\log \sigma + k)</math>.
Примечания
Шаблон:Wikibooks Шаблон:Примечания
Ссылки
Шаблон:Строки Шаблон:Нет источников