Aho-Corasick: Пошук у всьому словнику шаблонів за один прохід

Пошук багатьох шаблонів в одному проході

Враховуючи один шаблон та один текст, пошук за одним шаблоном, як у алгоритмі КМП, сканує текст лише один раз. Якщо потрібно шукати багато шаблонів – наприклад, вірусний сканер, що перевіряє файл проти тисяч відомих сигнатур, або функція виділення багатослів в текстовому редакторі – бездумно запускати пошук за одним шаблоном для кожного з них коштує O(n*k), де k – кількість шаблонів, а n – довжина тексту. Алгоритм Ахо-Корсіка, опублікований Альфредом Ахо та Мередіт Корсік у 1975 році, знаходить кожне вoccurrence кожного шаблону з цілої словникової бази в одному проході O(n) по тексту, незалежно від кількості шаблонів (окрім фіксованої вартості побудови автомата один раз).

Перший крок: побудова трійки

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

Крок другий: побічні зв’язки – вся суть

Простий trie може рухатися лише вперед від кореня, тому якщо ви пройшли три символи, збігаючи один шаблон, і четвертий символ не відповідає жодному з його дітей, наївний підхід починає збірку заново з кореня, викидаючи з уваги той факт, що прочитані раніше три символи самі по собі можуть бути корисним префіксом іншого шаблону. Aho-Corasick попередньо обчислює для кожного вузла побічний зв’язок: вузол, до якого можна дістатися, слідуючи найдовшим строгим суфіксом рядка цього вузла, який також є префіксом десь ще в trie. У разі невідповідності замість перезапуску з кореня автомат просто йде за побічним зв’язком і продовжує збірку звідти – жоден символ вхідних даних не перечитується.

failure(вузол) = вузол trie, до якого можна дістатися, слідуючи найдовшим строгим суфіксом рядка цього вузла, який також є префіксом в trie (корінь, якщо такого суфікса не існує) scan(текст): вузол = корінь для ch у тексті: поки вузол не має дитини для ch і вузол !== корінь: вузол = failure(вузол) // слідуємо побічний зв’язок, не перечитуючи ch якщо вузол має дитину для ch: вузол = дитина вивести всі шаблони, що закінчуються на вузлі, і всі вузли, доступні відвідуванням вихідних зв’язків з цього вузла (шаблони, які є суфіксами цього вузла) Побічні зв’язки обчислюються один раз, у широтному першому пошуку по trie після вставки всіх шаблонів, кожен вузол має побічний зв’язок побудований з побічного зв’язку його батька (дуже схожий за духом на те, як будується функція відмов одного шаблону в KMP, узагальнений з ланцюга до дерева). Оскільки символ тексту споживається з тексту максимум один раз під час успішного переходу та побічні зв’язки рухаються лише до коротшого рядка, середньозважена вартість всієї збірки становить O(n) незалежно від того, скільки шаблонів завантажено в автомат.

failure(node) = the trie node reached by the longest strict suffix of
                node's path-string that is also some prefix in the trie
                (root if no such suffix exists)

scan(text):
  node = root
  for ch in text:
    while node has no child for ch and node !== root:
      node = failure(node)              // follow failure link, don't re-read ch
    if node has child for ch: node = child
    output every pattern ending at node, and at every node reachable
      by following output links from node (patterns that are suffixes of it)

Вивід посилань: виявлення шаблонів, що є суфіксами інших збігів

Існує ще одна тонкість: якщо шаблони "he" та "she" обидва присутні, прибувши до вузла для "she", також має бути повідомлено про збіг з "he", оскільки він там закінчується як суфікс. Кожен вузол додатково містить посилання на найближчого предка (через посилання на невдалі спроби) який є кінцем шаблону, тому повідомлення про збіг у будь-якому вузлі також проходить ланцюг вивідних посилань для повідомлення про всі коротші шаблони, що закінчуються в цій самій позиції – без цього автомат би непомітно пропускав усі легітимні збіги, коли одна словникова стаття випадково є суфіксом поточного збігу.

Де це насправді використовується

Ахо-Корасюк – це класичний алгоритм, що лежить в основі оригінального Unix fgrep, і залишається стандартним у антивірусних та системах виявлення вторгнень, які сканують трафік або файли проти тисяч відомих сигнатур одночасно. Він також використовується в біоінформаційних інструментах для пошуку багатьох коротких мотивів в геномі за один прохід, а також у будь-якій конвеєрі обробки тексту, яка потребує тегування або видалення з контексту великої фіксованої словникової бази даних (заборонені слова, назви сутностей, набори ключових слів) за один прохід, а не за один прохід для кожного терміну.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Aho-Corasick і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.