Algorytm Aho-Corasick
Algorytm Aho-Corasick to technika wyszukiwania wzorców w tekście, stworzona przez Alfreda V. Aho oraz Margaret J. Corasick. Umożliwia on jednoczesne znajdowanie wystąpień słów z zadanego słownika w danym tekście. Dzięki tej metodzie, złożoność obliczeniowa algorytmu jest liniowa w odniesieniu do sumy długości wzorców, długości tekstu oraz liczby ich wystąpień. Warto zaznaczyć, że w tekście może wystąpić liczba wystąpień wzorców, która jest kwadratowa względem długości tekstu (np. w przypadku słownika składającego się z a, aa, aaa, aaaa, a tekstu zawierającego aaaa).
Podstawą algorytmu jest stworzenie drzewa trie, w którym wierzchołki są połączone sufiksowymi krawędziami reprezentującymi różne słowa (nawet te, które nie znajdują się w słowniku). Innymi słowy, tworzone jest drzewo z etykietowanymi krawędziami, gdzie każdy wierzchołek symbolizuje konkretne słowo, składające się z połączeń etykiet krawędzi od korzenia do danego węzła. Dodatkowo, do wierzchołków dodawane są krawędzie prowadzące do innych wierzchołków, które reprezentują ich najdłuższy sufiks (tzw. fail). Podczas wyszukiwania w tekście, algorytm porusza się po tym drzewie, zaczynając od korzenia i przechodząc przez krawędzie etykietowane znakami odczytanymi z tekstu. Gdy nie ma takiej krawędzi w drzewie, algorytm korzysta z krawędzi fail i próbuje przejść do wierzchołka po krawędzi oznaczonej odczytanym znakiem. W przypadku dotarcia do węzła oznaczonego jako koniec słowa, algorytm zgłasza je jako znalezione w tekście, a także sprawdza, czy w tym miejscu nie kończą się inne wzorce, przechodząc krawędziami fail aż do korzenia, weryfikując jednocześnie, czy nie przechodzi przez wierzchołek będący końcem wzorca.
Programem, który wykorzystuje ten algorytm, jest polecenie systemu Unix – fgrep.
Przykładowy słownik oraz drzewo trie
Węzły w drzewie trie, które są szare, odpowiadają słowom, które nie znajdują się w słowniku, natomiast niebieskie krawędzie wskazują na najdłuższy sufiks słowa.
Opis wyszukiwania wzorców w tekście „abccab”
Algorytm tworzenia automatu
Algorytm składa się z trzech funkcji:
- NEXT(węzeł, litera) – funkcja przejścia, która definiuje, z którym węzłem jest połączony przez krawędź etykietowaną literą. Na przykład, NEXT(„bc”, 'a’) zwraca „bca”, natomiast NEXT(„ca”, 'b’) zwraca NIL.
- FAIL(węzeł) – funkcja wskazująca węzeł połączony przez krawędź fail.
- OUTPUT(węzeł) – zbiór napisów związanych z danym węzłem.
Algorytm składa się z dwóch głównych etapów:
- utworzenie drzewa trie oraz ustalenie wartości funkcji NEXT i OUTPUT dla wszystkich napisów;
- uzupełnienie krawędzi fail, co oznacza określenie funkcji FAIL.
Uzupełnianie krawędzi fail
Drzewo trie jest przeszukiwane poziomami (wszerz). Posiadając zdefiniowane wartości FAIL dla wszystkich węzłów na poziomie P-1 oraz wcześniejszych, można określić wartości FAIL oraz OUTPUT dla węzłów z poziomu P.
Pierwszym krokiem jest uzupełnienie FAIL dla węzłów znajdujących się na poziomie pierwszym (następnicy korzenia), a następnie przeszukiwane są kolejne poziomy.
Algorytm wyszukiwania
Podczas przetwarzania jednego znaku, może być odwiedzonych więcej niż jeden węzeł, co oznacza, że najpierw mogą mieć miejsce przejścia przez krawędzie fail, a następnie przez jedną krawędź etykietowaną literą. Można jednak zdeterminować automat, rezygnując z krawędzi fail i określając dla każdego węzła jego następnika, co oznacza, że dla jednej litery automat zmienia stan dokładnie raz. Należy jednak pamiętać, że wiąże się to ze znacznym wzrostem wymagań pamięciowych.
Aby to odróżnić, nowa funkcja przejść została nazwana DETNEXT.
W efekcie algorytm wyszukiwania upraszcza się do:
Bibliografia
Alfred V. Aho, Margaret J. Corasick. Efficient string matching: An aid to bibliographic search. „Communications of the ACM”. 18 (6), s. 333–340, 1975. DOI: 10.1145/360825.360855.
