Algorytm Aho-Corasick
Rodzaj | wyszukiwanie wzorca |
---|---|
Złożoność | |
Czasowa |
|
Algorytm Aho-Corasick jest jednym z algorytmów wyszukiwania wzorca w tekście opracowanym przez Alfreda V. Aho oraz Margaret J. Corasick. 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).
Słownik { a, ab, bc, bca, c, caa } Ścieżka Czy węzeł jest w słowniku Najdłuższy sufiks będący w drzewie Sufiks będący innym wzorcem () – (a) + () (ab) + (b) (b) – () (bc) + (c) (c) (bca) + (ca) (a) (c) + () (ca) – (a) (a) (caa) + (a) (a)
Opis wyszukiwania wzorców w tekście abccab
Wyszukiwanie wzorców w tekście abccab
Węzeł Tekst do przeglądnięcia Wyjście programu:Pozycja w słowie Przejście Wyjście programu () abccab rozpoczęcie w korzeniu (a) bccab a:1 () do potomka (a) Obecny węzeł (ab) ccab ab:2 (a) do potomka (ab) Obecny węzeł (bc) cab bc:3, c:3 (ab) do sufiksu (b) do potomka (bc) Obecny węzeł, Węzeł sufiksowy ze słownika (c) ab c:4 (bc) do sufiksu (c) do sufiksu () do potomka (c) Obecny węzeł (ca) b a:5 (c) do potomka (ca) Węzeł sufiksowy ze słownika (ab) ab:6 (ca) do sufiksu (a) do potomka (ab) Obecny węzeł
Algorytm tworzenia automatu
Dane są trzy funkcje:
- NEXT(węzeł, litera) – funkcja przejścia definiująca, z którym węzłem jest połączony przez krawędź etykietowaną literą, np. NEXT("bc", 'a') ⇒ "bca", natomiast NEXT("ca", 'b') ⇒ NIL.
- FAIL(węzeł) – funkcja określająca węzeł połączony przez krawędź fail.
- OUTPUT(węzeł) – zbiór napisów powiązanych z węzłem.
Algorytm składa się z dwóch głównych kroków:
- utworzenia drzewa trie, dla wszystkich napisów na tym etapie ustalane są wartości funkcji NEXT oraz OUTPUT;
- uzupełnienie krawędzi fail (czyli określenie funkcji FAIL).
Uzupełnianie krawędzi fail
Drzewo trie przeglądane jest poziomami (wszerz) – mając zdefiniowane FAIL dla wszystkich węzłów na poziomie P-1 i wcześniejszych, można znaleźć wartości FAIL oraz OUTPUT dla węzłów z poziomu P.
W pierwszym kroku uzupełnia się FAIL dla węzłów z poziomu pierwszego (czyli następników korzenia), po czym przeglądane są kolejne poziomy.
procedure Aho-Corasick-tworzenie-fail(trie) kolejka := pusta kolejka korzeń := korzeń drzewa trie { etap 1 } for litera in alfabet do węzeł = NEXT(korzeń, litera) if węzeł <> nil then { powiąż krawędzią fail } FAIL(węzeł) = korzeń dodaj węzeł do kolejki else { określenie funkcji NEXT korzenia dla każdej litery } NEXT(korzeń, litera) = korzeń end end { etap 2 } while kolejka nie pusta do węzeł = weź z kolejki for litera in alfabet do następnik = NEXT(węzeł, litera) if następnik <> nil then dodaj następnik do kolejki x := FAIL(węzeł) while NEXT(x, litera) = nil do x := FAIL(x) end FAIL(następnik) := NEXT(x, litera) OUTPUT(następnik) := OUTPUT(następnik) + OUTPUT(NEXT(x, litera)) end end end
Algorytm wyszukiwania
procedure Aho-Corasick-wyszukiwanie(napis, trie) begin węzeł = korzeń drzewa trie for i := 1 to długość napisu do litera := napis[i] while NEXT(węzeł, litera) = nil do węzeł := FAIL(węzeł) end węzeł := NEXT(węzeł, litera) if OUTPUT(węzeł) <> nil then wypisz pozycję i wypisz wszystkie wartości ze zbioru OUTPUT(węzeł) end end end
Determinizacja automatu
Przy przetwarzaniu jednego znaku może być odwiedzone więcej niż jeden węzeł, tj. najpierw pewna liczba przejść przez krawędzie fail, a następnie przez jedną krawędź etykietowaną literą. Automat można jednak zdeterminizować, tj. zrezygnować z krawędzi fail i określić dla każdego węzła następnik, dzięki czemu dla jednej litery automat zmieni stan dokładnie raz. Wiąże się to jednak ze znacznym wzrostem wymagań pamięciowych.
Dla odróżnienia nowa funkcja przejść nazwana została DETNEXT.
procedure Aho-Corasick-determinizacja(trie) begin kolejka := pusta kolejka węzeł := korzeń drzewa trie for litera in alfabet do węzeł := NEXT(korzeń, litera) if węzeł <> korzeń then dodaj węzeł do kolejki end DETNEXT(korzeń, litera) := węzeł end while kolejka nie pusta do węzeł := weź z kolejki { wykonanie fragmentu procedury Aho-Corasick-wyszukiwanie } for litera in alfabet: { dla liter alfabetu, dla których NEXT jest nieokreślony (NIL) } if NEXT(węzeł, litera) = nil then DETNEXT(węzeł, litera) := DETNEXT(FAIL(węzeł), litera) { lub skopiowanie istniejącego przejścia } else x = NEXT(węzeł, litera) DETNEXT(węzeł, litera) = x dodaj x do kolejki end end end end
Wówczas algorytm wyszukiwania upraszcza się do:
procedure Aho-Corasick-wyszukaj-w-deterministycznym(napis, trie) begin węzeł = korzeń drzewa trie for i := 1 to długość napisu do litera := napis[i] węzeł := DETNEXT(węzeł, litera) if OUTPUT(węzeł) <> nil then wypisz pozycję i wypisz wszystkie wartości ze zbioru OUTPUT(węzeł) end end end
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.
Linki zewnętrzne
- Implementacja w Perlu
- Implementacja w Pythonie na licencji GPLv2 lub nowszej. hkn.eecs.berkeley.edu. [zarchiwizowane z tego adresu (2009-01-18)].
- Darmowa implementacja w C