Aho-Corasick: Przeszukiwanie Całego Słownika Wzorców w Jednym Przejściu

Wyszukiwanie wielu wzorców w jednym przejściu

Przy danym wzorcu i tekście, wyszukiwanie pojedynczego wzorca, jak w przypadku algorytmu KMP, skanuje tekst raz. Przy wielu wzorcach – np. skaner wirusów sprawdzający plik przeciwko tysiącom znanych sygnatur, lub podświetlacz wielosłowny w edytorze tekstu – naiwne uruchamianie pojedynczego wyszukiwania wzorca dla każdego wzoru kosztuje O(n*k), gdzie k to liczba wzorców względem długości tekstu n. Algorytm Aho-Corasick, opublikowany przez Alfreda Ahonego i Margaret Corasick w 1975 roku, znajduje każde wystąpienie każdego wzorca z całego słownika w jednym przejściu O(n) przez tekst, niezależnie od liczby wzorców (poza stałym kosztem zbudowania automatu raz).

Krok pierwszy: budowa tria

Wstaw każdy wzorzec do standardowego tria (drzewa prefiksów): każda krawędź jest oznaczona jednym znakiem, a każdy węzeł osiągnięty wzdłuż ścieżki od korzenia reprezentuje prefiks utworzony przez te znaki. Węzły oznaczające koniec kompletnego wzorca są oznaczone jako węzły wyjściowe. Do tej pory jest to nic innego niż współdzielona struktura danych z podprefiksami, która pozwala wielu wzorcom ponownie wykorzystywać te same węzły dla dowolnego wspólnego prefiksu.

Drugi krok: linki niepowodzenia – cała sztuczka

Prosta tria może poruszać się tylko do przodu od korzenia, więc jeśli jesteśmy trzy znaki głęboko dopasowując jeden wzorzec i czwarty znak nie pasuje do żadnego z jego potomków, naiwny algorytm zaczyna dopasowywanie od nowa od korzenia, tracąc fakt, że właśnie przeczytane trzy znaki mogą sam w sobie być przydatnym przedrostkiem innego wzorca. Aho-Corasick prekomputuje dla każdego węzła link niepowodzenia: węzeł osiągnięty poprzez śledzenie najdłuższego właściwego przedrostka ciągu tego węzła, który również jest przedrostkiem gdzieś indziej w triu. W przypadku niezgodności zamiast rozpoczynania dopasowywania od korzenia automat po prostu podąża za linkiem niepowodzenia i kontynuuje dopasowywanie z niego – żaden znak wejściowy nigdy nie jest ponownie odczytywany.

failure(node) = węzeł tria osiągnięty poprzez najdłuższy ścisły przedrostek ciągu ścieżki węzła, który również jest przedrostkiem w triu (korzeń, jeśli takiego przedrostka nie ma) scan(tekst): node = korzeń for ch in tekst: while node nie ma potomka dla ch i node !== korzeń: node = failure(node) // podążaj za linkiem niepowodzenia, nie odczytuj ponownie ch if node ma potomka dla ch: node = potomek wyświetl każdy wzorzec kończący się w węźle, oraz każdy węzeł osiągalny poprzez śledzenie linków wyjściowych z węzła (wzorców, które są przedrostkami tego węzla) Linki niepowodzenia są obliczane raz, w jednym poszukiwaniu wszerz po triu po wprowadzeniu wszystkich wzorców, każdy link niepowodzenia węzła budowany od linku niepowodzenia jego rodzica (bardzo podobny w duchu do sposobu budowy funkcji pojedynczego wzorca niepowodzenia w KMP, uogólniony z łańcucha do drzewa). Ponieważ znak jest konsumowany z tekstu najwyżej raz podczas udanej transycji i linki niepowodzenia poruszają się tylko do krótszego ciągu, koszt amortyzowany całego skanu wynosi O(n) niezależnie od liczby załadowanych wzorców do automatu.

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)

Wyjaśnienie powiązanych linków: wychwytywanie wzorców jako sufitów innych dopasowań

Istnieje jeszcze jedna subtelność: jeśli wzorce "he" i "she" są obecne, dotarcie do węzła dla "she" powinno również zgłosić dopasowanie dla "he", ponieważ kończy się on tam jako sufit. Każdy węzeł dodatkowo posiada link wyjściowy do najbliższego przodka (poprzez linki niepowodzenia), który sam w sobie jest końcem wzorca, więc zgłaszanie dopasowania w dowolnym węźle również przechodzi jego łańcuch linków wyjściowych w celu zgłoszenia wszystkich krótszych wzorców kończących się na tej samej pozycji – bez tego automat cicho pomijałby wszystkie uzasadnione dopasowania, gdy tylko jeden wpis słownikowy jest sufitem bieżącego dopasowania.

Where it actually gets used

Aho-Corasick is the classic algorithm behind the original Unix fgrep, and remains standard in antivirus and intrusion-detection engines scanning traffic or files against thousands of known signatures simultaneously, in bioinformatics tools searching a genome for many short motifs at once, and in any text-processing pipeline that needs to tag or redact a large fixed vocabulary (banned words, entity names, keyword sets) in one linear pass rather than one pass per term.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Aho-Corasick i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.