PL 
EnglishDomyślny
Українська🔤 Aho–Corasick — wyszukiwanie wielu wzorców w tekście
Zbuduj trie z kilku wzorców wraz z łączami niepowodzeń, a następnie przeskanuj tekst w jednym przejściu O(n), obserwując, jak automat podąża za łączami niepowodzeń i zgłasza każde dopasowanie naraz.
O algorytmie Aho–Corasick
Algorytm Aho–Corasick, wynaleziony w 1975 roku przez Alfreda V. Aho i Margaret J. Corasick w Bell Laboratories, rozwiązuje problem dopasowywania wielu wzorców w tekście: mając słownik wzorców i tekst, znajduje każde wystąpienie każdego wzorca w jednym liniowym przejściu. Uogólnia algorytm Knutha-Morrisa-Pratta (KMP) z jednego wzorca na wiele, łącząc wszystkie wzorce we wspólne drzewo trie i obliczając łącza niepowodzeń przeszukiwaniem wszerz — dokładnie tak, jak KMP oblicza funkcję niepowodzeń dla pojedynczego wzorca. Łącze niepowodzenia każdego węzła wskazuje na najdłuższy właściwy sufiks jego ciągu, który jest jednocześnie prefiksem jakiegoś wzorca, a każdy węzeł niesie scalony zbiór wyjściowy „sufiksów słownikowych” zebrany przez podążanie za łączami niepowodzeń aż do korzenia. Skanowanie tekstu o długości n kosztuje wtedy tylko O(n + m + z), gdzie m to łączna długość wzorców, a z to liczba zgłoszonych dopasowań. Dzięki tej efektywności Aho–Corasick leży u podstaw oryginalnego narzędzia fgrep/grep -F, skanerów sygnatur antywirusowych sprawdzających pliki pod kątem tysięcy sygnatur złośliwego oprogramowania naraz oraz systemów wykrywania włamań sieciowych, które badają zawartość pakietów pod kątem znanych ciągów ataku w czasie rzeczywistym.
Najczęściej zadawane pytania
Czym Aho–Corasick różni się od zwykłego uruchamiania KMP osobno dla każdego wzorca?
Uruchomienie KMP osobno dla k wzorców na tekście o długości n kosztuje w najgorszym przypadku O(k·n), ponieważ każdy wzorzec wymaga własnego przejścia. Aho–Corasick łączy wszystkie wzorce w jeden automat i skanuje tekst dokładnie raz, kosztując O(n + m + z) niezależnie od liczby wzorców, co jest znacznie szybsze przy wyszukiwaniu setek lub tysięcy wzorców jednocześnie.
Czym dokładnie jest łącze niepowodzenia i po co jest potrzebne?
Łącze niepowodzenia z węzła v wskazuje na węzeł trie reprezentujący najdłuższy właściwy sufiks ciągu węzła v, który wciąż jest prefiksem jakiegoś wzorca. Gdy automat nie może rozszerzyć bieżącego dopasowania o kolejny znak, podąża za łączami niepowodzeń zamiast zaczynać od korzenia, dzięki czemu żaden znak wejściowy nigdy nie jest odczytywany ponownie — to właśnie utrzymuje liniowość skanowania względem długości tekstu.
Czy Aho–Corasick potrafi znaleźć nakładające się dopasowania, na przykład zarówno "he", jak i "hers" kończące się blisko tej samej pozycji?
Tak. Ponieważ każdy węzeł trie przechowuje scalony zbiór wyjściowy zebrany przez podążanie za łączami niepowodzeń aż do korzenia (łańcuch sufiksów słownikowych), pojedynczy stan może zgłosić wiele wzorców będących swoimi wzajemnymi sufiksami lub po prostu kończących się w tej samej pozycji tekstu, więc wszystkie nakładające się i zagnieżdżone dopasowania są zgłaszane poprawnie.
Gdzie w praktyce wykorzystuje się Aho–Corasick?
Poza pierwotnym zastosowaniem w narzędziu fgrep w Uniksie, algorytm ten napędza silniki antywirusowe dopasowujące pliki do dużych baz sygnatur, systemy wykrywania włamań sieciowych skanujące pakiety pod kątem znanych ciągów ataku, filtry spamu i treści oraz narzędzia bioinformatyczne przeszukujące sekwencje DNA pod kątem wielu krótkich motywów naraz.