Algorytm Aho-Corasicka
 Schemat automatu Aho-Corasicka
| |
| Klasa | Wyszukiwanie ciągów, dopasowywanie ciągów |
|---|---|
| Struktura danych | Skończona maszyna strun |
W informatyce algorytm Aho – Corasick jest algorytmem przeszukiwania ciągów znaków, wynalezionym przez Alfreda V. Aho i Margaret J. Corasick w 1975 r. Jest to rodzaj algorytmu dopasowywania słowników, który lokalizuje elementy skończonego zestawu ciągów („ słownik") w tekście wejściowym. Dopasowuje jednocześnie wszystkie struny. Złożoność algorytmu jest liniowa pod względem długości łańcuchów plus długość wyszukiwanego tekstu plus liczba dopasowań wyjściowych . Zauważ, że ponieważ wszystkie dopasowania zostały znalezione, może istnieć kwadratowa liczba dopasowań, jeśli pasuje każdy podłańcuch (np. słownik = a , aa , aaa , aaaa i ciąg wejściowy to aaaa ).
Nieformalnie algorytm konstruuje maszynę o skończonych stanach , która przypomina trie z dodatkowymi połączeniami między różnymi węzłami wewnętrznymi. Te dodatkowe łącza wewnętrzne umożliwiają szybkie przejścia między nieudanymi dopasowaniami łańcuchów (np. wyszukiwanie cat w trie, które nie zawiera cat , ale zawiera cart , a zatem zakończyłoby się niepowodzeniem w węźle poprzedzonym przez ca ), do innych gałęzi trie, które współdzielą wspólny przedrostek (np. w poprzednim przypadku gałąź dla atrybutu może być najlepszym przejściem poprzecznym). Pozwala to automatowi na przechodzenie między dopasowaniami ciągów bez potrzeby cofania się.
Gdy słownik ciągów znaków jest znany z góry (np. baza wirusów komputerowych ), konstrukcja automatu może być wykonana raz w trybie off-line, a skompilowany automat przechowywany do późniejszego wykorzystania. W tym przypadku jego czas działania jest liniowy względem długości danych wejściowych plus liczby dopasowanych wpisów.
Algorytm dopasowywania łańcuchów Aho – Corasicka stanowił podstawę oryginalnego polecenia Unix fgrep .
Przykład
W tym przykładzie rozważymy słownik składający się z następujących słów: {a, ab, bab, bc, bca, c, caa}.
Poniższy wykres przedstawia strukturę danych Aho – Corasick zbudowaną z określonego słownika, przy czym każdy wiersz w tabeli reprezentuje węzeł w trie, a ścieżka kolumny wskazuje (unikatową) sekwencję znaków od korzenia do węzła.
Struktura danych ma jeden węzeł dla każdego prefiksu każdego łańcucha w słowniku. Więc jeśli (bca) jest w słowniku, to będą węzły dla (bca), (bc), (b) i (). Jeśli węzeł znajduje się w słowniku, jest to niebieski węzeł. W przeciwnym razie jest to szary węzeł.
Od każdego węzła do węzła, którego nazwę można znaleźć przez dodanie jednego znaku, znajduje się skierowany na czarno łuk „potomny”. Mamy więc czarny łuk od (bc) do (bca).
Od każdego węzła do węzła, który jest najdłuższym możliwym ścisłym sufiksem na wykresie, biegnie skierowany na niebiesko łuk „sufiksu”. Na przykład dla węzła (caa) jego ścisłymi przyrostkami są (aa) i (a) i (). Najdłuższy z nich, który istnieje na grafie, to (a). Jest więc niebieski łuk od (caa) do (a). Niebieskie łuki można obliczyć w czasie liniowym, przeprowadzając przeszukiwanie wszerz [potencjalny węzeł sufiksu zawsze będzie na niższym poziomie], zaczynając od korzenia. Cel dla niebieskiego łuku odwiedzanego węzła można znaleźć, podążając za niebieskim łukiem jego rodzica do jego najdłuższego węzła sufiksu i wyszukując potomka węzła sufiksu, którego znak pasuje do odwiedzanego węzła. Jeśli postać nie istnieje jako dziecko, możemy znaleźć następny najdłuższy sufiks (ponownie za niebieskim łukiem), a następnie wyszukać postać. Możemy to robić, dopóki nie znajdziemy znaku (jako dziecko węzła) lub dotrzemy do korzenia (który zawsze będzie sufiksem każdego łańcucha).
Od każdego węzła do następnego węzła w słowniku znajduje się zielony łuk „sufiksu słownika”, do którego można dotrzeć, podążając za niebieskimi łukami. Na przykład istnieje zielony łuk od (bca) do (a), ponieważ (a) jest pierwszym węzłem w słowniku (tj. A). Zielone łuki można obliczyć w czasie liniowym, wielokrotnie przechodząc przez niebieskie łuki, aż do znalezienia niebieskiego węzła, i zapamiętując te informacje.
| Ścieżka | W słowniku | Link sufiksu | Łącze sufiksu dyktowania |
|---|---|---|---|
| () | – | ||
| (A) | + | () | |
| (ab) | + | (B) | |
| (B) | – | () | |
| (ba) | – | (A) | (A) |
| (dziecko) | + | (ab) | (ab) |
| (pne) | + | (C) | (C) |
| (pne) | + | (około) | (A) |
| (C) | + | () | |
| (około) | – | (A) | (A) |
| (caa) | + | (A) | (A) |
Na każdym kroku bieżący węzeł jest rozszerzany poprzez znalezienie jego dziecka, a jeśli to nie istnieje, znalezienie dziecka jego sufiksu, a jeśli to nie zadziała, znalezienie dziecka sufiksu jego sufiksu i tak dalej, ostatecznie kończąc na korzeniu node, jeśli nic wcześniej nie było widoczne.
Gdy algorytm osiągnie węzeł, wyprowadza wszystkie wpisy słownika, które kończą się na bieżącej pozycji znaku w tekście wejściowym. Odbywa się to poprzez wydrukowanie każdego węzła, do którego dotarł, podążając za łączami sufiksu słownika, zaczynając od tego węzła i kontynuując, aż dotrze do węzła bez łącza sufiksu słownika. Ponadto drukowany jest sam węzeł, jeśli jest to pozycja słownika.
Wykonanie na łańcuchu wejściowym abccab daje następujące kroki:
| Węzeł | Pozostały ciąg | Wyjście: pozycja końcowa | Przemiana | Wyjście |
|---|---|---|---|---|
| () | abkab | zacznij od roota | ||
| (A) | bccab | za: 1 | () do dziecka (a) | Bieżący węzeł |
| (ab) | Kakaba | od:2 | (a) dziecku (ab) | Bieżący węzeł |
| (pne) | taksówka | pne:3, c:3 | (ab) do sufiksu (b) do dziecka (bc) | Bieżący węzeł, węzeł sufiksu Dict |
| (C) | Ab | c:4 | (bc) do sufiksu (c) do sufiksu () do dziecka (c) | Bieżący węzeł |
| (około) | B | za:5 | (c) dziecku (ca) | Węzeł sufiksu dict |
| (ab) | od:6 | (ca) dodać przyrostek (a) do dziecka (ab) | Bieżący węzeł |
Dynamiczna lista wyszukiwania
Oryginalny algorytm Aho-Corasicka zakłada, że zestaw ciągów wyszukiwania jest ustalony. Nie dotyczy to bezpośrednio aplikacji, w których nowe ciągi wyszukiwania są dodawane podczas stosowania algorytmu. Przykładem jest interaktywny program do indeksowania, w którym użytkownik przegląda tekst i zaznacza nowe słowa lub frazy do indeksowania tak, jak je widzi. Bertrand Meyer wprowadził przyrostową wersję algorytmu, w której zestaw ciągów wyszukiwania można stopniowo rozszerzać podczas wyszukiwania, zachowując algorytmiczną złożoność oryginału.
Zobacz też
Linki zewnętrzne
- Aho-Corasick w Słowniku algorytmów i struktur danych NIST (15.07.2019)