\section{Úsporné dátové štruktúry}

Pozor, táto časť obsahuje iba zopár útržkovitých poznámok, kombinácia
prezentácie a prípravy na hodinu.

\subsection{Úvod do úsporných štruktúr, úsporná štruktúra pre binárny strom
a pre rank a select}

Pozri prednášku 17, Erik Demaine, MIT\\ 
\url{http://courses.csail.mit.edu/6.851/spring12/lectures/}

\subsection{Zhrnutie rank/select}
Rank:
\begin{itemize}
\item trivialne riesenie n log n bitov, pamatam si rank pre kazde i
\item prakticke riesenie: pamatam si rank iba pre i*t pre nejake t, zvysok dopocitam
\item teoreticke riesenie: n+o(n) bitov: pamatam si rank kazdych t1 bitov, v ramci oblasti kratsi rank v ramci t2 bitov, predpocitana tabulka pre rank v ramci useku dlzky t2
\item poznamka: ak chceme spocitat rank$_0(i)$, pouzijeme i+1-rank$_1(i)$
\end{itemize}

Select:
\begin{itemize}
\item teoreticke riesenie: n+o(n) bitov, zlozitejsie ako rank
\item bin vyhladavanie so selectom O(log n) cas
\end{itemize}

\subsection{Binarny lexikograficky strom}
Na Erikovej prednaske sa vieme pohybovat po strome, ale nevieme
zistot, ci vnut. vrchol zodpoveda slovu v mnozine

Jednoduchy fix s 3n bitmi: bitovy vektor pre vsetky vrcholy stromu, poznac si, ktore vrcholy zodpovedaju slovu z mnoziny

Ktory sme ozajstny vrchol zisti pomocou rank

Pre tie slova, ktore su v mnozine mozeme mat dalsie pole indexovane cislom slova, ktore opat ziskame pomocou rank v tomto dalsom vektore, v tomto poli potom mozeme mat dalsie udaje, ako cisla dokumentov

Urcite existuju aj lepsie datove struktury, napr. nepotrebujeme explicitne ukladat bit pre listy


\subsection{Catalánove čísla}
Budeme uvažovať nasledujúce problémy:
\begin{itemize}
\item Koľko je binárnych stromov s $n$ vrcholmi?
\item Koľko je dobre uzátvorkovaných výrazov s $n$ pármi zátvoriek?
\item Koľko je postupností, ktoré obsahujú $n$ krát číslo +1 a 
$n$ krát -1 a pre ktoré sú všetky prefixové súčty nezáporné?
\end{itemize}
Už sme videli, že prvé dva z týchto problémov sú navzájom
ekvivalentné.  Druhé dva sú tiež ekvivalentné, lebo stačí každú ľavú
zátvorku nahradiť +1 a každú pravú zátvorku -1. Aby bol výraz dobre
uzátvorkovaný, v každom jeho prefixe musí byť aspoň toľko ľavých
zátvoriek ako pravých a teda v postupnosti +1 a -1 máme nezáporný
prefixový súčet.

Ukážeme teraz, že odpoveďou na všetky tri uvedené problémy je
Catalánove číslo $C_n = {2n\choose n}/(n+1)$ ($C_0 = 1, C_1=1, C_2 =
2, C_3 = 5,\dots$)

\begin{figure}
\def\myhead{$A$\qquad\qquad\quad $B$}
\begin{tabular}{ccc}
\myhead & \myhead & \myhead \\
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-00.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-01.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-02.eps}\\
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-03.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-04.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-05.eps}\\
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-06.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-07.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-08.eps}\\
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-09.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-10.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-11.eps}\\
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-12.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-13.eps}&
\includegraphics[width=0.3\textwidth]{figures/l22-catalan-14.eps}\\
\end{tabular}
\caption{Ilustrácia dôkazu o Catalánových číslach. Bijekcia medzi prvkami množín $A=X(3,3,-\infty)\setminus X(3,3,0)$ a $B=X(2,4,-\infty)$. Grafy zobrazujú prefixové súčty. Vedľa seba sú vždy 
zodpovedajúce si prvky z $A$ a $B$, prevrátená časť je zobrazená červenou.}
\label{fig:l22-catalan}
\end{figure}

%http://www.ams.org/journals/bull/2002-39-01/S0273-0979-01-00928-4/
Nech $X(n,m,k)$ je množina vsetkých postupností dĺžky $n+m$ obsahujúcich $n$ krát číslo +1, $m$ krát číslo -1 takých, že každý prefixový súčet je aspoň $k$. 
My chceme spočítať veľkosť množiny $X(n,n,0)$. 

Ak by sme nekládli žiadne požiadavky na prefixové súčty, dostali by
sme množinu $X(n,m,-\infty)$. Veľkosť tejto množiny je
$|X(n,m,-\infty)| = {n+m \choose n}$, lebo z celkových 
$n+m$ pozícií v postupnosti musíme zvoliť $n$, na ktorých bude hodnota
+1, na ostatných bude -1.

Uvažujme teraz množinu $A = X(n,n,-\infty)\setminus X(n,n,0)$,
t.j. množinu všetkých ``zlých'' postupností, v ktorých prefixový súčet
aspoň raz klesne pod nulu. Ukážeme, že táto množina je rovnako veľká
ako množina $B=X(n-1,n+1,-\infty)$. V množine $B$ sú prefixové súčty
ľubovoľné a teda jej veľkosť vieme spočítať.  Našim cieľom
je nájsť zobrazenia $f:A\rightarrow B$ a $g:B\rightarrow A$, ktoré sú
navzájom inverzné a teda ide o dve bijekcie, potvrdzujúce rovnakú
veľkosť množín $A$ a $B$.

Vezmime teda nejakú postupnosť $a_1\dots a_{2n}$ z $A$ a nájdime
najmenší index $i$, že súčet $a_1+\cdots+a_i$ je $-1$. Postupnosť
$f(a_1\dots a_{2n})\in B$ zostavíme tak, že od indexu $i$ napravo
zmeníme znamienka na opačné (obr. \ref{fig:l22-catalan}). Nakoľko
súčet celej postupnosti $a_1,\dots,a_{2n}$ je 0 a súčet jej prvých
$i$ členov je -1, súčet zvyšných členov je +1. Keď im zmeníme
znamienka na opačné, ich súčet bude -1 a teda súčet celej zmenenej
postupnosti bude -2, musí teda obsahovať $n-1$ krát $+1$ a $n+1$ krát
$-1$. Ide teda naozaj o postupnosť z množiny $B$. 

Naopak hodnotu zobrazenia $g$ pre nejakú postupnosť $b_1\dots
b_{2n}\in B$ zostavíme tak, že opäť nájdeme prvý index $i$, kde
prefixový súčet klesne na -1 (taký musí existovať, lebo celkový súčet
je -2). Opäť všetkým členom postupnosti napravo od $i$ zmeníme
znamienka na opačné. Takto zjavne dostávame zobrazenie inverzné k $f$.

Dokázali sme teda, že $|A|=|B|={2n \choose n-1}$. Počet dobre uzátvorkovaných 
postupností je teda 
$|X(n,n,0)| = |X(n,n,-\infty)|-|X(n-1,n+1,-\infty)|={2n \choose n} -
{2n \choose n-1}$. Ľahkou úpravou výrazov môžeme overiť, že tento
rozdiel je rovný ${2n \choose n}/(n+1)$.

Iný spôsob ako odvodiť vzorec pre počet dobre uzátvorkovaných výrazov
je najskôr zapísať tento počet rekurenciou. Nech teda $T(n)$ je počet
dobre uzátvorkovaných výrazov s $n$ pármi zátvoriek. Pre $n=0$
uvažujeme prázdny výraz za dobre uzátvorkovaný, máme teda $T(0)=1$.
Pre $n>0$ uvažujme prvú ľavú zátvorku a jej zodpovedajúcu pravú
zátvorku.  Nech $i$ je počet párov zátvoriek medzi týmito
dvoma. Vnútri tohto najľavejšieho páru môžeme zátvorky
rozmiestniť $T(i)$ spôsobmi a zvyšné zátvorky sú napravo od tohto páru
a môžu tam byť rozmiestnené $T(n-i-1)$ spôsobmi. Dostávame teda
rekurenciu $T(n) = \sum_{i=0}^{n-1} T(i)T(n-i-1)$. Ak túto rekurenciu
vyriešime metódami kombinatorickej analýzy, dostávame opäť Catalánove
čísla. Na riešenie je možné použiť napríklad generujúce funkcie.
%pozri Concrete mathematics

\subsection{Wavelet tree: Rank nad väčšou abecedou}
\begin{itemize}
\item Namiesto bitového poľa máme reťazec $S$ nad väčšou abecedou $\Sigma$
\item Chceme podporovat rank$_a(i)$, co je pocet vyskytov pismena $a$ v retazci $S[0..i]$
\item OPT je $n \log_2 \sigma$
\item Pouzijeme rank na binarnych retazcoch nasledovne:
\item rozdelime abecedu na dve casti $\Sigma_0$ a $\Sigma_1$ 
\item Vytvorime bin. retazec B dlzky n: B[i]=1 iff S[i] je v $\Sigma_1$
\item Vytvorime retazce $S_0$ a $S_1$, kde $S_i$ obsahuje pismena z S, ktore su v $\Sigma_i$, sucet dlzok je n
\item Rekurzivne pokracujeme v deleni abecedy a retazcov, az kym nedostaneme abecedy velkosti 2
\end{itemize}
rank$_a(i)$ v tejto strukture: 
\begin{itemize}
\item ak $a \in \Sigma_j$, i=rank$_j(i)$ v retazci B
\item pokracuj rekurzivne s vypoctom rank$_a(i)$ v lavom alebo pravom podstrome
\end{itemize}

Velkost: binarne retazce $n \log_2 \sigma$ + struktury pre rank nad bin. retazcami (mozem skonkatenovat na kazdej urovni a dostat $o(n \log_2 \sigma)$

Cas $O(\log \sigma)$, robim jeden rank na kazdej urovni. Extrahovanie S[i]
tiez v case $O(\log \sigma)$


\paragraph{Príklad:}
$\Sigma_0=\{\$,.,a\}$, $\Sigma_1=\{e,m,u\}$

{\small
\begin{verbatim}
i    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
T[i] e  m  a  .  m  a  .  m  a  m  u  .  m  a  m  a  .  m  a  .  e  m  u  $
B[i] 1  1  0  0  1  0  0  1  0  1  1  0  1  0  1  0  0  1  0  0  1  1  1  0
T0   a.a.a.aa.a.$
T1   emmmmummmemu 
\end{verbatim}}


\subsection{FM index}
\begin{itemize}
\item Ferragina and Manzini 2000
\item hladanie vyskytov P v T pomocou BWT a ranku
\item T dlzky n, pripojime \$ na poziciu T[n]
\item zostrojime sufixove pole SA pre T a $T' = BWT(T)$
\item zostrojime wavelet tree pre T', vieme ratat rank$_a(i)$ v T'
\item spocitame $C[a]=\sum_{b\in\Sigma,b<a}$ pocet vyskytov b v T
\item nech L(S) = najmensi index i t.z. S je prefix T[SA[i]..n]
\item nech R(S) = najvacsi index ...
\item pre S = epsilon, mame L(S)=0, R(S)=n
\item ak aS je podslovo T, $L(aS) = C[a]+rank_a(L(S)-1)$
\item ak aS je podslovo T, $R(aS) = C[a]+rank_a(R(S))-1$
\item navyse ak S je podslovo T, tak aS je podslovo T prave vtedy ak L(aS)<=R(aS)
\item Opakujeme pre stale dlhsie sufixy P, nakoniec dostaneme interval SA, kde sa nachadzaju vyskyty - spatne hladanie
\item vieme teda v O(|P|) testovat, ci ma vyskyt a kolko ich je, nepotrebujeme ani SA, iba wavelet tree
\item existuju aj techniky na kompaktnejsie ulozenie SA
\end{itemize}

\paragraph{Priklad}

{\scriptsize
\begin{verbatim}
i      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
T[i]   e  m  a  .  m  a  .  m  a  m  u  .  m  a  m  a  .  m  a  .  e  m  u  $
SA[i] 23 19 16  3 11  6 18 15  2  5 13  8  0 20 17 14  1  4 12  7 21  9 22 10

T'[i]  u  a  a  a  u  a  m  m  m  m  m  m  $  .  .  a  e  .  .  .  e  a  m  m
r$(i)  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1  1  1
r.(i)  0  0  0  0  0  0  0  0  0  0  0  0  0  1  2  2  2  3  4  5  5  5  5  5    
ra(i)  0  1  2  3  3  4  4  4  4  4  4  4  4  4  4  5  5  5  5  5  5  6  6  6
re(i)  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  2  2  2  2
rm(i)  0  0  0  0  0  0  1  2  3  4  5  6  6  6  6  6  6  6  6  6  6  6  7  8
ru(i)  1  1  1  1  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2
\end{verbatim}

\begin{verbatim}
x      $  .  a  e  m  u
C(x)   0  1  6 12 14 22 
\end{verbatim}


\begin{verbatim}
hladam .ama
L(epsilon) = 0
R(epsilon) = 23
L(a) = C(a) + ra(L(epsilon)-1) = 6 + ra(-1) = 6
R(a) = C(a) + ra(R(epsilon))-1 = 6 + ra(23)-1 = 11
L(ma) = C(m) + rm(L(a)-1) = 14 + rm(5) = 14  
R(ma) = C(m) + rm(R(a))-1 = 14 + rm(11) - 1 = 19  
L(ama) = C(a) + ra(L(ma)-1) = 6 + ra(13) = 10
R(ama) = C(a) + ra(R(ma))-1 = 6 + ra(19) - 1 = 10
L(.ama) = C(.) + r.(L(ama)-1) = 1 + r.(9) =  1
R(.ama) = C(.) + r.(R(ama))-1 = 1 + r.(10)-1 =  0
\end{verbatim}

\begin{verbatim}
 0 23 $
 1 19 .emu$
 2 16 .ma.emu$
 3  3 .ma.mamu.mama.ma.emu$
 4 11 .mama.ma.emu$
 5  6 .mamu.mama.ma.emu$
 6 18 a.emu$
 7 15 a.ma.emu$
 8  2 a.ma.mamu.mama.ma.emu$
 9  5 a.mamu.mama.ma.emu$
10 13 ama.ma.emu$
11  8 amu.mama.ma.emu
12  0 ema.ma.mamu.mama.ma.emu$
13 20 emu$
14 17 ma.emu$
15 14 ma.ma.emu$
16  1 ma.ma.mamu.mama.ma.emu$
17  4 ma.mamu.mama.ma.emu$
18 12 mama.ma.emu$
19  7 mamu.mama.ma.emu$
20 21 mu$
21  9 mu.mama.ma.emu$
22 22 u$
23 10 u.mama.ma.emu$
\end{verbatim}
}

\subsection{TODO}
Prerobiť na normálne poznámky, pridať niečo z MIT prednášky.



\end{document}
