\section{Vyhľadávanie viacerých vzoriek a 2D vzorky} 

Máme ${\mathcal
  P}=\{P_1,P_2,\dots,P_z\}$. Nech $m=\sum_i |P_i|$. Chceme nájsť
všetky výskyty reťazcov z ${\mathcal P}$ v $T$. Triviálne riešenie
tejto úlohy by bolo $z$-krát spustiť KMP, čím dostaneme časovú zložitosť
$\sum_iO(|P_i|+n)=O(m+zn)$.  Ak $m=N/2$ aj $z=N/2$ a $n=N/2$, tak
celkový čas bude $O(N^2)$, kde $N = m+n$ je celková veľkosť vstupu.

\subsection{Aho-Corasickovej algoritmus (1975)}

Je to rozšírenie MP algoritmu na viac vzoriek, pričom dosahuje zrýchlenie
oproti jednoduchému algoritmu popísanému vyššie.
Podobne ako pri odvodení MP môžeme zostaviť 
nedeterministický konečný automat rozpoznávajúci 
jazyk $L_{\mathcal  P} = \{xy|x\in \Sigma^*, y\in {\mathcal  P}\}$
(obr. \ref{fig:ac-nda}).

\begin{figure}
\centerline{\includegraphics[scale=0.8]{figures/l03-l8.1}}
\caption{Nedeterministický konečný automat rozpoznávajúci 
$L_{\mathcal  P}$ pre 
${ \mathcal P}=\{{ mama},{ma},{emu},{ema},{mamu}\}$.} 
\label{fig:ac-nda}
\end{figure}

Z nedeterministického automatu chceme spraviť automat podobný 
na automat pre MP algoritmus. Najskôr zostrojíme lexikografický strom 
(pozri časť \ref{kap:trie}). 
Do lexikografického stromu pridáme epsilonové hrany tak, že z vrcholu
pre slovo $u$ ide hrana do vrcholu pre slovo $v$, ktoré je 
najdlhším vlastným sufixom $u$, ktorý je prefixom niektorej vzorky
(príklad na obrázku \ref{fig:ac_complicated}). 

\begin{figure}[th]
\centering\includegraphics[scale=0.8]{figures/l04.0}
\caption{AC automat pre vzorky $\{mama, ma, emu, ema, mamu\}$, 
epsilové prechody sú čiarkovane, epsilonové prechody do $q_0$ nie sú
znázornené.}
\label{fig:ac_complicated}
\end{figure}

Na danom texte môžeme tento automat simulovať podobne ako MP automat a
v každom kroku bude stav predstavovať najdlhší sufix načítaného
reťazca, ktorý je súčasne prefixom niektorej vzorky. Musíme však
zmeniť spôsob vypisovania, lebo niektoré vzorky môžu byť podreťazcom
iných vzoriek a teda na danej pozícii potrebujeme vypísať
výskyty všetkých sufixov, ktoré sú vzorkami v ${\mathcal P}$.
Jedna možnosť by bola v každom stave prejsť po epsilonových hranách až
do $q_0$ a vypísať všetky stavy na tejto ceste, ktoré zodpovedajú
niektorej vzorke. Aby sme ale nemuseli prechádzať aj cez stavy, ktoré
nevypisujeme, pridáme si špeciálne výstupné hrany. Z vrcholu pre slovo
$u$ ide výstupná hrana do vrcholu pre najdlhšiu vzorku, ktorá je
vlastným sufixom $u$, alebo má hodnotu null, ak taká vzorka
neexistuje. Výstupné hrany teda tvoria spájaný zoznam výskytov, ktoré
treba vypísať.  Je to podmnožina spájaného zoznamu tvoreného
epsilonovými hranami.

\paragraph{Príklad:} 
V automate na obrázku \ref{fig:ac_complicated} pôjdu výstupné hrany z 
$q_4$ a $q_8$ do $q_2$ a zo všetkých ostatných vrcholov do null.
Na obrázku \ref{fig:ac_linear} je automat pre množinu vzoriek
$\{a,a^3,a^5\}$ aj s výstupnými hranami.

\begin{figure}[ht]
\centering\includegraphics[scale=1.1]{figures/l05-ac.eps}

\caption{Automat pre vzorky $\{a,a^3,a^5\}$, 
bodkované hrany sú výstupné.}\label{fig:ac_linear}
\end{figure}

Vrchol v lexikografickom strome môže mať napríklad nasledovnú štruktúru:
\begin{itemize}
\item $parent$: smerník na rodič vrchola
\item $child(a)~\forall a \in \Sigma$: pole smerníkov na deti
\item $last$: posledný znak slova pre tento vrchol, 
t.j. $a\in \Sigma$ také, že $parent.child[a]=this$
\item $id$: číslo vzorky/null
\item $epsilon$: epsilonová hrana
\item $output$: výstupná hrana
\end{itemize}

Predspracovanie sa bude skladať z nasledovných krokov:
\begin{enumerate}
\item Vytvorenie lexikografického stromu
\item Nájdenie epsilonových hrán
\item Nájdenie výstupných hrán
\end{enumerate}

Potom môže nasledovať samotný Aho-Corasickovej vyhľadávací algoritmus:

\begin{lstlisting}
v=root;
for (i=0; i<n; i++) {
  // hladame aktualny stav po epsilonovych hranach
  while (v!=root && v.child(T[i])==null) { 
    v=v.epsilon;
  }
  // ak sa da, posunieme sa o jedno dopredu
  if (v.child(T[i])!=null) {
    v=v.child(T[i]);
  }
  // vypis vyskytov po vystupnych hranach
  u=v;
  while (u!=null) {
    if (u.id!=null) {
      print u.id, i-|P[u.id]|+1;
    }
    u=u.output;
  }
}
\end{lstlisting}

\paragraph{Zložitosť.}
Samotný algoritmus vykoná najviac $n$ iterácií vo vonkajšom cykle, zaujíma nás
zložitosť vnútornej časti -- tu sa najskôr nájde po epsilonových hranách prvý
uzol, ktorý má potomka pre aktuálne písmeno, a potom (ak je to možné) sa vykoná
jeden krok na toto písmeno. Dôležité je, že spätných epsilonových krokov
sa počas celého algoritmu vykoná najviac toľko, 
koľko sa vykoná krokov do potomkov uzlov -- a keďže
týchto sa vykoná najviac $n$, aj spätných krokov bude najviac $n$. Celkovo
dostávame pre tieto časti $O(n)$.

Posledná dôležitá časť je druhý $while$-cyklus, ktorý postupne prechádza po
výstupných hranách a vypisuje výskyty vzoriek. Počas celého výpočtu sa po
výstupných hranách prejde $k$-krát, kde $k$ je celkový počet nájdených 
výskytov. Zložitosť je teda $O(n+k)$.

\paragraph{Výpočet $\varepsilon$-prechodov.}

Najskôr nastavíme koreňu epsilonový prechod do samého seba a potom pre
všetky ostatné vrcholy zavoláme funkciu findepsilon(v), pričom
postupujeme v poradí prehľadávania do šírky, takže najskôr spracujeme
všetky vrcholy v hĺbke 1, potom všetky vrcholy v hĺbke 2 atď.

\begin{lstlisting}
void findepsilon(node v) {
  // Predpokladame u.epsilon je zname 
  // pre vsetky slova u kratsie ako v
  a = v.last;
  u = v.parent.epsilon;
  while (u.child(a)==null && u!=root) {
    u=u.epsilon;
  }
  if (u.child(a)!=null) {
    u=u.child(a);
  }
  v.epsilon=u;
}
\end{lstlisting}

\paragraph{Zložitosť.}
Uvažujme cestu v lexikografickom strome z koreňa po list pre konkrétnu
vzorku $P_i$ a sčítajme čas potrebný na volania findepsilon pre všetky
vrcholy na tejto ceste. Uvažujme hĺbku vrchola $u$. 
Na začiatku cesty je táto hodnota 0 a vždy je nezáporná.  V
každom volaní funkcie sa hĺbka zvýši najviac o 1, takže celkový počet
zvýšení je najviac $|P_i|$. Hĺbka vrchola $u$ sa zníži aspoň o jedna
každou iteráciou while cyklu, takže týchto iterácií je tiež najviac
$|P_i|$.  Každú cestu, ktorá končí v liste pre $P_i$ teda spracujeme v čase
$O(|P_i|)$.  Celkový čas teda je $O(m)$, lebo v algoritme síce 
spracovávame striedavo vrcholy z rôznych
ciest, každý vrchol je však aspoň na jednej ceste, takže jeho čas
výpočtu aspoň raz započítame. 

\paragraph{Výpočet výstupných hrán.}
Pre každý vrchol $v$ chceme nájsť prvý epsilonový prechod, ktorý sa má
vypísať. 

\begin{lstlisting}
void find_output(node v) {
  // Predpokladame w.output je znamy pre vsetky slova 
  // kratsie ako v. 
  u=v.epsilon;  // prvy epsilonovy prechod
  if (u.id!=null) { // ak je vzorka, ukazujeme nanho
    v.output=u;
  } else {          // ak nie je vzorka, jeho najblizsi vystup
    v.output=u.output;
  }
}
\end{lstlisting}

%% fig 3

%novy odstavec
Ako sme videli v časti \ref{kap:trie}, lexikografické stromy pri
veľkej abecede potrebujú veľa pamäte na uloženie poľa detí, v ktorom
bude väčšinou veľa prázdnych položiek. Ak zarátame aj čas na
inicializáciu tejto pamäte, algoritmus bude bežať v čase $O(m\sigma +
n + k)$ a v pamäti $O(m\sigma)$. Ak použijeme nejakú zložitejšiu
štruktúru, napríklad vyvážený binárny vyhľadávací strom, dostaneme
algoritmus so zložitosťou $O((m+n)\log\sigma + k)$ a pamäťou $O(m+n)$.

\paragraph{Počet výskytov.}
Pre abecedu konštantnej veľkosti má Aho-Corasickovej algoritmus časovú
zložitosť $O(m+n+k)$, kde $k$ je počet výskytov. 
Aké veľké môže byť $k$ ako funkcia $N$? 
Ukážeme, že Aho-Corasickovej algoritmus má v najhoršom prípade
zložitosť $\Theta(N\sqrt{N})$.  Najskôr ukážeme dolný odhad, t.j. že
existuje vstup, na ktorom $k=\Omega(N\sqrt{N})$. Uvažujme množinu
vzoriek $\{a, a^2, \cdots, a^{\sqrt{n}}\}$ a text $T=a^n$.  Súčet
dĺžiek vzoriek je $\Theta(n)$, teda $N=\Theta(n)$. Vzorka $a^i$ má
výskyt na každej pozícii od 1 po $n-i+1$, čo je aspoň
$n-\sqrt{n}+1$. Celkový počet výskytov všetkých vzoriek je teda
$\Theta(n\sqrt{n}) = \Theta(N\sqrt{N})$.

Pre horný odhad musíme dokázať, že $k$ nikdy nebude viac ako
$O(N\sqrt{N})$. Vzorky rovnakej dĺžky majú vždy neprekrývajúce sa
výskyty a preto ľubovoľný počet vzoriek dĺžky $i$ má spolu najviac
$n-i+1$ výskytov. Stačí nám teda uvažovať vzorky typu $a^i$ v texte
$a^n$.  Takisto pre dané $z$ a $n$ dosiahneme najvyššie $k$ ako
funkciu $N$, ak máme čo najkratšie vzorky, lebo dlhšie vzorky znižujú
$k$ a zvyšujú $N$. Stačí teda uvažovať vzorky $\{a, a^2, \cdots,
a^z\}$. Potom $N = n+z(z+1)/2$ a $k=z(n+1) - z(z+1)/2$.  Aby sme
overili, že $k$ je najviac $O(N\sqrt{N})$, stačí do vzťahu pre $k$
dosadiť $n=N-z(z+1)/2$, zderivovať ako funkciu od $z$ a nájsť maximum.

\subsection{Cvičenia}

Čas Aho-Corasickovej algoritmu je $O(n+m+k)$, čo je horšie než
lineárne pre veľké $k$. Závislosť od $k$ je nevyhnutná, ak chceme
vypísať všetky výskyty, ale ak nám stačí iná informácia, vieme
algoritmus upraviť, aby bežal v čase $O(n+m)$.

\paragraph{Príklad:} Modifikácia Aho-Corasickovej algoritmu, aby v čase $O(m+n)$
zistil, či je v texte výskyt aspoň jednej vzorky.

\paragraph{Riešenie:} Namiesto vypisovania všetkých výskytov skontrolujeme len 
či aktuálny vrchol $v$ je vzorka alebo či $v.output$ je vzorka.

\paragraph{Príklad:} Celkový počet výskytov $k$. 
\paragraph{Riešenie:} V každom vrchole je navyše $v.count$ -- počet sufixov $v$,
ktoré sú z $P$. 

\paragraph{Príklad:} Nájsť všetky vzorky, ktoré majú aspoň jeden výskyt. 
\paragraph{Riešenie:} V každom vrchole $v$ mám ísť po ceste výstupných hrán až do koreňa. Poznačím si, či som konkrétny vrchol už vypísal a akonáhle nájdem
vrchol, ktorý som už vypísal, skončím. Po každej linke prejdem iba raz. Liniek
je $m$, práca behania po výstupných hranách je $O(m)$.


\paragraph{Príklad:} Chceme vektor dĺžky $m$, v ktorom bude uložený počet
výskytov každej vzorky v texte. 
\paragraph{Riešenie:} Počítadlo v každom vrchole, ktoré hovorí, koľko ráz sa
cezeň prešlo. Nakoniec chceme pre každý vrchol spočítať jeho počet aj počet pre všetky stavy, z ktorých sa do aktuálneho stavu vieme dostať po epsilonových hranách. 
\begin{lstlisting}
  for each v in reverse BFS order { // od najhlbsich vrcholov
    w=v.epsilon;
    w.passes+=v.passes; 
  }
\end{lstlisting}

\subsection{Bakerov-Birdov algoritmus pre vyhľadávanie matíc}

Vzorka $P$ aj text $T$ sú vo forme matice, ktorej prvky sú z abecedy $\Sigma$. 
Hľadáme súradnice ľavého
horného rohu všetkých výskytov $P$ v $T$. Rozmery $m$ a $n$ udávajú
celkový počet prvkov v jednotlivých maticiach, t.j. $m=m_1 m_2$ a
$n=n_1 n_2$, kde $m_1\times m_2$ a $n_1\times n_2$ sú rozmery
matíc $P$ a $T$.


Baker-Birdov algoritmus využíva Ahov-Corasickovej algoritmus na
vyhľadávanie viacerých vzoriek. Predpokladajme najskôr, že všetky
riadky matice $P$ sú navzájom rôzne. Algoritmus najskôr vytvorí
automat pre všetky riadky vzorky $P$, a následne ním vyhľadávame
postupne na všetkých riadkoch vstupu $T$, pričom vypĺňame maticu $A$
nasledovne:

$$ A[i,j] = 
\left\{ 
	\begin{array}{ll}
		k & \parbox{8cm}{ak $k$-ty riadok $P$ sa vyskytuje v matici $T$ na riadku $i$ od pozície $j$,} \\
		-1 & \mbox{inak.} \\
	\end{array}
\right.
$$

Na takto vyplnenej matici $A$ môžeme teraz po stĺpcoch spustiť
napríklad KMP, ktorý vyhľadáva postupnosť čísel, ktorá zodpovedá
vyhľadávanej vzorke (teda slovo $1,2,3,\dots, m_1$). Pokiaľ túto 
postupnosť v niektorom stĺpci nájdeme, našli sme zároveň výskyt
pôvodnej vzorky $P$. Všimnime si, že tu ide o vyhľadávanie 
nad veľkou abecedou, to však nezhoršuje zložitosť KMP algoritmu.

Ak sa riadky v $P$ opakujú, zitíme to pri budovaní lexikografického
stromu a všetkým zhodným riadkom pripradíme to isté číslo.

\paragraph{Príklad:}
Majme maticu
$$
P = 
\left(
\begin{array}{l}
    aa \\
    ba \\
    aa \\
\end{array}
\right).
$$
V Aho-Corasickovej algoritme hľadáme vzorky $P_1=aa, P_2=ba$.
Potom pomocou KMP hľadáme vzorku 1,2,1 v nejakom stĺpci matice $A$.

Celková zložitosť tohto algoritmu pre konštantnú abecedu je $O(n+m)$. Člen $k$
sa nevyskytuje, lebo výskyty vzoriek pre Aho-Corasickovej algoritmus
sa neprekrývajú a teda ich je spolu najviac $n$.


