Aho Corasick

Wprowadzenie

Niniejszy artykuł ma na celu prezentację pewnej bardzo ciekawej i przydatnej struktury danych oraz algorytmów, które na niej operują.
Prezentowany automat jest autorstwa Alfreda Aho i Margaret Corasick.

Problem

Oznaczenia

T – tekst
n – liczba wzorców
A1, A2, …, An – wzorce
L(S) – długość tekstu S
L(A) – suma L(Ai)
∑ – alfabet, czyli zbiór liter

Definicje

Tu (http://algorytmika.wikidot.com/kmp) jest definicja problemu wyszukiwania wzorca. Tym razem interesuje nas problem bardziej ogólny – wzorców jest wiele, tekst jest jeden. Chcemy znaleźć wszystkie wystąpienia wzorców w tekście.

Na wstępie należy rozróżnić, że wypisanie wszystkich znalezionych wystąpień kosztuje pesymistycznie Θ(L(S)*L(A)). Przykład to tekst ‘aaaaaaaaaaa’ i wzorce ‘a’, ‘aa’, ‘aaa’, … . W tym przypadku istnieje kwadratowo wiele dopasowań. Czasami chcemy je wypisać, czasami nie ma na to czasu. Np. w zadaniu „Diagnostyka” musimy jedynie stwierdzić dla każdego wzorca, czy on występuje - to jesteśmy w stanie zrobić w Θ(L(S)+L(A)).

Algorytm najprostszy

Na początek należy zauważyć, że problem ten można rozwiązać poprzez zastosowanie dowolnego algorytmu wyszukującego wzorzec w tekście – KMP, KMR itd.
n razy. Wystarczy rozbić problem na n problemów wyszukiwania jednego wzorca i rozwiązać każdy z osobna.

Deterministycze automaty skończone (DFA)

Abstrakcja

2m3fsih.png

Algorytmika oferuje nam całkiem ogólne narzędzie do rozwiązywania problemów tekstowych. Automaty skończone służą do ilustrowania przebiegu algorytmu, a konkretnie stanu, w jakim się znajduje i przejść między stanami.

Algorytmy które będziemy tworzyli będą bazowały jedynie na wczytywaniu liter przeszukiwanego tekstu po kolei i aktualizacji stanu (w oparciu o wcześniej przygotowaną strukturę – automat).

Stan symbolizuje pewną informację na temat danych, które już przetworzyliśmy. Przykład: możemy stworzyć dwa stany, mówiące o parzystości liczby przetworzonych do tej pory jedynek. Jeśli musimy rozstrzygnąć, czy w danej chwili jest parzyście wiele jedynek, udzielimy odpowiedzi na podstawie aktualnego stanu.

Aby aktualizować stan, musimy wiedzieć, w którym stanie wylądujemy po wczytaniu litery. Założymy że wszystkie stany i wszystkie litery możemy osiągnąć. Stwórzmy tzw. funkcję przejść, która każdej parze (stan, litera) przypisuje pewien stan, do którego przejdziemy po przetworzeniu tej litery.

Musimy jeszcze wiedzieć skąd zacząć, czyli określić stan, w którym znajdzie się algorytm przed rozpoczęciem wczytywania liter.

Automat skończony można przedstawić w formie grafu skierowanego, w którym wierzchołki są stanami, a funkcja przejść tworzy krawędzie.

Liczenie jedynek

Uwaga: w tej sekcji jest chyba jedna nieścisłość, której nie zdążę teraz naprawić.

2bcxvd.jpg

Mamy taki problem: jest sobie tekst nad alfabetem { 0, 1 }, chcemy się dowiedzieć, czy jest on postaci 000…011111…1. Będziemy potrzebowali trzech stanów: 0..0 dla sytuacji, gdy przetworzony tekst składa się z samych zer. 0..01..1 oznacza, że przetworzony tekst jest postaci takiej, jak chcemy. Stan error znaczy, że tekst to 0..01..10x, gdzie x jest czymkolwiek.

Krawędzie modelują przejścia między stanami – jeśli jesteśmy w 0..0 i dostaniemy 1, to przechodzimy do słowa postaci 0..01..1 i taki jest nasz nowy stan. Jeśli następną literą byłoby 0, trafilibyśmy z powrotem do tego samego stanu.

Jeśli jesteśmy w 0..01..1 i nową literą jest 0, tekst przestaje nam się podobać – nie jest tej postaci której szukamy. Stąd nazwa error:P.

A z errora krawędzie mogą prowadzić tylko do errora.

Jak odczytujemy wynik? Po wczytaniu całości jesteśmy w stanie, który nam mówi wszystko co chemy wiedzieć o tekście. Stan 0..01..1 jest równoważny z tym, że nasz tekst jest tej postaci.

Spacer po automacie

Jak już mamy przygotowany automat, możemy go uruchomić, czyli wykonywać następujący pseudokod:

S <- stan początkowy;
move[][] <- funkcja przejść
while(nie przetworzyliśmy całego tekstu) {
    L <- wczytaj_następną_literę();
    S <- move[S][L];
    // w tym miejscu wykorzystujemy informację ze stanu    
}

Teraz przejdźmy do stworzenia prawdziwego, działającego i użytecznego automatu.

Automat Aho-Corasick

Drzewo TRIE

2yxg8d1.jpg
5yxag8.jpg

Jak już napisałem, automat, z jego stanami i przejściami, to nic innego jak pewien graf skierowany. Będziemy tworzyli automat skończony, który umożliwi nam wyszukiwanie wielu wzorców. Zbudujemy go na podstawie tzw. drzewa TRIE. W drzewie tym krawędzie reprezentują litery, a każdy wierzchołek reprezentuje prefiks jednego lub wielu ze słów-wzorców. Korzeń to słowo puste. Podpinamy do niego początki wszystkich wzorców. Dla przykładu rozrysujmy takie drzewo… oto nasze wzorce:
- aab
- aa
- ab
- ba

Rysunek po lewej przedstawia drzewo TRIE stworzone z powyższych wzorców.

Stany automatu

Przejmijmy zatem strukturę TRIE jako podstawę do zbudowania naszego automatu. Zastanówmy się, na jakie pytanie musi odpowiadać automat. Oczywiście na to, ile liter każdego ze wzorców jest w danym miejscu dopasowanych. Jeśli niektóre wzorce mają mniej liter dopasowanych niż inne, nie musimy ich bezpośrednio znać – wystarczy pamiętać aktualnie najdłuższe dopasowanie. Pozostałe dopasowania są jego sufiksami, więc skoro będziemy je w stanie odtworzyć z aktualnego stanu, to obsłużymy je później.
A wszystkie dopasowania tej samej długości możemy pamiętać za jednym zamachem. Czemu? Pomyślmy, kiedy możemy jednocześnie dopasować tyle samo pierwszych liter kilku wzorców naraz. Tylko wtedy, gdy te prefiksy są sobie równe. A jeśli prefiksy są równe, to odpowiada im jeden wierzchołek w drzewie TRIE. Zatem mamy bijekcję między wierzchołkami drzewa a stanami automatu, które definiujemy jako najdłuższe możliwe dopasowanie pewnej ilości wzorców.

Po prawej widać automat utworzony na podstawie drzewa TRIE po lewej.

Funkcja przejść

Zostały jeszcze krawędzie. Mają one odpowiadać na pytanie, do którego stanu przejdziemy, jeśli jesteśmy w stanie X i dochodzi litera Y. Oczywiście jeśli słowo X z literą Y umieszczoną na końcu ma swój odpowiednik w drzewie, prowadzimy krawędź do odpowiedniego stanu. W ten sposób wykorzystujemy wszystkie krawędzie drzewowe – z tą różnicą, że teraz będą one skierowane.

To, co nam pozostało, to wypełnienie pozostałych przejść między stanami – tych, które nie prowadzą do słowa, które jest dłuższe. Patrząc na nasz przykład, musimy stwierdzić, co się stanie, jeśli w stanie, powiedzmy, 'ab' dostaniemy np. literę 'a'. Żaden wzorzec nie ma prefiksu 'aba'. Ale jak już pisałem, z dłuższych dopasowań wynikają krótsze. Musimy tylko znaleźć maksymalny sufiks słowa ‘aba’ (‘ab’ + ‘a’) występujący w drzewie TRIE. W tym przypadku jest to ‘ba’, który występuje w drzewie. Tak więc move[‘ab’][‘a’]=’ba’.

Funkcja FAIL

Zdefiniujmy funkcję FAIL(x) ze zbioru stanów na zbiór stanów, mówiącą nam, który wierzchołek reprezentuje maksymalny sufiks słowa w stanie x, który jest prefiksem któregoś ze wzorców. Przyda się do liczenia tablicy move – funkcji przejść między stanami.
Dla przykładu: FAIL(‘ba’)=’a’.

FAIL to nie jest zwykły prefikso-sufiks, ponieważ choć sufiks musi być sufiksem x, to za prefiks możemy wziąć prefiks dowolnego ze wzorców.
Note: ta funkcja nie stanowi części automatu w rozumieniu ścisłym, korzystamy z niej, aby łatwiej było zaimplementować algorytm.

Implementacja algorytmu

I etap – konstrukcja drzewa TRIE

Przenosimy naszą strukturę danych z papieru na kod. Wierzchołki drzewa oznaczymy liczbami naturalnymi, korzeń to 0.
Jedyne co będziemy pamiętali na temat samego automatu to tablicę move[][], reprezentującą funkcję przejść. No, jeszcze trzeba pamiętać dla każdego wierzchołka czy kończy się w nim jakiś wzorzec.

Potrzebujemy funkcji dodającej wzorzec do drzewa.

Na początku ustawiamy wartości tablicy move[0][c] na -1. -1 będzie oznaczać, że dany wierzchołek nie ma syna połączonego z nim krawędzią o etykiecie c (dla każdego c).

funkcja dodaj_slowo(s) {
    q := 0; // q – miejsce wstawienia
    foreach l in s
        q := dodaj(q,l);
    oznacz ostatnią literę jako koniec wzorca
} 
 
function dodaj(stan, litera) {
    if(move[stan][litera] > -1) return move[stan][litera]; // już kiedyś dodaliśmy tą literę
    nowy := liczba_stanów; // nowy stan
    liczba_stanów++;
    move[stan][litera]=nowy; // stworzyliśmy nowy wierzchołek, czas go połączyć krawędzią z resztą drzewa
    foreach i inmove[nowy][i]=-1;
    return nowy;
}

II etap – wyznaczenie kolejności BFS

Ten etap polega na odpaleniu algorytmu BFS ze źródła 0 na naszym drzewie, aby posortować wierzchołki po ich odległościach od korzenia.

III etap – konstrukcja FAIL i move

Celem tego etapu jest stworzenie z drzewa TRIE prawdziwego automatu skończonego. Musimy po prostu dodać nowe krawędzie tam, gdzie move[s][l]=-1.

FAIL[0]:=0; // umownie przyjmijmy, że najdłuższy  sufiks korzenia występujący w drzewie to sam korzeń
foreach i inif(move[0][i]!=-1) FAIL[move[0][i]]=0 // wszystkim dzieciom korzenia ustawiamy FAIL na korzeń
foreach i inif(move[0][i]=-1) move[0][i]:=0 // pierwszy wiersz move tworzymy ręcznie
dla każdego stanu q (oprócz stanu 0) w kolejności BFS czyń, co następuje {
    foreach i in{
        x := move[q][i];
        if(x=-1) move[q][i]:=move[FAIL [q]][i]; // przejście do najdłuższego dopasowania
        else FAIL [x]=move[FAIL [q]][i]; // ustawmy mu FAILa
    }
}

IV etap – spacer

Tu wykorzystujemy standardowy pseudokod dla automatów skończonych.

S <- stan początkowy;
move[][] <- funkcja przejść
match[] <- dla każdego stanu pamiętamy, czy go odwiedziliśmy
while(nie przetworzyliśmy całego tekstu) {
    L <- wczytaj_następną_literę();
    S <- move[S][L];
    match[S]=true;
    // w tym miejscu można też zliczać lub wypisywać wystąpienia
}
 
dla każdego wierzchołka s w odwróconej kolejności BFS czyń:
    if(match[s]) match[FAIL(s)]:=true; // aby nie zgubić wzorców zagnieżdżonych w innych wzorcach

Athina

Zadanie "Diagnostyka"

Należy stworzyć automat skończony i przeszukać nim tekst za pomocą powyższego pseudokodu.

Zadanie "Wirusy"

Rozwiązanie używa drzewa TRIE.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License