🕸️ Aho–Corasick
Автомат пошуку за кількома шаблонами
Стан: 0 · Позиція 0 / 0
Налаштування
Керування
Статистика
Поточний стан
0
Позиція
0 / 0
Збіги
0
Вузли бора
0
Журнал збігів
Поки що збігів немає.
Інфо та теорія

Aho–Corasick знаходить кожне входження кількох шаблонів у тексті за один лінійний прохід, поєднуючи бор (trie) усіх шаблонів із fail-посиланнями, що узагальнюють ідею, покладену в основу однопатернового алгоритму KMP.

1. Побудова бора

Кожен шаблон вставляється у спільний бор із коренем у вузлі 0. Кожен вузол відповідає рядку, що утворюється шляхом від кореня; вузол позначається як output-вузол, якщо цей шлях збігається з одним із шаблонів.

2. Fail-посилання (BFS)

Для кожного вузла v, до якого дістаються з батьківського вузла u через символ c, fail-посилання f(v) вказує на вузол, що відповідає найдовшому власному суфіксу рядка вузла v, який водночас є префіксом якогось шаблону (тобто теж є вузлом бора). Fail-посилання обчислюються за допомогою обходу BFS по бору, рівень за рівнем: діти кореня отримують f = корінь; для глибшого нащадка, до якого дістаються з u через c, проходимо ланцюжком fail-посилань вузла u, доки не знайдемо вузол із переходом goto по c (або не повернемось до кореня).

3. Output / словникові суфіксні посилання

Один вузол може одночасно бути суфіксом кількох збіжних шаблонів, тож ефективна множина збігів кожного вузла — це його власні outputs плюс усі виходи, досяжні шляхом переходу по fail-посиланнях аж до кореня — ланцюжок словникових суфіксів. Попереднє обчислення цієї об'єднаної множини (або її обхід у реальному часі) дозволяє сканеру повідомляти про кожен шаблон, що закінчується в певній позиції, не пропускаючи перекривних збігів.

4. Сканування

Текст подається по одному символу за раз. Із поточного стану виконується перехід по ребру бора, якщо воно існує; інакше послідовно застосовуються fail-посилання, поки не знайдеться ребро або не буде досягнуто кореня. Після кожного переходу об'єднана множина виходів нового стану повідомляється як збіги, що закінчуються в цій позиції.

Складність

Побудова бора та fail-посилань коштує O(m), де m — сумарна довжина всіх шаблонів; сканування тексту коштує O(n), де n — довжина тексту. Виведення всіх збігів коштує O(z), де z — кількість збігів, що в сумі дає O(n + m + z).

Про Aho–Corasick

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Оновлено: 11 липня 2026 р.

Алгоритм Aho–Corasick, винайдений у 1975 році Альфредом В. Ахо та Маргарет Дж. Корасік у лабораторіях Bell, вирішує задачу пошуку за кількома шаблонами: маючи словник шаблонів і текст, знайти кожне входження кожного шаблону за один лінійний прохід. Він узагальнює алгоритм Кнута–Морріса–Пратта (KMP) з одного шаблону на багато, об'єднуючи всі шаблони у спільний бор і обчислюючи fail-посилання обходом у ширину — так само, як KMP обчислює функцію відмови для одного шаблону. Fail-посилання кожного вузла вказує на найдовший власний суфікс його рядка, що водночас є префіксом якогось шаблону, а кожен вузол несе об'єднану "словникову суфіксну" множину виходів, зібрану переходом по fail-посиланнях аж до кореня. Сканування тексту довжини n коштує лише O(n + m + z), де m — сумарна довжина шаблонів, а z — кількість знайдених збігів. Завдяки цій ефективності Aho–Corasick лежить в основі оригінальної утиліти fgrep/grep -F, антивірусних сканерів сигнатур, що одночасно перевіряють файли на тисячі сигнатур шкідливого коду, а також систем виявлення мережевих вторгнень, які в реальному часі перевіряють вміст пакетів на відомі рядки атак.

Часті запитання

Чим Aho–Corasick відрізняється від простого запуску KMP для кожного шаблону окремо?

Запуск KMP окремо для k шаблонів на тексті довжини n у найгіршому випадку коштує O(k·n), оскільки кожен шаблон вимагає власного проходу. Aho–Corasick об'єднує всі шаблони в один автомат і сканує текст рівно один раз, витрачаючи O(n + m + z) незалежно від кількості шаблонів, що значно швидше при пошуку сотень чи тисяч шаблонів одночасно.

Що таке fail-посилання і навіщо воно потрібне?

Fail-посилання від вузла v вказує на вузол бора, що відповідає найдовшому власному суфіксу рядка v, який усе ще є префіксом якогось шаблону. Коли автомат не може продовжити поточний збіг наступним символом, він переходить по fail-посиланнях замість того, щоб починати з кореня, тож жоден вхідний символ ніколи не перечитується — саме це й тримає сканування лінійним за довжиною тексту.

Чи може Aho–Corasick знаходити перекривні збіги, наприклад, "he" і "hers", що закінчуються поряд?

Так. Оскільки кожен вузол бора зберігає об'єднану множину виходів, зібрану переходом по fail-посиланнях аж до кореня (ланцюжок словникових суфіксів), один стан може повідомити про кілька шаблонів, що є суфіксами один одного або просто закінчуються в одній позиції тексту, тож усі перекривні та вкладені збіги повідомляються коректно.

Де Aho–Corasick застосовується на практиці?

Окрім початкового використання в утиліті fgrep у Unix, він живить антивірусні рушії, що звіряють файли з великими базами сигнатур, системи виявлення мережевих вторгнень, що сканують пакети на відомі рядки атак, спам- та контент-фільтри, а також біоінформатичні інструменти, що шукають у ДНК-послідовностях безліч коротких мотивів одночасно.