\section{Sufixové polia}
Sufixové polia sú jednoduchšia štruktúra podobná sufixovým stromom. Problém pri sufixových stromoch je pamäťová náročnosť na ich uloženie. V počítači vieme uložiť $n$ znakový reťazec nad binárnou abecedou v pamäti veľkosti $n/8\, \mathtt{B}$. Sufixový strom pre tento reťazec pri priamočiarej implementácii potrebuje pre každý z $2n-1$ vrcholov dva indexy do reťazca, pričom vo vnútorných vrcholoch navyše potrebujeme smerníky na dve deti a v listoch index začiatku sufixu, čo je $7n$ čísel alebo smerníkov. Na 32-bitovom počítači potrebujeme pamäť $28n\, \mathtt{B}$. Často si však ukladáme vo vrcholoch aj ďalšie informácie, napríklad smerník na rodiča, reťazcovú hĺbku, sufixovú linku a podobne.

\begin{defin}
Sufixové pole reťazca $S$ je pole všetkých sufixov reťazca v lexikografickom usporiadaní. 
\end{defin}

\begin{priklad}
V lexikografickom usporiadaní $ma\$ < mama\$ < mamu\$$. Znak \$ budeme pouvažovať za prvý v abecede. Sufixové pole pre $S = mama$
(označujeme $SA$) je pole $SA=(5,4,2,3,1)$. Tieto čísla zodpovedajú reťazcom $\$$, $a\$$, $ama\$$, $ma\$$, $mama\$$ a sú to indexy začiatku príslušného podreťazca.
\end{priklad}

Vidíme, že na uloženie sufixového poľa potrebujeme podstatne menej pamäte, ako na uloženie sufixového stromu.

\subsection{Vyhľadávanie vzorky v sufixovom poli} 

Ak máme sufixové pole pre reťazec $T$, hľadáme výskyty vzorky $P$ v $T$. 

\paragraph{Algoritmus 1.}
Keďže je toto pole usporiadané, môžeme použiť binárne vyhľadávanie.
Hľadáme teda úsek v poli od $i$ po $j$, pre ktorý všetky sufixy
$SA[i]\dots SA[j]$ začínajú $P$.

\begin{lstlisting}
search(X) {
  //najdi max i take, ze T[SA[i]..n]<X 
  L = 0; R = n;
  while(L < R){
    k = (L + R + 1) / 2;
    if(T[SA[k]..n]<X) { L = k; }
    else { R = k - 1; }
  }
  return L;
}
\end{lstlisting}

Počet iterácií cyklu {\tt while} v tomto algoritme je $\mathcal{O}(\log n)$. Po skončení vieme, že prvý výskyt môže byť na pozícii $i+1$. Ak teda chceme vedieť, či vzorka má nejaký výskyt, stačí porovnať $P$ a $T[SA[i+1]..n]$. Celkový čas na vyhľadanie vzorky je počet iterácií krát $\mathcal{O}(m)$, lebo porovnanie reťazcov je v $\mathcal{O}(m)$. 

Ak chceme poznať všetky výskyty alebo ich počet, môžeme spustiť binárne vyhľadávanie dvakrát: raz pre $X=P\$$ a raz pre $X=P\#$, kde $\#$ je špeciálny znak, v lexikografickom poradí za všetkými ostatnými znakmi abecedy. Ak prvé vyhľadávanie vrátilo index $i$ a druhé index $j$, výskyty vzorky budú na pozíciách $SA[i+1],\dots SA[j]$. Všetky výskyty teda nájdeme v čase $\mathcal{O}(m\log n + k)$, 
kde $k$ je ich počet. 


\paragraph{Algoritmus 2.}
Tento algoritmus vynecháva niektoré zbytočné porovnania.
Nech $lcp(A,B)$ je dĺžka najdlhšieho spoločného prefixu reťazcov $A$ a $B$ 
(\emph{longest common
prefix}) (obr. \ref{l12_lcp0}). 

Budeme udržovať invariant:
$$ XL = lcp(T[SA[L]..n], X)$$
$$ XR = lcp(T[SA[R]..n], X)$$

\begin{lstlisting}
L = 0; R = n;
XL = lcp(X, T[SA[L]..n]); XR = lcp(X, T[SA[R]..n]);
while(R - L > 1){
  k = (L + R + 1) / 2;
  h = min(XL, XR);
  while(T[SA[k]+h]==X[h]) { h++; }
  if(T[SA[k]+h]<X[h]){ L = k; XL = h; }
  else {  R = k; XR = h; }
}
// skoncime s intervalom dlzky 1 alebo 2
if (T[SA[R]..n] < X) {return R;}
else {return L;}
\end{lstlisting}
%pic 2
\begin{figure}[h]
    \centering\includegraphics[width=4cm]{figures/l11-sa1.eps}
    \caption{Ilustrácia druhého algoritmu pre hľadanie vzorky v sufixovom poli, podprípad $XL>XR$.}
    \label{l12_lcp0}
\end{figure}

Tento algoritmus ale stále funguje v $\Theta(m \log n)$.

\paragraph{Algoritmus 3.}

%prepisane 2 odstavce
Tento algoritmus už má lepšiu zložitosť ako predchádzajúce dva. Podobá
sa na algoritmus 2, ale v každej iterácii nechceme začať porovnávanie
od pozície, ktorá je minimom $XL$ a $XR$, ale od pozície, ktorá je ich
maximom. Označme si ako $LCP(i,j)$ hodnotu $lcp(T[SA[i]..n],T[SA[j]..n])$. 
Predpokladajme, že vybrané hodnoty $LCP(i,j)$ poznáme (nezávisia od
vzorky, len od $T$).

Predpokladajme, že v aktuálnej iterácii $XL
\ge XR$. Prípad, že $XL < XR$ sa rieši symetricky podobným spôsobom.
Môžu nastať nasledujúce tri prípady (pozr obr. \ref{l12_cases}:

\begin{figure}[h]
\begin{minipage}[b]{0.3\textwidth}
\includegraphics[width=0.99\textwidth]{figures/l11-sa2.eps}\\
\centerline{Prípad $LCP(L,k) > XL$.}
\end{minipage}
\hfill
\begin{minipage}[b]{0.3\textwidth}
\includegraphics[width=0.99\textwidth]{figures/l11-sa3.eps}\\
\centerline{Prípad $LCP(L,k) < XL$.}
\end{minipage}
\hfill
\begin{minipage}[b]{0.36\textwidth}
\includegraphics[width=0.99\textwidth]{figures/l11-sa4.eps}\\
\centerline{Prípad $LCP(L,k) = XL$.}
\end{minipage}

\caption{Tri prípady v treťom algoritme pre vyhľadávanie v sufixovom poli}
\label{l12_cases}
\end{figure}

\begin{enumerate}
\item ak $LCP(L,k) > XL$, z tejto nerovnosti vieme, že
  $T[SA[k]..n] < X$ a teda
  $L=k$, $XL$ zostáva také isté.
  
\item ak $LCP(L,k) < XL$, priamo z nerovnosti vieme, že
  $T[SA[k]..n] >X$, a teda $R=k$, $XR=LCP(L,k)$.
  
\item ak $LCP(L,k) = XL$, potom 
  porovnávame $X$ a $T[SA[k]..n]$ od $XL+1$.
\end{enumerate}

\paragraph{Časová zložitosť} Máme $O(\log n)$ iterácií, v každej $O(1)$ +
porovnávanie znakov. $\max(XL,XR)$ neklesá. Nerovnosti znakov -- $O(\log n)$.
Rovnosť znakov posunie $\max(XL, XR)$ o $1$. $\max(XL,XR) \leq m$, teda dokopy
urobíme $m$ porovnaní. Celková zložitosť je $O(m+\log n)$.


Keď robíme binárne vyhľadávanie, nepotrebujeme všetky $lcp$ hodnoty. Konkrétne, 
v algoritme sme potrebovali $LCP(L,k)$ alebo $LCP(R,k)$, pričom $k$ sa stalo novým $L$ alebo $R$. Pozrime sa na rozhodovací strom na obrázku \ref{l12_bintree} -- keďže sa pýtame len na intervaly z tohto stromu, a vieme, že strom má dokopy najviac $2n-1$ vrcholov, stačí nám spočítať a uložiť $2n-1$ hodnôt. Najprv spočítame hodnoty $LCP$ pre listy (hodnoty $LCP(i,i+1)$). 

\begin{figure}[h]
    \centering\includegraphics{figures/l12.6}
    \caption{Rozhodovací strom potrebných $lcp$ hodnôt pri vyhľadávaní}
    \label{l12_bintree}
\end{figure}

Ak vieme spočítať $LCP(i,i+1)$, tak ostatné hodnoty $LCP$ dopočítame ľahko, pretože pre $LCP(i,j)$ kde $j>i+1$ a pre každé $k\in \{i+1,\dots,j-1\}$ platí
$$
LCP(i,j) = \min \{LCP(i,k),LCP(k,j)\}.
$$

Prečo? Môžeme to vidieť na obrázku \ref{obr:LCP}. (Keby sa reťazce na pozíciách $i$ a $j$ zhodovali na viacerých znakoch ako reťazce na pozíciách $i$ a $k$, tak potom by reťazce nemohli byť zoradené podľa abecedy, čo v sufixových poliach sú.) Z toho vyplýva, že ak vieme hodnoty pre listy, tak vieme lineárnym prechodom stromu spočítať pre všetky vrcholy. Takže potrebujeme už len spočítať $LCP$ pre listy, čo sa dá v čase $O(n)$, ako ukážeme v časti \ref{sec:lcp}.

\begin{figure}[h]
  \centerline{\includegraphics{figures/l13-lcp.1}}
  \caption{Odôvodnenie formuly na zrátanie $LCP(i,j)$}\label{obr:LCP}
\end{figure}

\paragraph{Zhrnutie}

V tabuľke \ref{tab:1} vidíme prehľad dátových štruktúr preberaných na prednáškach minulý týždeň. Vidíme, že sufixové pole je lepšie preto, lebo potrebujeme menej pamäte. S~použitím $LCP$ máme ešte nejaké urýchlenie -- ak si predpočítame $LCP$ pre niektoré dvojice, dosiahneme vyhľadávanie $\mathcal{O}(m+\log n)$ pri zachovaní pamäťovej náročnosti.

\begin{table}[h]
\begin{center}
\begin{tabular}{l|c|c|c}
& konštrukcia & vyhľadávanie vzorky & pamäť (počet smerníkov)\\
\hline
sufixový strom & $\mathcal{O}(n \log \sigma)$ & $\mathcal{O}(m \log \sigma)$ & cca $7n$ \\
\hline
sufixové pole & $\mathcal{O}(n)$ & $\mathcal{O}(m \log n)$ & $n$ \\
\hline
sufixové pole + $LCP$ & $\mathcal{O}(n)$ & $\mathcal{O}(m + \log n)$ & $3n$ \\
\end{tabular}
\end{center}

\caption{Porovnanie sufixových stromov, sufixových polí a sufixových polí s $LCP$.}\label{tab:1}
\end{table}

\subsection{TO DO}
Trochu učesať.





