\section{Konečné automaty a Knuth-Morris-Prattov algoritmus}

Hľadáme výskyty vzorky $P$ dĺžky $m$ v texte $T$ dĺžky
$n$. Triviálny algoritmus má časovú zložitosť $O(mn)$ a v priemernom
prípade $\theta(m+n)$. Teraz si ukážeme jeden z klasických algoritmov,
ktoré pracujú v lineárnom čase $O(n+m)$.

Všimnime si najprv, prečo je náš triviálny algoritmus ``zlý''. Vezmime
si vzorku $P = abcabd$ a hľadajme ju v~texte $T =
abcabcabd$. Triviálny algoritmus urobí v~prvom kroku šesť porovnaní
(zistí, že $P[0..4]=T[0..4]$ a $P[5]\ne T[5]$), potom dva krát po
jednom porovnaní (zistí, že $P[0] \ne T[1]$ a $P[0] \ne T[2]$) a
nakoniec znova šesť porovnaní (nájde jediný výskyt vzorky v~texte).
Spolu teda spraví 14 porovnaní. Ak by sme si však vopred predspracovali vzorku, vedeli by sme ju v texte hľadať rýchlejšie. Napríklad pomocou 
prvých 6 porovnaní zistíme, že $P[0..4] = T[0..4]$. Preto
vieme, že sa nám neoplatí posunúť vzorku o jednu pozíciu, lebo hneď
prvé porovnanie by porovnávalo $T[1]=P[1]=b$ s $P[0]=a$. 
Preto môžeme skočiť až na najbližší
výskyt $a$ v $T$, teda na pozíciu 3.
Aj tu ešte môžeme ušetriť porovnania a to preto, že vieme, že 
že $P[0..4]= T[0..4]$ a súčasne $P[0..1] = P[3..4]$. Preto 
pri porovnávaní $P$ a $T[3..8]$ stačí spraviť posledné 4 porovnania. Spolu tak 
ušetríme 4 porovnania. Takéto ušetrenie dosiahneme pomocou
Knuth-Morris-Prattovho algoritmu, ktorý zavedieme pomocou konečných
automatov.

\subsection{Nedeterministický konečný automat}

Majme slovo $P\in\Sigma^*$. Nech $L_P=\{xP|x\in\Sigma^*\}$. Tento
jazyk je regulárny a môžeme preto zostrojiť nedeterministický konečný
automat (NKA), ktorý ho rozpoznáva. Ako príklad budeme uvažovať vzorku
$P=aaba$.

\begin{figure}
\centerline{\includegraphics[scale=1.2]{figures/l03-nka2.eps}}
\caption{Nedeterministický konečný automat akceptujúci jazyk 
$L_P$ pre $P=aaba$.}  
\label{poz3figure1}
\end{figure}

Pre jazyk $L_P$ si zostrojíme NKA, tak ako na obrázku
\ref{poz3figure1}. Po načítaní reťazca $T$ môže tento automat skončiť
v stave $q_i$ ak prefix $P$ dĺžky $i$ je sufixom $T$, t.j.
$$(q_0,T)\vdash^*(q_i,\varepsilon)\Leftrightarrow \mbox{$P[0..i-1]$ je sufix $T$}.$$
Vzorka $P$ má teda výskyt v $T$ na pozícii $i$ práve vtedy, keď 
akceptujúci stav je dosiahnuteľný po načítaní prvých $i+|P|-1$ znakov $T$.
Môžeme teda simulovať činnosť automatu na reťazci $T$ (pre každú pozíciu
si vypočítame množinu dosiahnuteľných stavov) a testujeme túto podmienku. 
Na jednej pozícii $T$ však môže byť až $m$ dosiahnuteľných stavov, 
takže aj takýto algoritmus by fungoval v čase $O(mn)$.

\begin{lstlisting}
S = {0};
for(i=0; i<n; i++){
  S1 = empty_set;
  foreach state j in S { 
     add delta(j, T[i]) to S1;
  }
  if (m in S1){
    print i-m+1;
  }
  S = S1;
}
\end{lstlisting}
Cvičenia: ako implementovať množinu stavov $S$ resp. $S_1$ tak, aby algoritmus
naozaj pracoval v čase $O(mn)$? Aký je vzťah medzi počtom porovnaní v
triviálnom algoritme a súčtom veľkostí množín stavov $S$ v tejto
simulácii?


\subsection{Deterministický konečný automat}

Zostrojme teraz štandardnou podmnožinovou konštrukciu 
k tomuto automatu deterministický
konečný automat. Výsledný automat je na obrázku \ref{poz3figure2}.
Pre tento automat platí nasledovné tvrdenie:
$$(\{q_0\},T)\vdash^*(\{q_{i}\,|\,\mbox{$P[0..i-1]$ je $T$}\},\varepsilon) 
$$
Stavy tohto automatu sú teda podmnožiny stavov NKA, pričom 
stav zodpovedá všetkým prefixom vzorky $P$, ktoré sú sufixami 
prečítaného slova $T$.

\begin{figure}\centerline{\includegraphics[scale=1.2]{figures/l03-dka2.eps}}
\caption{Deterministický konečný automat akceptujúci jazyk $L_P$, ktorý bol
vyrobený z nedeterministického konečného automatu z obrázku
\ref{poz3figure1}.}\label{poz3figure2}
\end{figure}


Všimnime si, že ak poznáme najdlhší prefix $P$, ktorý je sufixom $T$,
vieme odvodiť aj všetky kratšie prefixy $P$, ktoré majú túto
vlastnosť.  Náš deterministický automat má teda zaručene presne $m+1$
stavov, jeden pre každú dĺžku prefixu. Tieto stavy pre jednoduchosť
môžeme aj premenovať: namiesto množiny pôvodných stavov nazveme každý
stav podľa dĺžky najdlhšieho prefixu. Stav $\{q_{a_i},\dots,q_{a_k}\}$
teda premenujeme na $p_{\max\{a_1\dots,a_k\}}$. V takto premenovanom DKA
teda platí
$$(p_0,T)\vdash^*(p_{i},\varepsilon) 
\iff \mbox{$P[0..i-1]$ je najdlhší prefix $P$, ktorý je sufixom $T$}
$$
Príklad takéhoto automatu je na obrázku \ref{poz3figure3}. 
DKA vieme ľahko simulovať na vstupe $T$ a ak sa
dostaneme do akceptačného stavu, našli sme koniec výskytu vzorky $P$. 


\begin{figure}
\centerline{\includegraphics[scale=1.2]{figures/l03-dka2p.eps}}
\caption{Deterministický konečný automat akceptujúci jazyk $L_P$
z obrázku \ref{poz3figure2} po prečíslovaní stavov.}
\label{poz3figure3}
\end{figure}

\begin{lstlisting}
state = 0;
for(i=0; i<n; i++){
  state= delta(state,T[i]);
  if (state==m){
    print i-m+1;
  }
}
\end{lstlisting}

Ak už máme zostrojený automat, časová zložitosť hľadania výskytov
vzoriek v texte je $O(n)$. Ako rýchlo vieme zostrojiť samotný automat? Pri
množinovej konštrukcii by sme dostali čas $O(m^2\sigma)$ a ak by sme sa
veľmi snažili, dal by sa dosiahnuť čas $O(m\sigma)$ (detaily neskôr). 
Zrýchliť sa to už nedá,
lebo potrebujeme celú prechodovú funkciu automatu a tá má veľkosť $m\sigma$.
Tiež si ju musíme celú pamätať a teda pamäťová zložitosť je tiež $O(m\sigma)$.
 
\subsection{Morrisov-Prattov algoritmus 1970}

Morrisov-Prattov algoritmus bol prvý známy algoritmus pracujúci v čase $O(m+n)$. 
Na to, aby sme mali menšiu pamäťovú zložitosť, je potrebné zmenšiť
náš automat.  Pridáme do neho epsilonové prechody, čím už síce nebude
deterministický, ale po epsilonových prechodoch sa budeme hýbať len
vtedy, ak sa nebudeme vedieť hýbať po neepsilonových prechodoch a
preto bude vždy jasné, do ktorého stavu sa posunúť. Výsledný automat
bude mať nasledovnú $\delta$ funkciu:

$$
\delta(i,a)=\left\{
\begin{array}{ll}
i+1 & \mbox{ak $a=P[i]$}\\
sp[i] & \mbox{inak, prechod na $\varepsilon$}
\end{array}
\right.
$$
kde $sp[i]$ je dĺžka najdlhšieho vlastného sufixu $P[0..i-1]$, ktorý
je súčasne prefixom $P$ (pozri príklad na obrázku
\ref{poz3figure3}). Z každého stavu $i$ okrem stavov 0 a $m$ teda
vychádzajú iba dva prechody: jeden do stavu $i+1$ a jeden do
niektorého z predchádzajúcich stavov. Ak zo stavu $i$ ideme po
epsilových hranách, prechádzame postupne po všetkých vlastných
sufixoch $P[1..i]$, ktoré sú súčasne prefixami $P$. Keď sa takto
dostaneme do stavu $j$, z ktorého vychádza prechod označený aktuálnym
znakom na vstupe, použijeme tento prechod.

\begin{figure}
\centerline{\includegraphics[width=0.6\textwidth]{figures/l03-mp.eps}}
\caption{Konečný automat pre MP algoritmus, vzorka $P=ababaca$. 
Epsilonové hrany idúce do 
$q_0$ nie sú v obrázku zakreslené.}\label{poz3figure3}
\end{figure}

Predpokladajme na chvíľku, že máme vypočítané $sp[i]$ pre každé $i$. Na
nájdenie vzorky v texte môžeme simulovať činnosť upraveného automatu.

\begin{lstlisting}
state=0;
for(i=0; i<n; i++){
  while(state>0 && T[i]!=P[state]){ //epsilonove prechody
    state=sp[state];    
  }
  if(T[i]==P[state]){  //prechod do dalsieho stavu
    state++;      
  }
  if(state==m){  //sme v koncovom stave
    print i-m+1;
    state=sp[state];  //z posledneho stavu sa uz neda ist dalej
  }
}
\end{lstlisting}

Tento algoritmus simuluje deterministický konečný automat. Po
spracovaní každého znaku sa ocitne v tom istov stave, ako DKA.
Intuícia za epsilonovými prechodmi je nasledovná. Predstavme si, že po
spracovaní textu $T$ je DKA v stave $p_i$, existuje teda reťazec
$\alpha$ dĺžky $i$, ktorý je sufixom $T$ a súčasne prefixom $P$.  Ak
teraz prečítame automatom ďalší znak $a$ (spracovali sme teda reťazec
$Ta$), potrebujeme nájsť najdlhšie $\beta$ ktorá je sufixom $Ta$ a
prefixom $P$. Ak $\beta\ne \varepsilon$, musí končiť znakom $a$,
t.j. $\beta=\beta'a$. Reťazec $\beta'$ je sufixom $T$ a teda aj
sufixom $\alpha$ a súčasne prefixom $P$ a teda aj prefixom
$\alpha$. Hľadáme teda najdlhšie $\beta'$, ktoré je sufixom
aj prefixom $\alpha=P[0..i-1]$ a pre ktoré je aj $\beta'a$ prefixom
$P$. Ak ideme zo stavu $i$ po epsilonových prechodoch až do stavu 0,
prejdeme cez zoznam všetkých stavov, ktoré zodpovedajú 
sufixom $P[0..i-1]$, ktoré sú súčasne aj prefixami $P$. Prvý z nich, z
ktorého ide šípka na $a$, je ten, ktorý hľadáme.

Tento algoritmus vyzerá kvadraticky, ale nie je.  Ak nerátame {\rm
  while} cyklus, časová zložitosť algoritmu je $O(n)$. Presnejšie,
nech $c_i$ je počet vykonaní riadku 4, potom zložitosť $i$-tej
iterácie je $O(c_i+1)$ a celková zložitosť algoritmu $O(n +
\sum_{i=0}^{n-1} c_i)$.  Vieme, že $0\le c_i<m$, ale ukážeme, že vysoké
hodnoty nemôže nadobúdať príliš často.  Každé vykonanie riadku 4 totiž
zníži hodnotu premennej {\rm state} aspoň o jedna. Hodnota tejto
premennej sa zvýši v každej iterácii for cyklu najviac o 1 (v riadku
$7$).  Zároveň hodnota premennej {\rm state} nebude nikdy nižšia ako
$0$ a preto sa riadok $4$ nemôže vykonať viackrát, ako riadok $7$ a
preto sa vykoná najviac $n$-krát a preto zložitosť celého algoritmu je
$O(n)$.

\paragraph{Vytvorenie automatu.}
Jediné, čo nám chýba, je vyrobenie automatu pre danú vzorku $P$. 
To sa nápadne podobá na samotné vyhľadávanie:

\begin{lstlisting}
sp[0]=sp[1]=0;
j=0;
for(i=2; i<=m; i++){
  // invariant: j=sp[i-1];
  while(j>0 && P[i-1]!=P[j]) {
    j=sp[j];
  }
  if(P[i-1]==P[j]) {
    j++;
  }
  sp[i]=j;
}
\end{lstlisting}

Zdvôvodnenie je podobné ako pri vyhľadávaní: opäť poznáme najdlhší
reťazec $\alpha$ dĺžky $j$, ktorý je vlastným sufixom $P[0..i-2]$ a
sufixom $P$ a hľadáme najdlhšiu $\beta=\beta'P[i-1]$, ktorá je sufixom
aj prefixom $P[0..i-1]$.

\paragraph{Zhrnutie.}
Ako vidíme, MP algoritmus beží v čase $O(n+m)$ a s pamäťou $O(m)$.
Samotný text nemusíme ukladať, môžeme ho čítať a spracovávať po jednom
písmene (napr. pri spracovaní streamovaných médií). Jediná operácia so
znakmi je ich porovnanie na rovnosť a algoritmus preto nie je príliš
citlivý na veľkosť abecedy. Na druhej strane medzi spracovaním dvoch
po sebe idúcich znakov môže prejsť čas až $O(m)$, pričom pri použití 
DKA je tento čas $O(1)$. 

\subsection{Knuth-Morris-Prattov algoritmus 1977}

KMP algoritmus sa veľmi podobá na MP algoritmus, ale má v automate dlhšie
epsilonové prechody, 
a to tak, že nasledujúce znaky sa nesmú rovnať. 
Takže $\delta'(i,\varepsilon)$ je dĺžka $j$ najdlhšieho vlastného sufixu 
$P[0..i-1]$, ktorý je zároveň prefixom $P$ a platí $P[j]\ne P[i]$ (pozri obr. \ref{fig:l03-kmp}). 
Napríklad pre $P=a^m$ KM algoritmus má $\delta(i,\varepsilon)=i-1$ a
KMP algoritmus má $\delta'(i,\varepsilon)=0$. Takže ak sa na vstupe
objaví napr. písmeno b, KMP použije iba jeden epsilonový prechod, kým 
KM môže použiť až $m-1$ prechodov. O takto
upravenom algoritme sa dá dokázať nasledovná veta:

\begin{figure}
\centerline{\includegraphics[width=0.6\textwidth]{figures/l03-kmp.eps}}
\caption{Konečný automat pre KMP algoritmus. Ak ide
$\varepsilon$ hrana do $q_0$, tak hrana v obrázku nie je zakreslená.}\label{fig:l03-kmp}
\end{figure}


\paragraph{Veta:}
Počet $\varepsilon$ prechodov v jednej iterácii 
KMP je naviac $\log_{\phi}(m+1)$,
kde $\phi=\frac{1+\sqrt{5}}{2}$ je zlatý rez.


Predtým, ako vetu dokážeme, uveďme niekoľko definícií a liem.
%pozri Periodicity lemma 2.3 v Crochemore Rytter 1994

\begin{defin} Celé číslo $x$ nazývame periódou slova $S$ ak 
$1\le x \le m$ a pre každé $i\in \{0,1,\dots, |S|-x-1\}$ platí 
$S[i] = S[i+x]$. 
\end{defin}

Podľa tejto definície, dĺžka slova je vždy jeho periódou, slovo však
môže mať aj kratšie periódy. Napríklad slovo abab má periódy 2 a 4,
slovo aaba má periódy 3 a 4 a slovo aaaa má periódy 1,2,3,4.

\begin{lema} 
Ak $p$ a $q$ sú periódy slova $S$ a platí, že $p<q$ a $p+q\le |S|$,
tak aj $q-p$ je perióda $S$.
\end{lema}

\begin{dokaz}
Vezmime nejaké $i\in \{0,1,\dots, |S|-(q-p)-1\}$, chceme dokázať, že
$S[i] = S[i+(q-p)]$. Ak $i+q<|S|$, tak keďže $q$ je perióda, máme, že
$S[i] = S[i+q]$. Podobne, keďže $p$ je perióda, platí, že
$S[i+q-p]=S[i+q]$. Spojením týchto dvoch rovností dostaneme požadované
tvrdenie.


Ak naopak $i+q\ge |S|$, potom $i-p\ge |S|-q-p\ge 0$ a teda keďže
$p$ a $q$ sú periódy, máme $S[i] = S[i-p]=S[i-p+q]$. \qed
\end{dokaz}

Nasledujúca lema sa už týka priamo KMP automatu pre vzorku $P$.

\begin{lema}
Nech $q_{j'}=\delta'(q_{j},\varepsilon)$ a
$q_{j''}=\delta'(q_{j'},\varepsilon)$. Potom $j\geq j'+j''+1$.
\end{lema}

\begin{dokaz}
Lemu dokážeme sporom. Predpokladáme, že $j \le j'+j''$. 

Nech $p=j-j'$ a $q=j-j''$. Pre ich súčet z nášho predpokladu platí
$p+q=j-j'+j-j'' \le j-j+j = j$. Taktiež $q>p$ a $p$ aj $q$ sú periódy
$P[0..j-1]$.  Podľa predchádzajúcej lemy teda aj $q-p$ je perióda.

Z definície $\delta'$ tiež vieme, že $P[j'']\not=P[j']$, čo je ale
spor, lebo $j' = j''+(q-p)$ a keďže $q-p$ je perióda, tieto dva znaky
by mali byť také isté. \qed
\end{dokaz}

\paragraph{Dôkaz vety:}
Nech zo stavu $q_j$ je $k$ prechodov do stavu $q_0$. Dokážeme indukciou vzhľadom na
$k$, že $j\geq F_{k+2}-1$, kde $F_i$ je $i$-te Fibonacciho číslo zadefinované 
rekurenciou $F_0=0$, $F_1=1$, $F_k=F_{k-1}+F_{k-2}$.

\begin{enumerate}
\item 
$k=0$: $j\ge 0 = F_2-1$\\
$k=1$: $j\geq 1 = F_3-1$\\
\item $k\geq 2$

$j\geq j'+j''+1\geq F_{k+1}-1+F_{k}-1+1=F_{k+2}-1$ 
\end{enumerate}

Z definície Fibonacciho čísel sa dá dokázať, že $F_k\geq \phi^{k-2}$, 
z čoho vyplýva $j+1\geq F_{k+2}\geq
\phi^k$ a teda $k\leq \log_{\phi}(j+1)\leq\log_{\phi}(m+1)$. \qed

\subsection{Cvičenia}

\begin{priklad}
Nájdite najdlhší prefix $P$, ktorý sa vyskytuje v~$T$. Riešenie: stačí
si zapamätať najvyšší navštívený stav v MP/KMP algoritme.
\end{priklad}

\begin{priklad}
Nájdite najdlhší sufix $P$, ktorý sa vyskytuje v~$T$. Riešenie:
prevedieme $P$ aj $T$ na zrkadlové obrazy a hľadáme najdlhší prefix
$P^R$ v $T^R$.
\end{priklad}

\begin{priklad}
Máme spočítané hodnoty $sp[i]$ z MP algoritmu, chceme $\delta(i,a)$ z DKA. 
Riešenie: pre každé $a$ v abecede spustíme
\begin{lstlisting}
if(P[0]=='a') {
  delta(0,'a') = 1;
}
else {
  delta(0,'a') = 0;
}
for(i=1; i<=m; i++) {
  if(i<m && P[i]=='a') {
    delta(i,'a')=i+1;
  }
  else {
    delta(i,'a')=delta(sp[i],a);
  }
}
\end{lstlisting}
\end{priklad}

\begin{priklad}
Máme spočítané hodnoty $sp[i]$ z MP algoritmu, chceme sp$_2$ z KMP. Riešenie:

\begin{lstlisting}
sp2[0]=0;
for(i=1; i<=m; i++) {
  if(i==m || P[sp[i]]!=P[i]) {
    sp2[i]=sp[i];
  }
  else {
    sp2[i]=sp2[sp[i]]; 
  }
}
\end{lstlisting}
\end{priklad}

\section*{TO DO}
\begin{itemize}
\item Priebeh triviálneho a zlepšeného algoritmu pre hľadanie vzorky
  abcabd nejako krajšie znázorniť (obrázkom, napr. ako v prehľade od
  Charrasa a Lecroqa uvedenom v zozname literatúry)
\end{itemize}

