Rozdział 12: Problemy tekstowe związane z automatami

W module tym zakładamy elementarną znajomość pojęć z przedmiotu: Automaty, języki i obliczenia.

Automaty skończone są modelem bardzo uproszczonych algorytmów tekstowych, automat czyta on-line tekst i za każdym razem daje odpowiedź, czy wczytany dotychczas prefiks ma odpowiednią własność. W ten sposób automat rozwiązuje problem string-matching otrzymując na wejściu strumień symboli tekstu, w którym szukamy wzorca. Ten tekst nie jest zapamiętywany.

W naszym przypadku interesować nas będzie to, czy aktualnie wczytany tekst kończy się wystąpieniem wzorca, inaczej mówiąc, czy automat akceptuje język $\Sigma^*x$, gdzie $\Sigma$ jest alfabetem wejściowym, a $x$ jest wzorcem.

Deterministyczny automat skończony jest formalnie zadany (wyspecyfikowany) jako
$$A = (\Sigma,\, Q,\, \delta,\, q_0,\, F), $$
gdzie $Q$ jest skończonym zbiorem stanów, $q_0$ jest stanem początkowym, $F$ jest tzw. zbiorem stanów akceptujących (ale nie kończących obliczenie - w definicji automatu nie występuje pojęcie stopu).

Algorytm znajdowania wystąpień wzorca wygąda następująco:

$q := q_0$
repeat
- wczytaj kolejny symbol $\alpha$ tekstu
- $q := \delta(q,\, \alpha)$
- if $q \in F$ then wypisz kolejne wystąpienie wzorca

Zamiast $q' = \delta(q,\, \alpha)$ będziemy też pisać $q \stackrel{\alpha}{\rightarrow} q'$.

Automaty dla jednego wzorca

Niech $w$ będzie wzorcem. Deterministyczny automat $A_w$ akceptujący język $\Sigma^* w$ można skonstruować biorąc za zbiór stanów $Q$ wszystkie prefiksy słowa $w$ ($A$ ma zatem $\vert w \vert + 1$ stanów) oraz przejścia $v \stackrel{\alpha}{\rightarrow} u$, gdzie $u$ jest maksymalnym właściwym sufiksem słowa $v \alpha$ będącym jednocześnie prefiksem $w$. Definiujemy:

$Q$ jest zbiorem prefisków $w$, włącznie z pustym;
$q_0$ jest słowem pustym;
$F = \lbrace w \rbrace$.

Niech $P$ będzie tablicą prefikso-sufiksów dla $w$, przy czym będziemy indeksować tablicę prefiksami $w$. Wtedy konstruujemy funkcję $\delta$ (program automatu) następująco:

$\delta(q_0,\, \alpha) := q_0$ dla każdego $\alpha \in \Sigma$
for $q \in Q$, $q$ niepuste, w kolejności rosnących długości $q$ do
- if $u \alpha \in Q$ then $\delta(u,\, \alpha) := u\alpha$
  else $\delta(u,\, \alpha) := \delta(P[u],\, \alpha)$

Zadanie

Udowodnić, że jeśli w automacie dla jednego wzorca usuniemy tranzycje prowadzące do stanu $q_0$, to mamy co najwyżej $2n-1$ tranzycji. Dowieść, że liczba nietrywialnych przejść "wstecznych", tj. przejść postaci $v \stackrel{\alpha}{\rightarrow} u$, gdzie $ \vert v \vert > \vert u \vert > 0$, jest nie większa niż $\vert w \vert$. Zauważmy, że daje to możliwość reprezentacji automatu o rozmiarze proporcjonalnym do $\vert w \vert$ (przejścia postaci $v \stackrel{\alpha}{\rightarrow} \epsilon$ możemy pominąć).

Wskazówka: wykazać, że dla każdej liczby $k$ istnieje co najwyżej jedno nietrywialne przejście wsteczne, takie, że $\vert v \alpha \vert - \vert u \vert = k$.

Zadanie

Załóżmy, że dla każdego stanu automatu trzymamy "tranzycje" w liście posortowanej względem "długości" stanu, do którego tranzycja prowadzi. Mając taki automat możemy wykonywać string-matching brutalnie, w danym momencie szukamy tranzycji dla danej litery przeszukując listę liniową. Udowodnić, że daje to liniowy, niezależny od rozmiaru alfabetu, algorytm dla string-matchingu. Algorytm ten jest znany jako algorytm Simona.

Automat dla wielu wzorców

Załóżmy, że mamy teraz skończony zbiór $X$ wzorców o łącznej sumie długości $n$. Załóżmy dla uproszczenia, że żaden wzorzec ze zbioru $X$ nie jest prefiksem innego wzorca z $X$. Konstruujemy automat akceptujący język $\Sigma^*X$.

Automat dla $\Sigma^*X$ możemy konstruować podobnie jak dla jednego wzorca. W tym wypadku:

zbiór $Q$ stanów jest zbiorem wszystkich prefiksów wzorców, "szkielet" automatu jest drzewem $T$, odpowiadającym strukturze prefisków;
stan początkowy (korzeń drzewa) odpowiada słowu pustemu;
stany akceptujące to słowa należące do $X$ (liście drzewa $T$);
$\delta(u,\, \alpha)$ jest maksymalnym właściwym sufiksem słowa $u \alpha$ będącym jednocześnie prefiksem pewnego wzorca ze zbioru $X$.

Przejście $\delta$ jest w szkielecie "do przodu" jeśli z prefiksu $u$ prowadzi do pewnego prefiksu $u \alpha$. Pozostałe przejścia są "w tył".

Metoda 1: algorytm Aho-Corasick

Pierwsza metoda polega na wstępnym obliczeniu uogólnionej tablicy $P$ prefisko-sufisków, a następnie za jej pomocą skonstruowanie automatu podobnie jak to wcześniej robiliśmy. $P[u]$ jest najdłuższym właściwym sufiksem $u$ będącym prefiksem pewnego wzorca ze zbioru $X$.

Zadanie

Skonstruować algorytm obliczający tablicę $P$ dla wielu wzorców w czasie $O(\vert x_1 \vert + \vert x_2 \vert + \ldots \vert x_k \vert)$ gdzie $x_1,\, x_2, \ldots x_k$ są wzorcami.

Mając tę tablicę konstruujemy funkcję $\delta$ (program automatu) następująco:

$\delta(q_0,\, \alpha) := q_0$ dla każdego $\alpha \in \Sigma$
for $q \in T$, $q$ niepuste, w kolejności BFS na drzewie $T$ do
- if $u \alpha \in T$ then $\delta(u,\, \alpha) := u \alpha$
  else $\delta(u,\, \alpha) := \delta(P[u],\, \alpha)$

Metoda 2: konstrukcja bezpośrednia

Dla wielu wzorców "bezpośrednia" metoda polega na przechodzeniu drzewa $T$ prefiksów wzorców metodą BFS. Na początku tworzymy automat poziomu zerowego, jest to zapętlony (dla każdego symbolu) korzeń drzewa $T$.

$\delta(q_0,\, \alpha) := q_0$ dla każdego $\alpha \in \Sigma$
for $u \alpha \in T$, $\alpha \in \Sigma$, w kolejności BFS na drzewie $T$ do
- $w := \delta(u,\, \alpha)$
- $\delta(u,\, \alpha) := u \alpha$
- if $w \beta$ jest prefiksem pewnego wzorca then $\delta(u \alpha,\, \beta) := w \beta$
  else $\delta(u \alpha,\, \beta) := \delta(w,\, \beta)$.

Na przykład jeśli zbiór wzorców jest $\lbrace abab,\, babb,\, bba \rbrace$ i mamy automat dla zbioru z poziomu drugiego $\lbrace ab,\, ba,\, bb \rbrace$ to automat dla następnego poziomu możemy zacząć od liczenia tranzycji dla stanu odpowiadającego prefiksowi $bab$, tworząc nowy stan odpowiadający prefiksowi $bab$, kopiując przejścia dla nowego stanu ze stanu $w = ab$, do którego prowadzi przejście etykietowane $b$ ze stanu $u_i = ba$, poza przejściem $\delta(bab,\, a) = w \; a)$ gdyż $w\; a$ jest prefiksem pewnego wzorca.

Sprawdzanie równoważności automatów

Jeśli mamy dwa automaty dające algorytmy dla tego samego problemu, to chcielibyśmy móc szybko sprawdzić, czy automaty realizują tę samą funkcję: wejście $\Rightarrow$ wyjście. Dla mocniejszych modeli obliczeniowych nie ma algorytmów na sprawdzanie tego typu równoważności. Deterministyczne automaty skończone są użyteczne też dlatego, że są one algorytmicznie łatwe.

Zamiast sprawdzać równoważność dwóch automatów łatwiej sprawdza się równoważność dokładnie dwóch stanów $q_1$, $q_2$ tego samego automatu. W algorytmie używamy struktury danych dla problemu FIND-UNION. Jeśli zaczynamy od podziału trywialnego (każdy element w klasie jednoelementowej) to $n$ operacji $find$ i $union$ możemy wykonać w łącznym czasie $O(n \log^*n)$ (odsyłamy do przedmiotu ASD).

Początkowo mamy podział na bloki będące singletonami;
Wstawiamy parę $(q_1,\, q_2)$ do kolejki $K$;
while kolejka niepusta do
- $(p,\, q) := K.pop()$;
- $A := Find(p)$;
- $B := Find(q)$;
- if $A \neq B$ then
  - $Union(A,\, B)$;
  - $\forall\; \alpha \in \Sigma \quad K.push((\delta(p,\, \alpha),\; \delta(q,\, \alpha) ))$;
- Na końcu sprawdzamy czy jakiś blok zawiera jednocześnie stan akceptujący i nieakceptujący: wtedy (i tylko wtedy) początkowe stany nie są równoważne.

Zadanie

Udowodnić poprawność tego algorytmu. Algorytm działa w czasie $O(n \log^*n)$, jeśli alfabet jest stałego rozmiaru.

Minimalizacja deterministycznego automatu skończonego

Innym problemem teorio-automatowym, dla którego istnieje efektywny algorytm jest problem minimalizacji. Można ten problem rozwiązać w czasie $O(n \log n)$, ale algorytm jest dosyć wyrafinowany. Pokażemy niezmiernie prosty algorytm działający w czasie $O(n^2)$, redukując w bardzo prosty sposób nasz problem do problemu teoriografowego: przechodzenie grafu skierowanego.

Tworzymy graf $G$, gdzie wierzchołki budujemy z par stanów $(\delta(s,\, \alpha),\; \delta(s',\, \alpha)) \rightarrow (s,\, s')$ dla każdej pary stanów $s,\, s'$ i symbolu $\alpha \in \Sigma$. Stany $s,\, s'$ nie są równoważne wtedy i tylko wtedy, gdy istnieje w $G$ ścieżka od $F \times (Q-F) \cup (Q-F) \times F$ do $(s,\, s')$. Daje to algorytm $O(n^2)$ na minimalizację automatu.

Jeśli policzyliśmy relację równoważności dla wszystkich par stanów to sklejamy klasy równoważnych stanów, w rezultacie otrzymujemy automat minimalny (złożony ze stanów osiągalnych ze stanu początkowego).

Zadanie

Mówimy, że dwa stany są $i$-równoważne, gdy są równoważne z dokładnością do słów długości co najwyżej $i$. Niech $R_i$ oznacza relację $i$-równoważności. Udowodnić, że $R_i = R_{i+1}$ implikuje $R_i = R_{i+2}$ oraz $R_i$ jest końcową relacją równoważności stanów. Wynika stąd, że dwa stany są równoważne gdy są równoważne z dokładnością do słów (wejść automatu) długości co najwyżej $n$, gdzie $n$ jest liczbą stanów automatau.