\section{Ukkonenov algoritmus na konštrukciu sufixových stromov}

Algoritmov na konštruovanie sufixových stromov je niekoľko, napríklad:

\begin{itemize}

\item Weiner 1973 (ktorý Knuth nazval ,,algoritmom roku '73'')
\item McCreigh 1976
\item Ukkonen 1995

\end{itemize}

Bližšie si popíšeme Ukkonenov algoritmus. Najprv budeme vytvárať implicitný sufixový strom, bez koncového $ \$ $ (v takomto strome niektoré sufixy môžu končiť uprostred hrany). Nech $\tau_i$ je implicitný sufixový strom pre $S[1..i]$ (prvých $i$ písmen reťazca $S$). Budeme postupne vytvárať $\tau_i$ pre dlhšie a dlhšie prefixy a používame implicitný strom namiesto sufixového stromu, lebo by nebolo efektívne po každom kroku (tj. zväčšení $i$) pridávať a uberať $ \$ $. 


Samotný algoritmus vyzerá nasledovne (pozn.: $ \texttt{T(i)} = \tau_i$):

\begin{verbatim}
zostav T(1)
for i = 2 to |S| + 1
  // nazveme to "fáza i" - prerob T(i-1) na T(i)
  for j = 1 to i
    // nazveme to "predĺženie j" - pridaj S[j..i] do stromu
    nájdi koniec cesty zodpovedajúcej S[j..i-1]; 
    pridaj k tejto ceste S[i] (*)
\end{verbatim}

V kroku (*) môžu nastať 4 prípady:
\begin{itemize}
\item prípad \textbf{1} - cesta končí v liste, do ktorého ide hrana označená $\alpha$ $\Rightarrow$ pridaj $S[i]$ k hrane do listu, tj dostanem hranu $\alpha S[i]$
\item prípad \textbf{2a} - skončíme vo vnútornom vrchole a nedá sa pokračovať $S[i]$ $\Rightarrow$ pridáme dieťa k vrcholu s hranou $S[i]$ a index listu bude $j$
\item prípad \textbf{2b} - skončíme uprostred hrany a nedá sa ďalej pokračovať $S[i]$ $\Rightarrow$ máme teda hranu $\alpha \beta$ a za $\alpha$ nemôžeme pokračovať, tak rozsekneme hranu na dve časti, kde prvá časť ostane hrana $\alpha$ za ktorou nasleduje vrchol s dvoma deťmi - jeden s hranou $\beta$ a druhé dieťa s indexom $j$, kde hrana je označená $S[i]$
\item prípad \textbf{3} - cesta pre $S[i..j]$ už je v strome $\Rightarrow$ netreba robiť nič

\end{itemize}

Takáto triviálna implementácia algoritmu má časovú zložitosť $O(n^3)$, čo nie je príliš dobré. Zlepšíme to trikmi medzi ktoré patrí odbúravanie pochodovania po cestách a (rozumným) preskočením väčšiny prípadov 1 až 3.

\subsection{Trik 1 - sufixové linky}

Ak $v$ je vrchol pre reťazec $x \alpha$ ($x \in \Sigma$, $\alpha$ je reťazec), sufixová linka $S(v)$ je vrchol pre reťazec $\alpha$. Udržujeme si $S(v)$ pre všetky vnútorné vrcholy.

\paragraph{Vytvorenie linky pre novo-vzniknutý vnútorný vrchol:} Nové vnútorné vrcholy vznikajú iba v prípade 2b. Nech $S[j..i] = x \alpha y$ $(x, y \in \Sigma)$. Pridali sme vrchol pre reťazec $x \alpha$. $\alpha$ je už v strome. Vrchol pre $x \alpha$ má aspoň dve deti začínajúce na $y, z$. Vo fáze $i - 1$ strom obsahoval $x \alpha z$ a teda aj $\alpha z$ (keďže obsahuje každý sufix). Po rozšírení $j+1$ fázy $i$ určite bude existovať vnútorný vrchol pre $\alpha$. V tom kroku tiež navštívime vrchol pre $\alpha$ a dorobíme linku z $x \alpha$.

Otázka znie, ako nám takéto sufixové linky pomôžu? V rozšírení $j$ sme našli pozíciu $S[j..i]$. V ďalšom kroku hľadáme $S[j+1..i]$. Nájdeme najbližšieho predka $S[j..i]$, ktorý má $S(v)$ (nech to je $S[j..k]$) a cez jeho sufixovú linku sa dostaneme do $S[j+1..k]$ a zídeme dole do $S[j+1..i]$). Sufixová linka je najneskôr v praotcovi (príp. v koreni, pre ktorý sufixová linka nie je definovaná, ale to nám nevadí), pretože v strome je najviac jeden vnútorný vrchol (okrem koreňa), ktorý ešte nemá sufixovú linku a môže to byť práve otec novovytvoreného listu.

\paragraph{Lema:} Ak hĺbka vrchola $v$ je $h$, tak hĺbka $S(v)$ je aspoň $h - 1$.

\begin{figure}[h]
	\center\includegraphics[height=100mm]{figures/l08-1}
	\caption{Strom so sufixovými linkami. Prerušované čiary značia sufixové linky a bodkovaná predstavuje obe možnosti sufixovej linky.}
\end{figure}

Pozn.: V leme je $h - 1$, pretože syn koreňa nemusí mať vždy sufixovú linku na ,,vedľajší'' vrchol, ale aj do koreňa.

Začneme v hĺbke 0. Dokopy vo fáze $i$ stúpame najviac o $3n$ (najviac dve stúpania do praotca a jedno cez linku (z lemy)). Na konci fázy skončíme v hĺbke $1$. Hĺbku teda zvýšime najviac $3n + 1$-krát. Spolu teda prejdeme po $O(n)$ hranách resp. linkách.

\subsection{Trik 2 - zrátaj a preskoč}

Sme v stave, že sme dokončili spracovanie $x \alpha y$ a chceme spracovať $\alpha y$ a na to potrebujeme nájsť $\alpha$. Vieme, že $\alpha$ je už niekde v strome. Trik je, že na každej hrane nám stačí skontrolovať len prvý znak a zvyšok už musí sedieť, pretože z každého vrchola musia hrany začínať iným znakom. Na každej hrane sa teda zdržím $O(1)$. Spolu teda jedna fáza trvá $O(n)$ a celý algoritmus tým pádom $O(n^2)$. Stále to však nie je to, čo chceme.

\subsection{Trik 3 - tri a dosť}

Tretí trik znamená uvedomiť si, že ak sme v rozšírený fázy $i$ a použijeme pravidlo \textbf{3}, tak vo zvyšku fázy $i$ už budeme používať už len pravidlo \textbf{3}. Inými slovami, ak $S[j..i]$ už je v strome, tak aj $S[k..i]$ (pre $k > j$, teda všetky ďaľšie sufixy) sú tiež v strome. Takže keď v algoritme použijeme pravidlo \textbf{3}, tak skončíme fázu.

\subsection{Trik 4 - list zostane listom}

Ak pre $S[j..i]$ vyrobíme list (to môžeme pravidlom \textbf{1}, \textbf{2a} alebo \textbf{2b}), tak pre $S[j..i+1]$ použijeme pravidlo \textbf{1} na tento list. Nech $j_i$ je prvýkrát, keď vo fáze $i$ použijeme pravidlo \textbf{3}.

\begin{figure}[h]
	\center\includegraphics[width=12cm]{figures/l08-2}
	\caption{Pravidlá používané počas fáz $i$ a $i + 1$ s využitím trikov 3 a 4}
\end{figure}

V hranách do listov použijeme špeciálny index na koniec reťazca (napríklad nekonečno) reprezentujúci aktuálne $i$. Následne, vo fáze $i + 1$ môžeme preskočiť prvých $j_i - 1$ rozšírení (obrázok 3). Preskočím len prvých $j_i - 1$, pretože $j_i$ už je pravidlo \textbf{3}.

Po aplikovaní všetkých trikov vyzerá fáza $i$ nasledovne:

\begin{verbatim} 

j = j_(i-1);
while (j <= i) {
  sprav rozšírenie j (podľa pôvodných pravidiel);
  ak sa použilo pravidlo 3 {
    j_i = j;
    break;
  }
}
\end{verbatim}

Počet rozšírení je najviac $2n$ v celom algoritme. Čas na jedno rozšírenie je $O(1)$ + pochodovanie dole po hranách. Toto zlepšíme tak, že si vo fáze $i$ zapamätáme posledný vrchol a tento bude prvý vo fáze $i + 1$, takže v prvom kroku netreba pochodovať.

Koľko je teda možných pochodovaní? Spravíme najviac $2n$ rozšírení, pričom v každom stúpneme najviac o 3. Začíname v hĺbke 0 a po skončení sme najviac v $n + 1$. Spolu teda najviac $7n + 1$-krát klesneme ($2n * 3 + n + 1$) a teda $O(n)$.


