\section{Regulárne výrazy}

Aj keď by mali byť čitateľovi týchto poznámok regulárne výrazy dôverne známe, nezaškodí pripomenúť
si ich definíciu.

\begin{defin} Regulárny výraz definujeme rekurzívne takto:
\begin{itemize}
    \item $\epsilon$ je regulárny výraz generujúci prázdny jazyk $L(\epsilon) = \{\epsilon\}$
    \item Ak $a \in \Sigma$, tak potom je $a$ regulárny výraz generujúci jazyk $L(a) = \{a\}$
    \item Ak $R_1$ a $R_2$ sú regulárne výrazy aj
        \begin{itemize}
            \item $(R_1)$ a generuje jazyk $L((R_1)) = L(R_1)$
            \item $(R_1 . R_2)$ a generuje jazyk $L((R_1 . R_2)) = L(R_1).L(R_2)$
            \item $(R_1 | R_2)$ a generuje jazyk $L((R_1 | R_2)) = L(R_1) \cup L(R_2)$
            \item $(R_1^*)$ a generuje jazyk $L((R_1)^*) = L(R_1)^* = \cup _{i=0}^{\infty} L(R_1)^i$
        \end{itemize}
\end{itemize}
\end{defin}

Regulárne výrazy nájdu široké uplatnenie v každodennom živote. Napríklad regulárnym výrazom
\verb=[0-9][0-9][0-9] [0-9][0-9]= môžeme overovať slovenské poštové smerovacie čísla. Regulárne
výrazy používa aj unixový program \verb=grep=. Taktiež si môžeme všimnúť, že regulárne
výrazy generujú práve množinu regulárnych jazykov rovnako ako napríklad konečné automaty alebo
regulárne gramatiky.

\paragraph{Príklad:}
Majme regulárny výraz $a(((a.b)|(cd))^*)$ ktorý po vynechaní zátvoriek môžeme zapísať ako
$a(ab|cd)^*$. Tento regulárny výraz generuje jazyk \newline $L(R) = \{a, aab, acd, aabab, aabcd, acdab,
acdcd, \ldots \}$

Pri vyhľadávaní regulárnych výrazov dostaneme na vstup text $T$ dĺžky $n$ a regulárny výraz $R$
dĺžky $m$. Našou úlohou bude nájsť všetky výskyty slov z jazyka $L(R)$.

\subsection{Thompsonov algoritmus (1968)}
Pri spracovávaní regulárnych výrazov by nám mohla prísť vhod aj šikovnejšia reprezentácia
regulárneho výrazu ako len obyčajný reťazec. Jednou z takýchto reprezentácii je aj tzv. parse
tree:

\begin{itemize}
    \item Listami stromu sú prvky abecedy $\Sigma$ alebo prázdne slovo $\epsilon$.
    \item Vnútornými uzlami stromu sú reprezentované operátory $|$ a $.$ s dvoma synmi a operátor
    $*$ s jediným synom.
\end{itemize}

\begin{figure}[h]
    \begin{center}
    \includegraphics[width=0.25\textwidth]{figures/l06-1.eps}
    \caption{Strom regulárneho výrazu}
    \end{center}
\end{figure}

Úlohou Thompsonovho algoritmu je z regulárneho výrazu $R$ za pomoci vyššie popísaného stromu
skonštruovať nedeterministický konečný automat akceptujúci rovnaký jazyk ako $R$. Tento automat si
z parsovacieho stromu zostrojíme jednoducho smerom zdola nahor nasledujúcim rekurzívnym postupom:

\begin{itemize}
    \item Pre jednotlivé uzly budeme konštruovať automaty s jedným počiatočným a akceptačným stavom.
    \item Automat pre $\epsilon$ bude mať počiatočný a akceptačný stav, spojené budú epsilónovým
    prechodom.
    \item Automat pre $a$ bude mať počiatočný a akceptačný stav, spojené budú prechodom na znak $a$.
    \item Automat pre konkatenáciu vyrobíme z jednoduchších automatov tak, že spojíme akceptačný
    stav prvého s počiatočným stavom druhého automatu.
    \item Automat pre zjednotenie vytvoríme tak, že najprv vytvoríme nový počiatočný a akceptačný
    stav. Z počiatočného stavu urobíme $\epsilon$ prechody do počiatočných stavov jednoduchších
    automatov. Z akceptačných stavov jednoduchších automatov povedieme ďalšie prechody na $\epsilon$
    do nového akceptačného stavu.
    \item Automat pre iteráciu zostrojíme tak, že nový počiatočný a akceptačný stav prepojíme
    prechodom na $\epsilon$ alebo viacerými prechodmi cez jednoduchší automat.
    \item Do počiatočného stavu výsledného automatu nakoniec pridáme slučku na každé písmeno abecedy, aby sme
    mohli prečítať ľubovoľne dlhý nezaujímavý úsek textu pred výskytom regulárneho výrazu.
\end{itemize}

\begin{figure}[h]
    \begin{center}
    \includegraphics[width=0.3\textwidth]{figures/l06-2.eps}
    \caption{Ilustrácia rekurzívneho spájania automatov pre jednotlivé operátory regulárneho výrazu}
    \end{center}
\end{figure}

Takouto konštrukciou vieme zostrojit nedeterministický automat, ktorý bude mať pre $m$ uzlov
parsovacieho stromu najviac  $2m$ stavov a $4m$ prechodov. Vieme totiž zaručiť, že každý stav má
najviac dve vstupné a dve výstupné hrany.

Zostrojenie parsovacieho stromu nám zaberie najviac $O(m)$ času. Výsledný automat vieme simulovať v
čase $O(mn)$ Thompsonovým algoritmom. V bitovom poli \verb=B= si budeme pamäť čísla dosiahnuteľných stavov a
postupne ich dopĺňať o ďalšie.

\begin{lstlisting}
B[0] = 1; B[1..k-1]=(0,0,...);
epsilon(B);
for(int i=0; i<n; i++) {
  B2[0..k-1] = 0;
  foreach transition a->b labeled T[i] {
    if(B[a]==1) { B2[b]=1; }
  }
  B=B2;
  epsilon(B);
  if(B[k-1]) { print occurrence ending at i }
}

void epsilon(B) {
  for(int i=0; i<k; i++) {
    if(B[i]) { search(B,i); }
  }
}
void search(B,i) {
  foreach epsilon transition i->j {
    if(! B[j]) {
      B[j]=1; search(B,j);
    }
  }
}
\end{lstlisting}

Cvičenie: Thompsonov algoritmus nájde konce výskytov, ako by sme našli
začiatky, prípadne pre každý koniec najbližší začiatok?


\subsection{Iné prístupy}
Pre vyhľadávanie regulárnych výrazov vieme použiť aj mierne obmeny predchádzajúceho algoritmu.
Môžeme sa v čase $O(m^2 2^m\sigma)$ pokúsiť zostrojit deterministický konečný automat s exponenciálnym
počtom stavov, ktorý ale bude pracovať v čase $O(n)$. Iným prístupom by bolo vytvoriť viacero malých
deterministický automatov, ktoré by sme prepojili do jedného veľkého automatu.

Vyhľadávanie si tiež môžeme zjednodušiť filtrovaním vzorov, o ktorých vieme, že sa v regulárnom
výraze musia vyskytnúť. Zrýchlenie by sme mohli dosiahnuť použitím bitového paralelizmu.

\subsection{Vzorky so žolíkmi}
Môžu nastať situácie, keď nepotrebujeme presne určiť niektoré symboly podslova, ktoré chceme nájsť,
ale vystačíme si s ľubovoľným znakom. Vytvoríme si nový symbol $*$, ktorý bude zastupovať ľubovoľný
iný symbol z abecedy $\Sigma$. Ide teda o špeciálnu podtriedu regulárnych výrazov (pozor, znak $*$ už neznamená Kleeneho uzáver ale žolík).

\paragraph{Príklad:}
Regulárnemu výrazu \verb=aa*b= vyhovujú texty \verb=aaab=, \verb=aabb=,\verb=aacb=,\verb=aadb= atď.

Na vyhľadávanie takýchto výrazov si vieme ľahko upraviť triviálny algoritmus. Stačí rozšíriť
podmienku, ktorou sme overovali rovnosť znakov napríklad takto: 

\begin{verbatim}
if (P[j] == '*' || P[j] == T[i, j] ...
\end{verbatim}

Obdobne vieme upraviť aj algoritmy BNDM a Shift-and.

Časová zložitosť upraveného triviálneho algoritmu ostane $O(nm)$. Upravený algoritmus Shift-and bude
pracovať v čase $O(n + m + \sigma)$. Pomocou sufixových stromov 
si neskôr ukážeme aj algoritmus
pracujúci v čase $O(kn)$, kde $k$ je počet hviezdičiek v regulárnom výraze. Teraz sa však pozrieme
ako sa dá využiť rýchla Fourierova transformácia (Fast Fourier Transform - FFT) na zkonštruovanie
algoritmu pracujúceho v čase $O(n \log m)$.

\subsection{Využitie Fast Fourier Transform na hľadanie vzoriek}
Fourierova transformácia sa hojne používa pri analýze signálu alebo v oblasti počítačového videnia.
Pomocou Fourierovej transformácie si vieme rozložiť zložitý signál na jednotlivé zložky. Efektívny
algoritmus na výpočet Fourierovej transformácie sa však dá použiť na násobenie polynómov. Ukážeme
si, ako pomocou takéhoto násobenia polynómov využitím FFT dokážeme vyhľadávať regulárne výrazy v
texte. Najprv sa však rozpamätajme, čo to vlastne násobenie polynómov je.

\paragraph{Násobenie polynómov.}
K daným polynómom
\begin{eqnarray*}
    A(x) &=& \Sigma_{k=0}^{n-1} a_k x^k \\
    B(x) &=& \Sigma_{k=0}^{n-1} b_k x^k 
\end{eqnarray*}
chceme vypočítať polynóm 
\begin{eqnarray*}
    C(x) &=& A(x)B(x)\\
    C(x) &=& \Sigma_{k=0}^{2n-1} c_k x^k \mbox{kde}\\
    c_k &=& \Sigma_{j=0}^{n-1} a_j b_{k-j}
\end{eqnarray*}

V prípade potreby si môžeme nedefinované koeficienty položiť rovné nule. Triviálnym algoritmom
vypočítame súčin polynómov v čase $O(n^2)$, Fourierovou transformáciou to však zvládaneme v čase
$O(n \log n)$. Ukážme si ale najprv, ako vyhľadať výskyt obyčajnej textovej vzorky výrazu pomocou násobenia polynómov.

\paragraph{Hľadanie vzorky v texte.}
Pozrime sa na znaky našej abecedy na chvíľu ako na čísla. Náš text tak bude nad abecedou $\Sigma = \{1, \ldots, m+1\}$. Pre každé $i=0,\dots n-m$ si vypočítajme výraz
\begin{eqnarray*}
    a_i &=& \Sigma_{j=0}^{m-1} (P[j] - T[i + j])^2
\end{eqnarray*}
Čomu ale takýto výraz zodpovedá? Môžeme si ho predstaviť ako akési ohodnotenie zarovnania textu a
regulárneho výrazu začínajúceho na pozícii $i$.

\begin{figure}
    \begin{center}
    \includegraphics[width=0.35\textwidth]{figures/l06-3.eps}
    \caption{Reprezentácia hodnoty $a_i$}
    \end{center}
\end{figure}

Ďalej si treba uvedomiť, že jednotlivé členy sumy sú rovné nule práve vtedy, 
keď nastáva zhoda na
príslušnom písmene textu a vzorky. Celá suma bude teda rovná nule, ak nastala zhoda na všetkých
pozíciach vzorky a prehľadávaného textu. K ďalším záverom dôjdeme, ak si túto sumu rozpíšeme.

\begin{eqnarray*}
    a_i &=& \Sigma_{j=0}^{m-1} (P[j] - T[i + j])^2 \\
    &=& \Sigma_{j=0}^{m-1} P[j]^2 - 2\Sigma_{j=0}^{m-1} P[j]T[i+j] + \Sigma_{j=0}^{m-1} T[i+j]^2
\end{eqnarray*}

Môžeme si všimnúť, že prvý člen súčtu nezávisí na pozícii vzorky v texte, preto sa dá predpočítať.
Poslednú sumu si síce predpočítať nevieme, ale vieme ju rátať rýchlo pomocou prefixových súm.

\begin{eqnarray*}
    g_i &=& \Sigma_{j=0}^{i-1} T[j]^2 \\
    g_{i+1} &=& g_i + T[i]^2 \\
\end{eqnarray*}

A teda posledný člen súčtu je pre $a_i$ rovný $g_{i+m} - g_{i}$. Ostáva nám vypočítať druhý člen. Tu si
pomôžeme trikom a prehľadávaný text reverzneme. Výsledkom bude výraz, ktorý sa viac podobá na
násobené polynómy spomínané vyššie.

\begin{eqnarray*}
    \Sigma_{j=0}^{m-1} P[j]T[i+j] &=& \Sigma_{j=0}^{m-1} P[j]T^{R}[n - 1 - i - j]  \\
                                  &=& \Sigma_{j=0}^{m-1} P[j]T^{R}[k - j]  
\end{eqnarray*}

Tento výraz už vieme vypočítať pomocou FFT v čase $O(n \log n)$ pre reverznutý text a pôvodný vzor,
t.j. pre $T^R.P$. Túto časovú zložitosť však vieme zlepšiť použitím ďalšieho triku. Vzorový text si
rozdelíme do $\frac{n}{m}$ okienok dĺžky $2m$, pričom nasledujúce okienka sa budú prekrývať o $m$
symbolov. Vyššie naznačeným výpočtom nájdeme vzory v jednotlivých okienkach v čase $O(m \log m)$.
Keďže okienok je $\frac{n}{m}$, výsledný čas bude $O(n \log m)$, ktorý je o čosi lepší, pretože $m < n$.

\begin{figure}
    \begin{center}
    \includegraphics[width=0.5\textwidth]{figures/l06-4.eps}
    \caption{Rozdelenie prehľadávaného textu.}
    \end{center}
\end{figure}

Tento algoritmus zrejme nebudeme chcieť použiť na nájdenie obyčajnej vzorky, pretože máme rýchlejšie
algoritmy. Je však veľmi jednoducho rozšíriteľný na vyhľadávanie vzoriek so žolíkmi.

\paragraph{Využitie Fourierovej transformácie na hľadanie vzoriek s žolíkmi.}
Ak si uvedomíme, že zhodu na jednotlivých znakoch sme v predchádzajúcom algoritme rozoznávali tak,
že jeden člen zložitej sumy je nulový, ľahko vymyslíme spôsob, ako testovať rovnosť na žolíka. Pre
naše potreby bude rozumné, ak si symbol $*$ budeme reprezentovať hodnotou $0$. Výslednú sumu tak
upravíme nasledovne:

\begin{eqnarray*}
    a_i &=& \Sigma_{j=0}^{m-1} (P[j] - T[i + j])^2T[i + j]P[j] \\
    &=& \Sigma_{j=0}^{m-1} P[j]^3T[i + j] - 2\Sigma_{j=0}^{m-1} P[j]^2T[i+j]^2 + \Sigma_{j=0}^{m-1} P[j]T[i+j]^3
\end{eqnarray*}

Výskyt žolíkov povolíme aj v texte, čo nájde uplatnenie pri prehľadávní neúplných alebo poškodených textov, pri ktorých si nemôžeme byť istý všetkými ich symbolmi. Ak sa na danej pozícii vyskytuje
žolík, tak potom príslušný člen sumy bude nulový bez ohľadu na hodnotu toho druhého symbolu. Na
počítanie tohto výrazu použijeme postupne tri FFT, konkrétne na súčiny polynómov $T^3 P$, $T^2P^2$ a
$TP^2$.

Ostáva nám ešte objasniť, ako pomocou Fourierovej transformácie vynásobiť dva polynómy.

\paragraph{Násobenie polynómov pomocou FFT.}
Pre lepšie pochopenie ďalšieho textu nám pomôže, ak si uvedomíme, že polynóm môžeme reprezentovať
dvoma rôznymi spôsobmi, pomocou koeficientov pri jednotlivých $x^k$, alebo podľa aspoň $n+1$ bodov v
rovine \footnote{kde $n$ je stupeň polynómu}, ktorými prechádza graf daného polynómu.
Medzi jednotlivými reprezentáciami vieme konkrétny polynóm
prevádzať, body v rovine jednoducho určíme tak, že ich do polynómu dosadíme. Opačnou transformáciou
je interpolácia.

Reprezentácia pomocou bodov v rovine je pre nás výhodná, lebo pomocou nej vieme polynómy násobiť
veľmi jednoducho. Vezmime si teda $n$ bodov prislúchajúcich polynómu \footnote{$n$ musí byť dosť
veľké, aby sa doň zmestil aj stupeň súčinu polynómov.}:

\begin{eqnarray*}
  (x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n) \\
  y_i = A(x_i)
\end{eqnarray*}

Cez tieto body prechádza práve jedna krivka stupňa menej ako $n$. Súčin dvoch polynómov si takto
vieme zrátať po bodoch. Jednoducho si vypočítame $n$ bodov pre polynóm $B$ v rovnakých súradniciach
$x_i$ ako pre polynóm $A$. Hodnoty $y_i$ pre súčin polynómov $A(x)B(x)$ získame súčinom hodnôt $y_i$
pre jednotlivé polynómy.

Stupeň polynómov s ktorými počítame je však príliš malý, preto ho zvýšime \footnote{Pre vysoké
mocniny nastavíme nulové koeficienty} na $n$ také, aby sa doň zmestil aj výsledný súčin. Ďalej je
potrebné, aby tento stupeň bola mocnina dvojky.

%prepisany odstavec
Hodnoty $y_i$ pre dané polynómy vieme určiť v $O(n^2)$ čase pomocou
Hornerovej schémy ($O(n)$ čas na každé $y_i$). Transformácia v opačnom
smere, t.j. ako z množiny bodov určiť koeficienty polynómu, ktorý cez
ne prechádza by sa dala riešiť sústavu rovníc, kedy by nám každý pár
$(x_i, y_i)$ prispel jednou rovnicou. V oboch prípadoch je
však rýchlejším riešením použitie Fourierovej transformácie.

Z teórie Fourierovej transformácie vyplýva, že jej výpočtom pre daný vektor koeficientov polynómu 
môžeme vyhodnotiť polynóm v $n$ rôznych $n$-tých komplexných odmocninách jednotky. Nasleduje
jednoduché násobenie po správanych súradniciach a spätný prevod do reprezentácie pomocou
koefecientov využitím inverznej Fourierovej transformácie.

Potrebné komplexné odmocniny vypočítame pomocou nasledujúceho vzorca. 
\begin{eqnarray*}
  \omega_n &=& e^{2\pi i} = \cos \frac{2\pi}{n} + i \sin \frac{2\pi}{n}
\end{eqnarray*}

\begin{figure}
    \begin{center}
    \includegraphics[width=0.25\textwidth]{figures/l06-5.eps}
    \caption{Vizualizácia ôsmych odmocnín komplexnej jednotky}
    \end{center}
\end{figure}

Násobenie na jednotkovej kružnici v komplexnej rovine sa správa ako
sčítanie uhlov, pripomína teda sčitovanie modulo 
$n$: $\omega_n^i \omega_n^j = \omega_n^{i + j \bmod n}$.


Pomocou tzv. rýchlej Fourierovej transformácie (Fast Fourier Transform - FFT) vypočítame hodnoty
polynómu v komplexných odmocninách metódou rozdeľuj a panuj \footnote{Práve rozdeľovacia fáza tohto
prístupu spôsobí, že potrebujeme polynóm, ktorého stupeň je mocnina dvojky}. Koeficienty polynómu
$A$ si rozdelíme do dvoch skupín podľa toho, či sú pri párnej alebo nepárnej mocnine $x$ a získame
tak dva polynómy $A_1$ a $A_2$.

\begin{center}
\begin{tabular}{ c c c c c c c c }
         & $x^0$ & $x^1$ & $x^2$ &\dots & $x^{n/2-1}$ &\dots & $x^{n-1}$ \\ 
\hline
  $A$  : & $a_0$ & $a_1$ & $a_2$ &\dots & $a_{n/2-1}$ &\dots & $a_{n-1}$ \\ 
  $A_1$: & $a_0$ & $a_2$ & $a_4$ &\dots & $a_{n-2}$ \\ 
  $A_2$: & $a_1$ & $a_3$ & $a_6$ &\dots & $a_{n-1}$ \\ 
\end{tabular}
\end{center}

Pre takto rozdelený polynóm platí
$A(x) = A_1(x^2) + x A_2(x^2)$

Využitím vzťahu $\omega_n^{2j} = \omega_{n/2}^{j}$ platného pre komplexné odmocniny zrátame
výslednú hodnotu pomocou výsledkov dosiahnutých v rekurzívnom kroku. Hodnoty pre mocniny
$\omega_{n}^{2j}$ už poznáme pre $j \leq \frac{n}{2} - 1$. Ak je $j > \frac{n}{2} - 1$, využijeme
modulárnosť násobenia na kruhu:
$$\omega_{n/2}^{j} = \omega_{n/2}^{n/2} \omega_{n/2}^{j - n/2}
= 1 \omega_{n/2}^{j - n/2} =  \omega_{n/2}^{j - n/2}$$

Teraz už môžeme smelo písať program na výpočet FFT.
\begin{lstlisting}
complex FFT(A,n) {
  if n=1, return (A[0]);
  A1 = A[0,2,4,...,n-2];   Y1 = FFT(A1);
  A2 = A[1,3,5,...,n-1];   Y2 = FFT(A2);
  omega = cos(2*pi/n) + i* sin(2*pi/n);
  x = 1;
  for(int j=0; j<n/2; j++) {
    Y[j] = Y1[j] + x*Y2[j];
    Y[j+n/2] = Y1[j] - x*Y2[j];
    x = omega*x;
  }
  return Y;
}
\end{lstlisting}

Tento výpočet bude pracovať v čase určenom rekurenciou $T(n) = 2T(n/2) + O(1)$ teda v čase $O(n\log n)$.

Celkové násobenie polynómov zostavíme postupom:
\begin{itemize}
\item nájdi $n=2^k$ také, že $A(x)B(x)$ má stupeň $<n$
\item pridaj nulové koeficienty, aby  $A$ a $B$ mali dĺžku $n$
\item spočítaj $A(\omega_n^j)$ pre $j=0\dots n-1$ pomocou FFT
\item spočítaj $B(\omega_n^j)$ pre $j=0\dots n-1$ pomocou FFT
\item spočítaj $C(\omega_n^j) = A(\omega_n^j)B(\omega_n^j)$ pre všetky $j$ v $O(n)$
\item preveď $C(x)$ späť na koeficienty pomocou FFT
\end{itemize}

Zostáva vysvetliť spätný prevod polynómu na koeficienty: TODO, len
krátke poznámky:

Given values of $y_j = A(\omega_n^j)$ for $j=0\dots n-1$, compute $A$
with degree $\le n$. Coefficient $a_j = (1/n) \sum_{k=0}^{n-1} y_k
\omega_n^{-kj}$ (without proof). Compare with original FFT computing
$y_j = \sum_{k=0}^{n-1} a_k \omega_n^{jk}$. Use FFT-like algorithm,
use $Y$ as $A,$ use $\omega_n^{-1}$ instead of $\omega_n$, multiply
result by $1/n$.

\subsection{TO DO}
Spätný prevod na koeficienty pri FFT. Trochu podrobnejšie vysvetliť
rozdeľuj a panuj algoritmus pre FFT.
