Алгоритм Ахо — Корасик¶

Алгоритм Ахо — Корасик — это алгоритм поиска подстрок в тексте, построенный на основе конечного автомата и позволяющий за линейное время найти все вхождения любого из заданного набора образцов (строк-шаблонов) в исходном тексте. Алгоритм был разработан в 1975 году американскими учёными Альфредом Ахо и Маргарет Корасик (в некоторых источниках — Корасик). Он относится к классу алгоритмов множественного поиска строк и является обобщением алгоритма Кнута — Морриса — Пратта на случай нескольких образцов.

¶История

Алгоритм впервые был опубликован в 1975 году в статье «Efficient String Matching: An Aid to Bibliographic Search» (Эффективный поиск строк: помощь в библиографическом поиске). Авторы — Альфред Ахо (род. 1941) и Маргарет Корасик (род. 1945), работавшие в Bell Labs. Разработка была мотивирована задачами автоматического индексирования научных статей и поиска цитат в больших массивах текстов. В отличие от наивного подхода, при котором каждый образец ищется отдельно, алгоритм Ахо — Корасик обрабатывает текст за один проход, что даёт значительный выигрыш в производительности при большом количестве шаблонов.

¶Основные понятия

Алгоритм использует структуру данных, называемую бор (trie) — префиксное дерево, в котором каждый путь от корня до листа соответствует одному из образцов. Дополнительно вводится понятие суффиксных ссылок (failure links), которые позволяют при несовпадении символа быстро переходить к другому узлу бора, соответствующему самому длинному суффиксу текущей строки, который является префиксом какого-либо образца. Также используются выходные ссылки (output links), указывающие на узлы, в которых заканчиваются образцы, найденные в процессе обхода.

¶Устройство и этапы работы

Работа алгоритма делится на три этапа:

¶Построение бора

На первом этапе из заданного набора образцов строится бор. Каждый узел бора представляет собой префикс некоторого образца. Корень соответствует пустой строке. Для каждого символа из алфавита в узле может быть переход в дочерний узел. Если переход отсутствует, он считается неопределённым. В узлы, соответствующие полным образцам, добавляется пометка о том, что в данной точке заканчивается образец (или несколько образцов, если один является суффиксом другого).

¶Построение суффиксных ссылок

На втором этапе для каждого узла бора (кроме корня) вычисляется суффиксная ссылка. Суффиксная ссылка узла v указывает на узел, соответствующий самому длинному собственному суффиксу строки, представленной путём от корня к v, который является префиксом какого-либо образца. Для корня и его непосредственных детей суффиксные ссылки ведут в корень. Для остальных узлов ссылка вычисляется рекурсивно: если из родительского узла есть переход по последнему символу, то суффиксная ссылка — это узел, полученный из суффиксной ссылки родителя; иначе — корень. Построение выполняется с помощью обхода в ширину (BFS) бора.

¶Поиск в тексте

На третьем этапе текст обрабатывается посимвольно. Текущее состояние автомата — узел бора. Для каждого очередного символа c алгоритм пытается выполнить переход из текущего узла по c. Если переход существует, состояние обновляется. Если нет, алгоритм переходит по суффиксной ссылке до тех пор, пока не найдёт узел, из которого есть переход по c, или не достигнет корня. Если переход из корня по c отсутствует, состояние остаётся корнем. После каждого перехода проверяется, не заканчивается ли в текущем узле какой-либо образец (выход). Если да, то фиксируется вхождение образца в текст с указанием позиции. Также могут проверяться выходные ссылки — узлы, достижимые по цепочке суффиксных ссылок, в которых заканчиваются образцы.

¶Временная сложность

Время построения бора и суффиксных ссылок составляет O(m), где m — суммарная длина всех образцов. Время поиска по тексту длины n составляет O(n + k), где k — общее количество найденных вхождений. Таким образом, алгоритм является линейным относительно длины текста и суммарной длины образцов, что делает его эффективным для больших объёмов данных.

¶Применение

Алгоритм Ахо — Корасик широко применяется в различных областях:

• Антивирусное программное обеспечение — для поиска сигнатур вирусов в файлах и сетевом трафике.
• Поисковые системы и текстовые редакторы — для подсветки синтаксиса, проверки орфографии и поиска ключевых слов.
• Фильтрация контента — для блокировки нежелательных слов или фраз в сообщениях, комментариях, чатах.
• Биоинформатика — для поиска подстрок в геномных последовательностях (например, поиск сайтов рестрикции или мотивов).
• Сетевые системы безопасности — в системах обнаружения вторжений (IDS/IPS) для анализа пакетов на наличие вредоносных строк.
• Обработка естественного языка — для выделения ключевых фраз, именованных сущностей, терминов.

¶Пример работы

Пусть задан набор образцов: {he, she, his, hers}. Текст: "ushers". Построенный бор будет содержать пути для каждого образца. При обработке текста:

• Символ u — переход из корня отсутствует, состояние остаётся корнем.
• Символ s — переход из корня по s есть (начало образца she), состояние переходит в узел s.
• Символ h — из узла s переход по h есть (продолжение she), состояние переходит в узел sh. Образец не найден.
• Символ e — из узла sh переход по e есть (образец she), состояние переходит в узел she. Выход: найден образец she на позиции 2 (начиная с 0).
• Символ r — из узла she переход по r отсутствует. Переход по суффиксной ссылке: из she ссылка ведёт в узел he (суффикс he). Из he переход по r есть (образец hers), состояние переходит в узел her. Выход: найден образец hers на позиции 3.
• Символ s — из узла her переход по s есть (образец hers), состояние переходит в узел hers. Выход: найден образец hers на позиции 2 (так как hers заканчивается на позиции 5). Также по выходным ссылкам может быть найден образец his, если он является суффиксом hers (в данном примере нет).

Таким образом, в тексте "ushers" найдены образцы she (позиция 2) и hers (позиция 2 и 3).

¶Модификации и расширения

Существуют различные модификации алгоритма:

• Алгоритм с поддержкой подстановочных символов — позволяет искать образцы, содержащие символы, совпадающие с любым символом текста.
• Алгоритм для поиска в сжатых данных — адаптирован для работы с текстами, сжатыми алгоритмами LZ77, LZ78.
• Параллельные версии — реализованы для многопроцессорных систем и GPU.
• Алгоритм с динамическим обновлением набора образцов — позволяет добавлять или удалять образцы без полного перестроения автомата.

¶Критика и ограничения

Основным недостатком алгоритма является значительное потребление памяти при большом количестве образцов или большом алфавите. Каждый узел бора может содержать массив переходов размером, равным мощности алфавита, что приводит к неэффективному использованию памяти для разреженных алфавитов. Для решения этой проблемы применяются сжатые представления, такие как хеш-таблицы, деревья поиска или битовые векторы. Также алгоритм не поддерживает поиск с учётом регистра без дополнительной нормализации текста.

¶Источники

• Aho, A. V., Corasick, M. J. Efficient String Matching: An Aid to Bibliographic Search // Communications of the ACM. — 1975. — Vol. 18, № 6. — P. 333–340.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — Глава 32.3.
• Гасфилд, Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — СПб.: Невский Диалект, 2003. — Глава 3.