Algorytm Aho-Corasick

Algorytm Aho-Corasick jest jednym z algorytmów wyszukiwania wzorca w tekście opracowanym przez Alfreda V. Aho oraz . Znajduje on w tekście wystąpienia słów ze słownika (pewnego zadanego zbioru wzorców). Wszystkie wzorce są szukane jednocześnie, co powoduje, że złożoność obliczeniowa algorytmu jest liniowa względem sumy długości wzorców, długości tekstu i liczby wystąpień wzorców w tekście. W tekście może jednak występować nawet kwadratowa od długości tekstu liczba wystąpień wzorców (np. gdy słownikiem jest a, aa, aaa, aaaa, zaś tekstem jest aaaa). Ideą algorytmu jest stworzenie Drzewa trie o sufiksowych połączeniach pomiędzy wierzchołkami reprezentującymi różne słowa (niekoniecznie znajdujące się w słowniku). Inaczej mówiąc tworzone jest drzewo o etykietowanych krawędziach w którym każdy wierzchołek reprezentuje pewne słowo, składające się ze złączonych etykiet krawędzi znajdujących się na ścieżce od korzenia do tego węzła. Dodatkowo dołączane są krawędzie od wierzchołka do innego wierzchołka reprezentującego jego najdłuższy sufiks (tzw. fail) W czasie wyszukiwania w tekście algorytm porusza się po tym drzewie zaczynając od korzenia i przechodząc do wierzchołka po krawędzi etykietowanej znakiem odczytanym z tekstu. W przypadku gdy takiej nie ma w drzewie, algorytm korzysta z krawędzi fail i tam próbuje przejść do wierzchołka po krawędzi etykietowanej odczytanym znakiem. W przypadku natrafienia na węzeł oznaczony jako koniec słowa, algorytm wypisuje je jako znalezione w tekście oraz sprawdza, czy czasem w tym miejscu nie kończy się więcej wzorców przechodząc krawędziami fail aż do korzenia, sprawdzając, czy nie przechodzi po wierzchołku będącym końcem wzorca. Jednym z programów wykorzystujących ten algorytm jest polecenie systemu Unix – fgrep. Przykładowy słownik oraz drzewo trie (szare węzły odpowiadają słowom niewystępującym w słowniku, niebieskie krawędzie wskazują najdłuższy sufiks słowa). Opis wyszukiwania wzorców w tekście abccab