\section{Lexikografické stromy}

\begin{figure}[h]
	\center\includegraphics[height=100mm]{figures/l07-1}
	\caption{Trie pre $\{ema, ma, mamu, mama, emu\}$}
\end{figure}

Na jednej z predchádzajúcich prednášok sme si už spomínali dátovú štruktúru trie. Trie je strom, ktorého každá hrana je označená znakom z abecedy $\Sigma$, pričom hrany z jedného vrchola sú označené rôznymi znakmi. Slovo zodpovedajúce vrcholu dostaneme konkatenáciou znakov na ceste z koreňa. Vrcholy zodpovedajú prefixom slov zo vstupnej množiny ${S_1, S_2, ...}$. Ak vrchol zodpovedá $S_i$ označíme ho indexom $i$ (tak ako na obrázku č. 1).

\subsection{Úlohy}

\paragraph{Je $Q$ v $\{S_1, ..., S_z\}$?}

Predpokladáme, že máme trie. Postupne prechádzame po hranách a môže nastať:

\begin{itemize}
\item Minieme $Q$ a skončíme v akceptačnom vrchole $\Rightarrow$ vrátime "áno".
\item Minieme $Q$ a skončíme v neakceptačnom vrchole $\Rightarrow$ vrátime "nie".
\item Neminieme $Q$ a nemáme sa kam posunúť $\Rightarrow$ vrátime "nie".
\end{itemize}

Zložitosť je zjavne $O(m)$, kde $m = |Q|$.

\paragraph{Pridanie nového $Q$}

\begin{itemize}
\item Minieme $Q$ a skončíme v akceptačnom vrchole $\Rightarrow$ nerobíme nič, keďže dané slovo už v trie je.
\item Minieme $Q$ a skončíme v neakceptačnom vrchole $\Rightarrow$ označíme vrchol ako akceptačný.
\item Neminieme $Q$ a nemáme sa kam posunúť $\Rightarrow$ pridáme hrany pre zvyšok slova.
\end{itemize}

Zložitosť je znova $O(m)$.

\paragraph{Zmazanie $Q$ z existujúceho trie}

Nájdeme vrchol zodpovedajúci $Q$:

\begin{itemize}
\item Ak je list, tak mažeme cestu ku koreňu až kým nedojdeme po vrchol, ktorý je akceptačný (okrem seba samého) alebo rozvetvenie.
\item Ak nie je list tak odznačíme, že je akceptačný.
\end{itemize}

Zložitosť je taktiež $O(m)$.

Vieme teda spraviť operácie search, insert a delete. Takže sa na trie môžeme pozerať ako na slovníkovú štruktúru. Keby sme mali napr. vyvážený vyhľadávací strom, tak by povedzme insert trval $O(m\log(z))$, zatiaľ čo v trie to je $O(m)$ (pokiaľ predpokladáme malú resp. konštantne veľkú abecedu).

Aby sme trochu zjednodušili algoritmy pracujúce s trie, pridáme za každé slovo v množine špeciálny symbol \$, ktorý sa nenachádza v $\Sigma$. Budujeme teda trie pre reťazce ${S_1\$, ..., S_z\$}$, ako je naznačené na obrázku \ref{fig:triedollar}. Po takejto úprave každému slovu z množiny zodpovedá jeden list v strome.

\begin{figure}[th]
	\center\includegraphics[height=100mm]{figures/l07-2}
	\caption{Trie pre $\{ema\$, ma\$, mamu\$, mama\$, emu\$\}$. }
\label{fig:triedollar}
\end{figure}


\subsection{Príklady použitia lexikografického stromu}

Trie môžeme použiť na riešenie rôznych úloh s množinami slov, ako napríklad:

\begin{itemize}

\item Spellchecking: zostavíme trie pre slová v slovníku, hľadáme slová v kontrolovanom texte.
\item Rátanie frekvencií výskytu jednotlivých slov v texte - ku každému listu pridáme počítadlo; zložitosť je $O(n)$.
\item Hľadáme najdlhšie slovo, ktoré je prefixom aspoň dvoch reťazcov z ${S_1, ..., S_z}$. Nájdeme najhlbší vrchol, ktorý má pod sebou aspoň dva listy.

\item Pokiaľ by sme chceli hľadať najdlhšie slovo, ktoré je podslovom
  aspoň dvoch reťazcov z ${S_1, ..., S_z}$ tak na to sa trie príliš
  nehodí, pretože vrcholy zodpovedajú prefixom. Skúsime to vyriešiť
  rozšírením trie a to tak, že vybudujeme trie všetkých sufixov. Tým
  pádom vrcholy budú zodpovedať prefixom sufixov slov z ${S_1, ...,
    S_z}$ a to sú práve podslová. A na takto skonštruovanom trie
  hľadáme najhlbší vrchol, ktorý má pod sebou aspoň dva listy, ktoré
  sú z dvoch rôznych slov (tj. nie sufixy toho istého slova).  Problém
  ale je, že veľkosť takejto trie a tým pádom aj zložitosť jej
  konštrukcie je $O(\sum_{i=1}^z |S_i|^2)$, pretože súčet dĺžok
  sufixov slova dĺžky $m$ je $\Theta(m^2)$. Aby sme sa vyhli takejto
  kvadratickej zložitosti, budeme namiesto lexikografických stromov používať
  sufixové stromy.

\end{itemize}

\section{Sufixové stromy}

\begin{figure}[h]
	\center\includegraphics[height=100mm]{figures/l07-3}
	\caption{Lexikografický strom so všetkými sufixami $ aabab\$ $}
\label{fig:triesuf}
\end{figure}

%prepisany odstavec
Sufixový strom dostaneme z lexikografického stromu tak, že nahradíme
každú postupnosť $k$ vrcholov bez vetvenia jednou hranou, ktorú
označíme príslušným reťazcom dĺžky $k$. Napr. pre $S = aabab$
dostávame lexikografický strom sufixov ako na obrázku \ref{fig:triesuf}
a sufixový strom ako na obrázku \ref{fig:triesuf2} hore.
Aby sme však naozaj ušetrili pamäť, nebudeme si 
pamätať samotné reťazce dĺžky $k$, ale len súradnice 
tohto reťazca v slove $S$ (obr. \ref{fig:triesuf2}, strom dole). 

Teda v sufixovom strome sú hrany označené reťazcami. Reťazce pre hrany z jedného vrchola začínajú rôznymi písmenami. Každý list zodpovedá jednému sufixu $ S\$ $ a naopak. Každému vrcholu zodpovedá podslovo $ S\$ $, ale nie nutne naopak (kvôli skompaktneniu).

\begin{figure}[h]
	\center\includegraphics[height=100mm]{figures/l07-4}
	\caption{Skompaktnený sufixový strom pre $ aabab\$ $ a pod ním daný strom so súradnicami namiesto reťazcov na hranách.}
\label{fig:triesuf2}
\end{figure}

Koľko má vrcholov sufixový strom? Nech $|S| = m$. Potom sufixový strom má $m + 1$ listov, jeden pre každý sufix. Potom $m$ vnútorných vrcholov  je najviac $m$, lebo každý má aspoň dve deti. Spolu máme teda $O(m)$ vrcholov. V každom vrchole si pamätáme smerníky do detí (prípadne na rodiča), teda $O(1)$ smerníkov (keď predpokladáme konštantnú abecedu), 2 indexy do $S$ a v listoch ešte číslo sufixu (listy číslujeme od najdlhšieho sufixu ktorý reprezentujú, napr. pre strom na obr. 4 je list pri hrane $ abab\$ $ označený 1, list do ktorého ide hrana $ \$ $ z koreňa označený 6, atď.). Spolu teda $O(\log(m))$ bitov v každom vrchole respektíve $O(1)$ registrov. Pre celý strom to tvorí $O(m\log(m))$ bitov či $O(m)$ registrov. Čas na zostrojenie sufixového stromu je pri triviálnej implementácií až $O(m^2)$ ale pri použití pár ,,trikov'' sa dostaneme k $O(m)$, pričom takýto algoritmus je opísaný v poznámkach nasledujúcej prednášky.

\subsection{Zovšeobecnené sufixové stromy pre reťazce $S_1, S_2, ..., S_z$}

Zovšeobecnený sufixový strom vytvoríme tak, že všetky reťazce ukončíme znakom $ \$ $, teda dostanem $S_1\$, S_2\$, ..., S_z\$ $ (obr. 5). Potrebujeme si pamätať v každej hrane okrem indexov podslova aj z ktorého reťazca daný sufix je a v každom liste aj zoznam príslušných reťazcov (keďže môže byť daný sufix pre viac reťazcov). 


\begin{figure}[h]
	\center\includegraphics[height=100mm]{figures/l07-5}
	\caption{Zovšeobecnený sufixový strom pre $ aaba\$, bba\$ $ a pod ním skompaktnený zovšeobecnený sufixový strom s indexami pre tie isté vstupy}
\end{figure}

\subsection{Príklady použitia sufixových stromov}

Znovu ich je viacero, napríklad online vyhľadávanie vzoriek v statickom texte. Máme text $T$ a postupne prichádzajú vzorky $P_1, P_2, \dots$. Úlohou je nájsť pre každú vzorku výskyty. Doteraz sme to vedeli len cez KMP algoritmus v $(|P_i| + |T|)$ pre každú vzorku $P_i$. Pomocou sufixových stromov to zvládneme v $O(|P_i|+k)$, kde $k$ je počet výskytov (po $O(|T|)$ predspracovaní na vybudovanie stromu). Pre vzorku $P_i$ sledujeme cestu z koreňa, až kým:

\begin{itemize}

\item neminieme $P_i$ a nedá sa pokračovať (môže sa stať aj uprostred hrany) $\Rightarrow$ nemá výskyt
\item minieme $P_i$ a skončíme vo vrchole $v$. Potom potrebujeme vypísať indexy sufixov všetkých listov v podstrome $v$. Zložitosť prezretia podstromu je $O(k)$, kde $k$ je počet výskytov.
\item minieme vzorku a skončíme uprostred hrany. Postupuje rovnako ako v predchádzajúcom prípade pre spodný vrchol hrany na ktorej sme skončili.

\end{itemize}

Iný príklad použitia je najdlhšie podslovo, ktoré sa v $T$ vyskytuje aspoň dvakrát. Tento zodpovedá nejakému vrcholu (prečo?). Zaujíma nás reťazcová dĺžka vrchola, čo je dĺžka zodpovedajúceho reťazca pre daný vrchol. Hľadáme vnútorný vrchol s maximálnou reťazcovou hĺbkou.

%nový odstavec
Vráťme sa k nášmu motivačnému príkladu, t.j. nájsť najdlhšie slovo,
ktoré je podslovom aspoň dvoch reťazcov z ${S_1, ..., S_z}$. Zostrojíme si 
zovšeobecnený sufixový strom pre tieto reťazce a hľadáme najhlbší vrchol,
ktorý má pod sebou listy zodpovedajúce sufixom aspoň dvoch rôznych $S_i$. 

%nový odstavec
Ako ho nájdeme? Prehľadávame strom od listov a pre každý vrchol si
pamätáme, či má pod sebou sufixy jedného slova alebo viacerých. Ak iba
jedného, pamätáme si aj ktorého, aby sme v rodičovi vedeli tiež rýchlo
vyhodnotiť túto podmienku. Celkovo vieme príklad riešiť v lineárnom
čase pre konštantnú abecedu.

\subsection{Hľadanie maximálnych opakovaní}

%nový odstavec
Už sme videli ako nájsť najdlhšie podslovo s výskytom v dvoch rôznych
textoch. Niečo podobné by sa nám hodilo pri detekcii plagiátorstva,
avšak potrebovali by sme hľadať skôr približné než presné zhody.  Ako
uvidíme neskôr, hľadanie približných zhôd je výpočtovo náročnejšie,
preto pre zrýchlenie môžeme chcieť nájsť aspoň viacero fragmetov
presných zhôd. Nasledujúci problém takýto cieľ presnejšie formalizuje.

Maximálny pár v $S$ je dvojica podslov $S[i..i+k]$ a $S[j..j+k]$ taká, že $S[i..i+k] = S[j..j+k]$ a $S[i-1] \neq S[j-1]$ a $S[i+k+1] \neq S[j+k+i]$. Inými slovami, pred a za rovnakými podslovami sú rozdielne znaky a teda sa rovnaká časť už nedá predĺžiť. Pre jednoduchosť si $S$ predstavíme (resp. upravíme) na  $ \#S\$ $, aby sa nám nestalo ze vypadneme z reťazca.

\paragraph{Príklad} Nech $S = xabxabyabz$. Maximálny pár je $xab$ na pozíciách 1 a 4, $ab$ na pozíciách 2 a 8 a taktiež $ab$ na pozíciách 5 a 8.

Maximálne opakovanie je reťazec, ktorý je časťou maximálneho páru. Pre predchádzajúcu ukážku to je $ab$ a $xab$.


Chceme teraz pre reťazec S nájsť všetky maximálne opakovania. Zostavime sufixový strom pre S. Každé max. opakovanie zodpovedá nejakému vnútornému vrcholu. Tým pádom je najviac $n$ max. opakovaní. Nech $v$ je list, ktorý zodpovedá sufixu $S[i..n]$. Zavedieme si, že ľavý znak listu $v$ bude $l(v) = S[i-1]$. Ďalej povieme, že vrchol stromu $u$ je rôznorodý, ak v jeho podstrome sú aspoň dva rôzne $l(v)$. Potom tvrdíme, že vnútorný vrchol zodpovedá maximálnemu opakovaniu práve vtedy, keď je rôznorodý. Jedna implikácia je zjavná, pretože ak vnútorný vrchol zodpovedá max. opakovaniu, tak z definície sa vo vstupnom slove vyskytuje daný reťazec aspoň dvakrát a znaky naľavo od výskytu sa odlišujú. Opačnú implikáciu si ukážeme:

Majme reťazec $\alpha$ zodpovedajúci rôznorodému vnútornému vrcholu. Potom existujú dva znaky $x$ a $y$ také, že $x \alpha$, $y \alpha$ sú podslová $S$. Čo nasleduje za $\alpha$ v týchto výskytoch? Máme dve možnosti:

\begin{itemize}

\item rôzne $x \alpha p$ a $y \alpha r$ - a teda je to maximálny pár
\item rovnaké $x \alpha p$ a $y \alpha p$. Z vrcholu $\alpha$ však ide aj ďalšia hrana začínajúca na nejaké $q \neq p$. Čo ide pred $\alpha q$? Znova máme dve možnosti:

\begin{itemize}

\item vždy $x$ ($x \alpha q$) a teda mám $x \alpha q$ a $y \alpha p$
\item alebo $z \neq x$ ($z \alpha q$) a z toho dostávam $z \alpha q$ a $x \alpha p$

\end{itemize}

\end{itemize}

Ako hľadať rôznorodé vrcholy? Prehľadávame strom od listov v
post-orderi. V každom vrchole si pamätáme buď jediné $l(v)$ ak nie je
rôznorodý, alebo špeciálnu značku ak je. Toto sa ľahko spočíta
pre daný vrchol prezretím všetkých detí. 

Takže celkovo vieme vypísať všetky maximálne opakovania v $O(n)$
čase. Algoritmus sa dá ďalej rozšíriť na detekciu opakovaní, ktoré nie
sú podreťazcami iných, resp. na výpis maximálnych dvojíc.


\subsection{Zhrnutie}
\begin{itemize}
\item Sufixové stromy sú kompaktná reprezentácia všetkých sufixov reťazca
\item Dajú sa zostrojiť v lineárnom čase, ako uvidíme na budúcej prednáške
\item Potrebujú však pomerne dosť veľa pamäte na každý znak reťazca, čo je problém pre dlhé reťazce
\item Pomocou nich vieme v lineárnom čase odpovedať na mnohé zaujímavé problémy o rovnosti podslov
\end{itemize}



