\subsection{Konštrukcia sufixového poľa}

% prepisany odstavec
\paragraph{Klasickým triedením.} Sufixové pole môžeme zostrojiť použitím klasického triedenia, napr. merge sortu. Ten urobí $\mathcal{O}(n\log n)$ porovnaní sufoxov, každé porovnanie trvá $\mathcal{O}(n)$, dokopy je to $\mathcal{O}(n^2 \log n)$.

% prepisany odstavec
\paragraph{Triedením pomocou radix sortu.}
Trochu lepšie je použiť radix sort. Radix sort vo všeobecnosti triedi $d$ ciferné čísla v $k$-árnej sústave, pričom každú cifru triedi pomocou counting sortu. Counting sort utriedi $n$ čísel z množiny $\{0..k-1\}$ v čase $\mathcal{O}(n+k)$. Radix sort volá counting sort postupne $d$ krát v poradí od najmenej významnej cifry po najvýzmanejšiu. Preto je celkový čas radix sortu $\mathcal{O}(d(n+k))$. V našom prípade predpokladajme, že abeceda je nejaká podmnožina množiny $\{0,..n-1\}$ a teda sufixy sú $n$-ciferné čísla v $n$-árnej sústave. Radix sort ich teda utriedi v čase $\mathcal{O}(n^2)$. Sufixové pole by sme ale chceli zostrojiť v lineárnom čase.

\paragraph{Pomocou sufixového stromu.} Ďalšia možnosť je zostrojiť sufixový strom v lineárnom čase a potom ho prejsť do hĺbky tak, že v každom vrchole neprejdené hrany vyberáme podľa abecedy. Potom to poradie, v ktorom navštívime listy, je poradie, v akom majú byť sufixy v sufixovom poli. Takto vieme zostrojiť sufixové pole v lineárnom čase. Problém je v tom, že sme nechceli používať sufixové stromy kvôli veľkosti pamäte a takto ju aj tak budeme potrebovať. 

%cely algoritmus pomerne prepisany.
\paragraph{Lineárny algoritmus na konštrukciu sufixového poľa.}
Existuje niekoľko lineárnych algoritmov na konštrukciu sufixového
poľa, my si ukážeme jeden od autorov Karkkainen a Sanders (2003).
Pracuje nad abecedou $\{1,\dots, n\}$, kde $n$ je dĺžka reťazca, pričom
pracuje aj pre takúto veľkú abecedu v čase $O(n)$. Iné abecedy môžeme
prečíslovať triedením znakov textu, čo však môže zhoršiť zložitosť. Za
koniec reťazca pridáme niekoľko núl, ktoré budú simulovať špeciálny
znak \$.

Prácu tohto algoritmu si ukážeme na príklade $S_p= fabbcabbd$. V
tabuľke \ref{tab:array1} môžeme vidieť prepísanie tohto slova do
pracovnej abecedy.

\begin{table}[h]
  \begin{center}
\begin{tabular}{|c|cccccccccccc|}
  \hline
  $i$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & & & \\
  \hline
  $S_p[i]$ & f & a & b & b & c & a & b & b & d  & & & \\
  \hline
  $S[i]$ & 5 & 1 & 2 & 2 & 3 & 1 & 2 & 2 & 4 & 0 & \dots & 0 \\
  \hline
\end{tabular}
\end{center}
\caption{Prepísanie vstupu $S_p$ do pracovnej abecedy $\{1\dots n\}$}
\label{tab:array1}
\end{table}

\paragraph{Krok 1:} 
Utriedime sufixy $S[3i+k..n]$ pre $k=1,2$ do poľa $SA_{1,2}$. Triedime
teda dve tretiny zo všetkých sufixov pôvodného reťazca. Dosiahneme to
tak, že vytvoríme nový reťazec $S'$ nad abecedou $\Sigma^3$, t.j.
znakmi budú trojice znakov z pôvodného reťazca, pričom 
$$S' = S[1..3]S[4..6]\dots S[3n'+1..3n'+3]S[2..4]S[5..7]\dots S[3n'+2..3n'+4],$$ kde $n'$ je najmenšie také, aby $S[3n'+3]=0$. V našom príklade je to 
$$S' = [abb][cab][bd0][bbc][abb][d00] = [1,2,2][3,1,2][2,4,0][2,2,3][1,2,2][4,0,0].$$

Sufixy v $S'$ zodpovedajú vybraným sufixom $S$ a sú aj v tom istom
lexikografickom poradí. Stačí nám teda pre $S'$ rekurzívne vytvoriť
sufixové pole $SA'$. Predtým však ešte musíme prečíslovať znaky v
$S'$, aby sme dostali reťazec nad abecedou $\{1,\dots,n\}$. To
spravíme tak, že utriedime trojice znakov, ktoré tvoria znaky $S'$
radix sortom v čase $O(n)$.  Máme nový reťazec $S' = 1,4,3,2,1,5,0$,
pričom $|S'| \approx 2/3|S|$. Teraz môžeme rekurzívne pustiť
algoritmus na $S'$, čím dostaneme sufixové pole $SA'$. V našom príklade
dostaneme $SA'=(6,0,4,3,2,1,5)$.

Keď sme spočítali sufixové pole $SA'$ pre $S'$, prepočítame indexy
tak, aby sa vzťahovali na pôvodný reťazec $S$ a uložíme do poľa
$SA_{1,2}$.  Výsledné pole $SA$ neskôr spravíme z poľa $SA_{1,2}$
povkladaním tých sufixov, ktoré sme neuvažovali. Príklad tejto transformácie
vidíme v tabuľke \ref{tab:array2}.

\begin{table}[h]
  \begin{center}
    \begin{tabular}{|c|ccccccc|}
     \hline
      $S'$ & 1 & 4 & 3 & 2 & 1 & 5 & 0 \\
      \hline
      pozícia v $S'$ & 0 & 1 & 2 & 3 & 4 & 5 & 6\\
      \hline
      pozícia v $S$ & 1 & 4 & 7 & 2 & 5 & 8 &  \\
      \hline\hline
      $SA'$ & 6 & 0 & 4 & 3 & 2 & 1 & 5 \\
      \hline
      $SA_{1,2}$ & -- & 1 & 5 & 2 & 7 & 4 & 8 \\
      \hline
    \end{tabular}
  \end{center}
  \caption{Polia $SA'$ a $SA_{1,2}$ pre príklad z tabuľky \ref{tab:array1}.}
\label{tab:array2}
\end{table}

Vytvoríme tiež v $O(n)$ čase pole $rank$ definované nasledovne:
$$
rank[i] =\left\{
\begin{array}{ll}
    0 & i \geq n \\
    - & i \bmod{3} = 0 \\
    j & SA_{1,2}[j]=i \\
\end{array}
\right.
$$ Ak teda chceme porovnať lexikograficky dva sufixy na pozíciách
$3i+k$ a $3j+k'$ kde $k,k'\in \{1,2\}$, stačí nám porovnať príslušné
hodnoty v poli $rank$ (pozri príklad v tabuľke \ref{tab:array3}).

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|*{10}{l}|}
\hline
Poz& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
$S$   & f & a & b & b & c & a & b & b & d &\\
\hline
~   & 5 & 1 & 2 & 2 & 3 & 1 & 2 & 2 & 4 & 0\\
\hline
rank & --& 1 & 3 & --& 5 & 2 & --& 4 & 6 & 0\\
\hline
\end{tabular}
\end{center}
\caption{Pole rank pre príklad z tabuľky \ref{tab:array1}.}
\label{tab:array3}
\end{table}


\paragraph{Krok 2:} Utriedime sufixy tvaru $S[3i..n]$ do 
$SA_0$. Sufix $S[3i..n]$
reprezentujeme ako $(S[3i],rank[3i+1])$. 
V našom príklade dostávame 
$S[0..n]$ ako $(f,1)$, $S[3..n]$ ako $(b,5)$ a $S[6..n]$ ako $(b,4)$.
Ak chceme porovnávať dva sufixy
na pozíciách $3i$ a $3j$, stačí porovnávať ich reprezentáciu pomocou dvojíc, 
lebo 
$$S[3i..n]<S[3j..n] \iff 
S[3i]<S[3j] \vee (S[3i]=S[3j] \wedge rank[3i+1]<rank[3j+1]).$$
Takto vzniknuté dvojice teda vieme utriediť lexikograficky radix sortom  
v čase $O(n)$. V našom príklade dostávame $SA_0=(6,3,0)$. 

\paragraph{Krok 3:} Zlúčime triedené zoznamy sufixov 
$SA_0$ a $SA_{1,2}$ do výsledného sufixového poľa $SA$. 
Postupujeme podobne ako pri zlučovaní zoznamov v MergeSorte, chceme však 
každú dvojicu sufixov (jeden z $SA_0$ a jeden z $SA_{1,2}$) porovnať v
konštantnom čase. Majme teda sufix $S[i..n]$ z
poľa $SA_{1,2}$ s sufix $S[j..n]$ z $SA_0$. 
\begin{eqnarray*}
\mbox{\quad ak $i \bmod{3} = 1$:}\\
S[i..n] \leq S[j..n] &\iff& (S[i], rank[i+1]) \le (S[j],rank[j+1])\\
\mbox{\quad ak $i \bmod{3} = 2$:}\\
S[i..n] \leq S[j..n]&\iff&(S[i], S[i+1], rank[i+2]) \le (S[k],S[j+1],rank[j+2])
\end{eqnarray*}

Príklad niekoľkých porovnaní:
\begin{eqnarray*}
S[3..n] \le S[7..n] \iff (b,5) \le (b,6)\\
S[3..n] \le S[4..n] \iff (b,5) \le (c,2)\\
S[3..n] \le S[2..n] \iff (b,c,2) \le (b,b,5)\\
S[6..n] \le S[2..n] \iff (b,b,6) \le (b,b,5)\\
\end{eqnarray*}

\paragraph{Zložitosť}
\begin{itemize}
\item Krok 1: radixSort $O(n)$, rekurzia na $S'$, $T(\frac{2}{3}n)$,
vytvorenie $SA_{1,2}$, $rank$ $O(n)$.
\item Krok 2: radixSort v $O(n)$ 
\item Krok 3: zlučovanie v $O(n)$
\end{itemize}
Celkový čas je teda $T(n) = T(\frac{2}{3}n) + O(n)$ (úplne správne by
sme mali uvažovať aj drobný aditívny člen pri $\frac{2}{3}n$, to však
pre jednoduchosť zanedbáme). Rekurencie tvaru $T(n) = aT(\frac{n}{b})+f(n)$
vieme riešiť použitím Master theorem, pričom nás zaujíma prípad 
$f(n)=\Omega(n^{\log_b(a)+\varepsilon})$, ktorý sa dá použiť iba ak navyše platí 
$a\cdot f(\frac{n}{b}) \leq c\cdot f(n)$ pre nejaké $c<1$.
Potom dostávame $T(n)=\Theta(f(n))$.

V našom prípade máme $a=1$, $b=\frac{3}{2}$, $\log_{\frac{3}{2}}(1) =
0$. Ľahko overíme aj dodatočnú podmienku, lebo $a\cdot f(\frac{n}{b})
= \frac{2}{3} n$. Dostávame teda, že čas nášho algoritmu je lineárny: 
$T(n) = \Theta(n)$.

Namiesto Master theorem môžeme spočítať čas strávený na každej úrovni
rekurzie. Na vrchnej úrovni potrebujeme čas $c\cdot n$, a na každej 
ďalšej úrovni sa nám veľkosť vstupu zmenší na dve tretiny, na 
$i$-tej úrovni teda potrebujeme čas 
$c\cdot \left(\frac{2}{3}\right)^in$. Sčítaním tejto geometrickej
postupnosti dostávame
$$T(n) \leq \sum_{i=0}^{\infty} c\cdot n\left(\frac{2}{3}\right)^i = c\cdot n
\sum_{i=0}^{\infty}\left(\frac{2}{3}\right)^i = O(n).$$

\subsection{Konštrukcia sufixového stromu zo sufixového poľa}

%cela subsection novy text
Do stromu budeme pridávať sufixy v poradí, v akom sú v sufixovom poli.
V každom vrchole budeme mať uloženú hodnotu $d(u)$ určujúcu sufixovú
hĺbku vrcholu, t.j. dĺžku reťazca, ktorý mu zodpovedá. Predpokladajme,
že už máme v strome sufixy $SA[0], SA[1],\dots SA[i-1]$ a chceme
pridať $T[SA[i]..n-1]$. Nech $k$ je dĺžka najdlhšieho spoločného
prefixu $T[SA[i-1]..n-1]$ a $T[SA[i]..n-1]$. So všetkými ostatnými
sufixami, ktoré už máme v strome, má aktuálny sufix tiež spoločný
prefix dĺžky najviac $k$. Nový sufix bude teda nový list, ktorý sa na
súčasný strom napája vo vrchole reťazcovej hĺbky $k$ ležiacom niekde 
na ceste z listu pre sufix $SA[i-1]$ do koreňa.

Začneme teda v liste pre sufix $SA[i-1]$ a posúvame sa smerom ku
koreňu, kým nenájdeme prvý vrchol $u$ s $d(u)\le k$. Ak $d(u)=k$, nový
sufix prilepíme nový list označený sufixom $SA[i]$.  Ak $d(u)<k$,
rozdelíme hranu z $u$ do jeho dieťaťa novým vrcholom s reťazcovou
hĺbkou $k$ a pripojíme nový list. V ďalšej iterácii pre 
$i+1$ začneme opäť hľadať smerom hore z tohto listu.

Na prvý pohľad je tento algoritmus kvadratický, lebo na pridanie
jedného sufixu môžeme potrebovať výjsť hore až po $n$ hranách. Dá sa
však dokázať, že celkový počet posúvania sa po strome je lineárny,
podobne ako pri konštrukcii kartézskeho stromu. Pri vkladaní sufixu
$SA[i]$ sa totiž posúvame zdola z listu pre sufix $SA[i-1]$. Každý
vrchol, cez ktorý takto prejdeme a zistíme, že jeho reťazcová hĺbka je
príliš veľká, už nikdy nenavštívime pri vkladaniach ďalších sufixov,
lebo budeme začínať z nových listov, ktoré nezdieľajú túto časť cesty. 

Zostáva nám len rýchlo určiť hodnotu najdlhšieho spoločného prefixu
pre každé dva susedné sufixy v sufixovom poli. Toto vieme spočítať
v lineárnom čase pomocou algoritmu, ktorý uvedieme v kapitole 
\ref{sec:lcp}. 

\begin{lstlisting}
create roof and leaf w corresponding to SA[0]
v = w;
for(int i=1; i<=n; i++) {
   while(v.parent.string_depth>L[i-1]) {
     v = v.parent;
   }
   if(v.parent.string_depth<L[i-1]) {
     split edge from v.parent to v with a new vertex 
     at string depth L[i-1]
   }
   attach new leaf w for SA[i] from v.parent;
   v = w;
}
\end{lstlisting}


Ak teda spojíme lineárny algoritmus na konštrukciu sufixového poľa,
lineárny výpočet spoločných prefixov a lineárny prevod so sufixového
poľa na sufixový strom, dostávame $O(n)$ algoritmus na konštrukciu
sufixového stromu, ktorý funguje v čase $O(n)$ aj pre abecedu
$\{1,2,\dots,n\}$. Všimnite si, že deti každého vrcholu budú pridávané
v abecednom poradí a teda ich môžeme pridávať na koniec utriedeného
poľa dynamickej veľkosti. 


\subsection{Výpočet LCP hodnôt pre sufixové pole}

\label{sec:lcp}

%prepisany odstavec
Pripomeňme si, že $lcp(A,B)$ je dĺžka najdlhšieho spoločného prefixu
reťazcov $A$ a $B$ a pre daný reťazec $S$ definujeme 
$LCP(i,j) = lcp(T[SA[i]..n-1],T[SA[j]..n-1])$.
V tejto časti uvedieme algoritmus, ktorý pre každý prvok sufixového
poľa spočíta dĺžku najdlhšieho spoločného prefixu medzi
$T[SA[i]..n-1]$ a $T[SA[i+1]..n-1]$, t.j. $LCP(i,i+1)$. 
Takúto hodnotu uložíme do nového poľa $L[i]$. 
Ako sme videli, tieto hodnoty sú potrebné pre rýchle
vyhľadávanie vzoriek v sufixovom poli aj pre konštrukciu sufixového
stromu zo sufixového poľa. Teraz uvedieme kľúčovú lemu algoritmu.

\begin{figure}[h]
  \centerline{\includegraphics{figures/l13-lcp.2}}
  \caption{Obrázok ilustrujúci lemu \ref{lem:lcp}.}
\label{fig:LCPlema}
\end{figure}

%prepisany odstavec
\begin{lema}\label{lem:lcp}
Majme $x$ a $y$, pre ktoré platí $SA[x+1]+1 = SA[y+1]$. Potom $L[y]\ge L[x]-1$.
\end{lema}

\begin{proof}
 Pozrime sa na pole $SA$ (obrázok \ref{fig:LCPlema}). Chceme
 zistiť hodnotu $LCP(y,y+1)$, pričom $SA[y+1]=i$ a $SA[y]=k$. Nájdeme
 si hodnotu $i-1$ na nejakej pozícii $x+1$ a pozrieme sa na hodnotu
 tesne pred ňou, $j-1$. Nech
 najdlhší spoločný prefix sufixov začínajúcich na pozíciách $i-1$
 a $j-1$ je $c\alpha$. Sufixy začínajúce na pozíciách $i$ aj $j$
 sa teda začínajú slovom $\alpha$. Keďže $S[j-1..n]$ je v lexikografickom 
 poradí pred $S[i-1..n]$, tak aj $S[j..n]$ musí byť pred $S[i..n]$ preto aj
 $S[k..n]$ začína na $\alpha$. Vidíme, že $LCP(y,y+1) \ge
 LCP(x,x+1)-1$. 
\end{proof}

%zmeneny odstavec
Na využitie tejto lemy potrebujeme vedieť rýchlo zistiť, kde v poli
$SA$ je nejaká hodnota $i$. Na to použijeme inverzné pole $rank$, pre
ktoré platí $rank[i]=x \iff SA[x]=i$. Toto pole vieme vypočítať jedným
prechodom poľa $SA$ v čase $O(n)$.

\begin{lstlisting}
for(i=0;i<=n,i++){
  rank[SA[i]] = i;
}
\end{lstlisting}

%novy odstavec
Samotný algoritmus postupuje od najdlhších sufixov po najkratšie a pre
každý sufix spočíta jeho prefix s jeho predchodcom v poli $SA$.

\begin{lstlisting}
h = 0;
for(i=0; i<=n; i++) {
  if(rank[i]>0) {
    k = SA[rank[i]-1];
    // porovnavame sufixy S[i..n-1] a S[k..n-1]
    // vieme vsak, ze maju aspon h znakov spolocnych 
    while (T[i+h]==T[k+h]) { h++; }
    // nasli sme prvu poziciu, kde sa retazce nerovnaju
    L[rank[i]-1] = h;
    if(h>0) { h--; }
  }
}
\end{lstlisting}

Ak v nejakej iterácii pre $i-1$ nájdeme hodnotu $h$, tak pre $i$ bude
hodnota $LCP$ aspoň $h-1$. Najprv sa pozrieme, kde v poli $SA$ je $i$,
ak to nie je na začiatku, pozrieme sa, aký reťazec je pred ním, a
potom ich porovnávame od $h$-tej pozície.  
Nakoniec upravíme $h$ na $h-1$, lebo v nasledujúcej
iterácii máme garantovaných $h-1$ zhôd.

\paragraph{Časová zložitosť.} 
Budeme rátať počet porovnaní vo vnútornom cykle algoritmu. Počet
iterácií, v ktorých porovnanie dopadne nerovnosťou, je najviac $n$,
lebo v každej iterácii máme najviac jednu nerovnosť. Počet rovností už
nie je taký jasný, ale vieme že každá rovnosť zvýši $h$ o jedna. Keďže
$h$ začne na nule a dosahuje hodnotu najviac $n$, v každom kroku sa
zmenší najviac o jeden, preto sa najviac $n$ krát zníži. Takže počet
rovností môže stúpnuť najviac $2n$ krát. Dokopy teda máme najviac $3n$
porovnaní.

\subsection{Burrows-Wheelerova transformácia}

% prepisany odstavec
Burrows-Wheeler transformácia (BWT) je transformácia textu využívaná
pri kompresii (napríklad v programe bzip2), ale ako uvidíme neskôr, aj
v úsporných dátových štruktúrach na hľadanie vzorky v texte.  BWT
transformuje vstupný reťazec $S$ na reťazec $bw(S)$, pričom z reťazca
$bw(S)$ vieme neskôr spätne získať reťazec $S$. Reťazec $bw(S)$ je permutáciou
reťazca $S$, no táto permutácia sa často dá oveľa lepšie 
skomprimovať ako pôvodný reťazec.

\paragraph{Transformácia.}
BWT pozostáva z niekoľkých krokov.
\begin{itemize}
\item na koniec reťazca $S$ pridáme špeciálny symbol $\$$, ktorý sa nevyskytuje v $S$
\item vytvoríme maticu cyklických posunov reťazca $S\$$
\item lexikograficky utriedime riadky matice 
\item $bw(S)$ je posledný stĺpec matice
\end{itemize}
Tretí krok vieme spočítať pomocou sufixového poľa: $bw(S)[i]=S[SA[i]-1]$, 
alebo $bw(S)[i]=S[n]$, ak $SA[i]=0$.

\paragraph{Príklad.}
Zoberme vstupný reťazec $S=$\,banana a pridajme nakoniec znak \$. Matica cyklických posunov a matica
utriedených cyklických posunov:
\begin{table}[h]
\begin{center}
\renewcommand{\arraystretch}{0.95}
\begin{tabular}{lllllll}
b & a & n & a & n & a & \$ \\
a & n & a & n & a & \$ & b \\
n & a & n & a & \$ & b & a \\
a & n & a & \$ & b & a & n \\
n & a & \$ & b & a & n & a \\
a & \$ & b & a & n & a & n \\
\$ & b & a & n & a & n & a \\
\end{tabular}
\hfill
\begin{tabular}{lllllll}
\$ & b & a & n & a & n & \bf a \\
a & \$ & b & a & n & a & \bf n \\
a & n & a & \$ & b & a & \bf n \\
a & n & a & n & a & \$ & \bf b \\
b & a & n & a & n & a & \bf \$ \\
n & a & \$ & b & a & n & \bf a \\
n & a & n & a & \$ & b & \bf a \\
\end{tabular}
\end{center}

$bw(S\$)$ = annb\$aa
\end{table}

\paragraph{Spätná transformácia.} Máme daný posledný stĺpec matice
lexikograficky usporiadaných cyklických rotácií.  Z neho vieme
spočítať prvý stĺpec tejto matice jednoduchým triedením posledného
stĺpca. Pre jednoduchosť označme prvý stĺpec matice $F$ a posledný
stĺpec $L$;\,\,$L=bw(S\$)$.

\begin{table}[h]
\begin{center}
\renewcommand{\arraystretch}{0.95}
\begin{tabular}{lll}
F & & L \\
\$ & \dots & a \\
a & \dots & n \\
a & \dots & n \\
a & \dots & b \\
b & \dots & \$ \\
n & \dots & a \\
n & \dots & a \\
\end{tabular}
\end{center}
\end{table}

Platí, že $F[i]$ nasleduje po $L[i]$ v $S$. Preto symbolu $\$$ v $L$ prislúcha $S[0]=b$.

Následne môžeme najsť $S[0]$ v $L$ a tým dostať $S[1]$ v $F$. Teda $S[1]=a$. Takto by sme mohli
pokračovať ďalej, no ku písmenu $a$ v $L$ prislúchajú písmená z množiny $\{n,\$\}$. Nevieme teda jednoznačne
určiť $S[2]$.

\begin{table}[h]
\begin{center}
\renewcommand{\arraystretch}{0.95}
\begin{tabular}{lllllll}
\bf \$ & b & a & n & a & n & \bf a$_5$ \\
\bf a$_5$ & \$ & b & a & n & a & \bf n$_4$ \\
\bf a$_3$ & n & a & \$ & b & a & \bf n$_2$ \\
\bf a$_1$ & n & a & n & a & \$ & \bf b \\
\bf b & a & n & a & n & a & \bf \$ \\
\bf n$_4$ & a & \$ & b & a & n & \bf a$_3$ \\
\bf n$_2$ & a & n & a & \$ & b & \bf a$_1$ \\
\end{tabular}
\end{center}
\end{table}

Môžeme si všimnúť, že relatívne poradie písmen $a$, alebo $n$ je v $L$ a $F$ rovnaké. Pozrime sa
napr. na písmená a v $F$. Ich poradie (5,3,1) je určené na základe kontextu  na konci (banan, ban,
b). Tento kontext určuje aj ich poradie v $L$.

Teraz už vieme jednoznačne vytvoriť pôvodný reťazec.
Nájdeme $S[0]$ v $L$, dostaneme $S[1]$ v $F$ ($S[1] =$ tretie  $a$).
Nájdeme tretie  $a$ v $L$, dostaneme $S[2]$ v $F$ ($S[2] =$ druhé $n$, atď.

Na realizáciu použijeme nasledovné dátové štruktúry.
\begin{table}[h]
\begin{center}
\renewcommand{\arraystretch}{0.95}
\begin{tabular}{lll}
0:&  \$$_0$ &  a$_0$ \\
1:&  a$_0$ &   n$_0$ \\
2:&  a$_1$ &   n$_1$ \\
3:&  a$_2$ &   b$_0$ \\
4:&  b$_0$ &  \$$_0$ \\
5:&  n$_0$ &   a$_1$ \\
6:&  n$_1$ &   a$_2$ \\
\end{tabular}
\end{center}
\end{table}

Reprezentácia pozícií písmen v $L$:\\
\$: 4\\
a: 0, 5, 6\\
b: 3\\
n: 1, 2

\subsubsection*{Použitie BWT v kompresii}
Riadky matice, v ktorej sú usporiadané cyklické reťazce, majú ako prefixy postupne prvky zo sufixového poľa. 
Prvky zo sufixovéhom poľa $SA$, ktoré majú spoločný prefix (v $SA$ sú za sebou) majú v $S$ často ako predchodcu rovnaké
písmeno. Tieto písmená sú práve v poslednom stĺpci matice. V nasledujúcom
príklade písmenu \verb '.'  predchádzajú písmená u,a, preto v $bw(S\$)$ je úsek obsahujúci iba tieto písmená.
\begin{eqnarray*}
S\ &=& \verb'ema.ma.mamu.mama.ma.emu.ema.sa.ma$'\\
bw(S\$) &=&\verb'auaaaauaammsmmmmmm$....ae.e..ea.mm'
\end{eqnarray*}
Môžeme použiť Move-to-front(MTF) recording, kde písmeno $S[i]$ nahradíme počtom rôznych písmen od
posledného výskytu $S[i]$ v $S[0..i-1]$. Pred reťazec $bw(S\$)$ ešte pridáme všetky písmená z
abecedy od najmenšieho po najväčší, aby sme vedeli skonštruovať postupnosť. 
\begin{eqnarray*}
&&\verb'$.aemsu|auaaaauaammsmmmmmm$....ae.e..ea.mm'\,\,\textrm{je zakódovaný do postupnosti}\\
&&\verb'        4110001103031000006600046211012240'
%4, 1, 1, 0, 0, 0, 1, 1, 0, 3, 0, 3, 1, 0, 0, 0, 0, 0, 6, 6, 0, 0, 0,
%4, 6, 2, 1, 1, 0, 1, 2, 2, 4, 0
\end{eqnarray*}
Z tejto postupnosti vieme ľahko získať $bw(S\$)$ a z neho $S$. V tejto postupnosti sú malé čísla,
veľa núl. Pre anglický text viac ako $50\%$ tvoria nuly. Takáto postupnosť je ľahko komprimovateľná.

% prepisany odstavec
V príklade je entropia $S$ rovná 2,37, entropia MTF reťazca $bw(S\$)$
je rovná 2,18. Napríklad pri použití aritmetického kódovania na
dostatočne dlhom reťazci potrebujeme na zakódovanie jedného znaku
v priemere počet bitov, ktorý sa približne rovná entropii.
Bližšie informácie o BWT nájdu záujemcovia v článoku Manzini: The
Burrows-Wheeler Transform: Theory and Practice. MFCS 1999, kapitola 2.

\subsection{TO DO}
V BWT miestami podrobnejšie vysvetliť, napr. použité dátové štruktúry.
