\section{Obsah predmetu a  motivácia}

\paragraph{Základný problém (vyhľadávanie vzorky v texte, string matching):}
dané sú dva reťazce: vzorka (pattern) $P$ a text $T$. Nájdite všetky
výskyty $P$ v $T$.

\paragraph{Príklad:} $P=$''ma '' $T=$''Ema ma mamu''.
Vzorka $P$ má dva výskyty na pozíciách 2 a 5 reťazca $T$.

\paragraph{Príklady využitia:}
Vyhľadávacia funkcia v textových editoroch, internetových
prehliadačoch a podobne. UNIXové nástroje ako grep. 
Práca s textovými atribútmi v relačných
databázach, napríklad nasledujúci dotaz nájde apple,
pineapple, apples atď.:

\centerline{\tt select name from fruits where name like "\%apple\%"}  

Ukážeme si niekoľko efektívnych algoritmov pre tento problém
(Knuth-Morris-Pratt, Boyer-Moore a iné). Budeme tiež študovať aj
ďalšie varianty tohto problému popísané nižšie.

\paragraph{Problém:} V texte $T$ chceme vyhľadať všetky výskyty niekoľkých
vzoriek $P_1, P_2, \dots, P_k$.

\paragraph{Príklad využitia:} hľadanie vírusov, detekcia spamu, 
monitorovanie siete pred útočníkmi

Ukážeme si rozšírenia algoritmov zo základného problému, ktoré fungujú
v tomto prípade (Ahov-Corasickovej algoritmus).

\paragraph{Problém:} V texte $T$ chceme postupne vyhľadať výskyty rôznych
vzoriek $P1, P2, \dots$ Chceme si text $T$ predspracovať (zostaviť index),
aby sme odpoveď pre každú vzorku vedeli nájsť rýchlejšie.  Tento problém sa
líši od predchádzajúceho v tom, že vzorky nemáme dané naraz, ale
prichádzajú po jednej a pre každú máme nájsť odpoveď, kým príde ďalšia.

\paragraph{Príklad:} internetové vyhľadávanie, knižničný katalóg 

Ukážeme si efektívne dátové štruktúry na tento účel (sufixové stromy a
polia). Tieto štruktúry tiež umožňujú efektívne riešiť problémy typu:
nájdite najdlhšie podslovo, ktoré sa nachádza v daných dvoch
reťazcoch.

\paragraph{Problém:} V texte $T$ nájdite všetky podslová, ktoré sú podobné
na vzor $P$ (majú od $P$ napr. Hammingovu alebo editačnú vzdialenosť
najviac $k$).

\paragraph{Príklad:} vyhľadávanie v texte s preklepmi, detekcia plagiátorstva,
detekcia príbuzných génov, ktoré vznikli zo spoločného predka
mutáciami

Budeme sa venovať algoritmom na výpočet editačnej vzdialenosti medzi
reťazcami a na nájdenie približných výskytov vzorky.

V poslednej časti semestra sa budeme venovať niekoľkým problémom,
ktoré porovnávajú viacero textov a ktoré pochádzajú z bioinformatiky.


\subsection{Označenie}

Budeme používať štandardné označenie na prácu s reťazcami, ktoré
poznáte napríklad z formálnych jazykov.

Abeceda $\Sigma$ je konečná množina znakov (symbolov), jej veľkosť
budeme označovať $\sigma$. Slovo (reťazec) nad abecedou $\Sigma$ je
postupnosť $s_0s_1\dots s_{n-1}$. Dĺžku slova $S$ označujeme
$|S|$. Prázdne slovo (slovo dĺžky 0) označujeme $\varepsilon$. Pre
slovo $S=s_0s_1\dots s_{n-1}$ budeme $S[i..j]$ označovať podslovo
$s_is_{i+1}\dots s_j$, kde $0\le i\le j< n$. Ak $i>j$, $S[i..j]$
definujeme ako prázdny reťazec. $S[i]$ označuje $i$-ty znak slova $S$.
Podslovo $S[i..j]$ je prefix slova $S$ ak $i=0$ a sufix, ak
$j=|S|-1$. Vlastné podslovo slova $S$ je také podslovo, ktoré sa nerovná
$S$ (podobne vlastný sufix, prefix). Zreťazenie slov $S$ a $S'$
označujeme $SS'$. {\bf Upozornenie:} niektoré časti textu číslujú pozície 
v texte od 1.


\section{Vyhľadávanie kľúčových slov}

%pridaj veci z prezentacie

Dokument -- Sekvencia slov\\
Dotaz -- Pre dané slovo w nájsť všetky dokumenty, ktoré ho obsahujú\\
Cieľ -- vytvoriť index pre statickú množinu dokumentov, aby sme vedeli efektívne odpovedať na dotazy


\paragraph{Príklad}~\\
\textbf{Dokument 0} : Ema ma mamu.\\
\textbf{Dokument 1} : Mama ma Emu.\\
\textbf{Dokument 2} : Mama sa ma. Ema sa ma.\\[0.2cm]
\textbf{Dotaz:} Mama\\
\textbf{Odpoveď:} Document 1, Document 2

V praxi ako dokument uvažujeme web stránku, email, knihu, kapitoly, atď. Dokument môžeme predspracovať -- lower/upper case, úprava na základný tvar, ako su oddelené slová, synonymá, atď. Ak máme veľa dokumentov, vzniká otázka, ako ich ohodnotiť.

\subsection{Invertovaný index (inverted index)}
Cieľom je vytvoriť utriedený zoznam slov a pri každom si pamätať, v ktorých dokumentoch sa nachádza (nezaujíma nás koľko krát).

\paragraph{Príklad}~\\
Ema : 0,2 \\
Emu : 1 \\
ma : 0,1,2 \\
Mama : 1,2 \\
mamu : 0 \\
sa : 2

\paragraph{Statická implementácia pomocou polí}
\begin{itemize}
\item Sadu dokumentov / url / súborov si namapujeme na čísla $(0,1,\ldots)$. 
\item Všetky slová si namapujeme na zoznamy ich výskytov v dokumentoch. 
\item Všetky výskyty slov si budeme pamätať v jednom veľkom poli, v druhom si budeme pamätať slová a index do poľa výskytov.
\end{itemize}

\paragraph{Príklad}~\\
\textbf{Pole 1} = (0,2,1,0,1,2,1,2,0,2) \\
\textbf{Pole 2} = (Ema - 0, Emu - 2, ma - 3, Mama - 6, mamu - 8, sa - 9, \$ - 10)

\paragraph{Vyhľadávanie}
Hľadáme slovo dĺžky $m$, dohromady majme $n$ slov a výsledok nám vráti $k$ výsledkov. Čas potrebný na nájdenie slova bude:
\begin{itemize}
\item vyhľadáme slovo v zozname pomocou binárneho vyhľadávania $O(\log n)$. 
\item každé porovnanie ale trvá $O(m)$
\item prejdeme $k$ výsledkov
\end{itemize}
Dohromady to je $O(m\log n + k)$

\begin{figure}
\includegraphics{figures/l00-bintree.eps}
\caption{Príklad binárneho stromu}
\end{figure}

\paragraph{Vytvorenie štruktúry}
Danú štruktúru vytvoríme nasledovne:
\begin{itemize}
\item v každom dokumente utriedime všetky slová
\item v každom dokumente odstránime duplicitné slová
\item všetky slová dáme dohromady pričom si zapamätáme, v ktorom dokumente boli
\item tento velký zoznam ešte raz utriedime a jedným prechodom vytvoríme obe polia
\end{itemize}

Nech $N$ je veľkosť vytvoreného poľa 1. Potom celková zložitosť bude $O(m N\log  N)$

Pri tejto implementácii však vznikne problém, ak pridáme nový dokument. Musíme obidve polia kompletne poposúvať, čo je náročné.

Miesto poľa sa dá použiť na pamätanie si slov binárny vyhľadávací strom, ktorý v listoch bude mať spájané zoznamy výskytov. Ak zabezpečíme vyváženosť stromu, čas sa nezmení a problém s vkladaním sa odstráni. Prehľad zložitosti týchto dátových štruktúr sa nachádza v tabuľke \ref{tab:keyword}.

Keď je databáza textov veľká a musí byť uložená na disku, používajú sa B-trees.


\begin{table}
\caption{Zložitosť vyhľadávania a predspracovane pre rôzne implementácie 
invertovaného indexu.}
\label{tab:keyword}
\begin{tabular}{lll}
\hline
     & Dotaz & Predspracovanie \\
\hline
Utriedené pole & $O(m\log n + p)$ & $O(mN\log N)$ \\
Vyhľ. strom & $O(m\log n + p)$ & $O(mN\log n)$ \\
Hašovanie - najh. prípad & $O(mn + p)$ & $O(mNn)$ \\
Hašovanie - priem. prípad & $O(m + p)$ & $O(mN)$ \\
Lex. strom & $O(m\log\sigma + p)$ & $O(mN\log\sigma)$ \\
\hline
\end{tabular}
\end{table}

\subsection{Lexikografické stromy (trie)}
\label{kap:trie}

Ďalšou možnosťou ako implementovať zoznam slov pre invertovaný index
je použiť lexikografický strom, čo je stromová štruktúra špecificky určená na
ukladanie množín reťazcov. Každá hrana lexikografického stromu zodpovedá
nejakému znaku a cesta z koreňa do nejakého vrchola zodpovedá slovu na ceste.

\begin{figure}
\includegraphics{figures/l00-trie.eps}
\caption{Trie (lexikografický strom)}
\end{figure}

\subsubsection*{Vyhľadávanie}
                          
Slovo w dĺžky m

\begin{lstlisting}
node =root;
for (i=0; i<m; i++) {
  node = node-> child[w[i]]
  if (!node) return empty list
}
return list of node
\end{lstlisting}

\vspace{3mm}\hspace{-6mm}čas -- O(m) -- nezáleží na tom, aký veľký je strom, čas vždy závisí iba od dĺžky slova


\subsubsection*{Pridanie nového slova}

Pridávame slovo w, ktoré sa nachádza v dokumente D

\begin{lstlisting}
node = root;
for(i=0; i<m; i++) {
   if(! node->child[w[i]]) {
     node->child[w[i]] = new node;
   }
   node = node->child[w[i]];
}
node->list.add(D)
\end{lstlisting}

\vspace{3mm}\hspace{-6mm}čas - O(m)

\paragraph{Zložitosť pri veľkej abecede.}

%novy odstavec
Uvažujme niekoľko slov s dĺžkami $n_1\dots n_z$, celková dĺžka $N$,
veľkosť abecedy $\sigma$, dĺžka dotazu $m$.  Lexikografické stromy sú
dobré na reprezentáciu pri konštantnej abecede, pri veľkých abecedách
musíme vyriešiť problém, ako uložiť smerníky na deti v každom vrchole
tak, aby sme rýchlo vedeli pokračovať po hrane označenej určitým
písmenom abecedy. Môžeme použiť napríklad takéto alternatívy:

%cely itemize novy text
\begin{itemize}
\item Pole detí indexované znakmi abecedy. Toto sa jednoducho
  implementuje a nájsť príslušné dieťa vieme v $O(1)$ čase. Môžeme
  však strácať pamäť, ak máme veľa prázdnych položiek. Celkové pamäť
  je $O(N\sigma)$, čas na vloženie slov $O(N\sigma)$, hľadanie slova
  $O(m)$.

\item Pole dynamickej veľkosti, do ktorého uložíme iba skutočne
  existujúce deti a kvôli rýchlemu hľadaniu ich utriedime podľa
  abecedy. Pamäť je $O(N)$, vyhľadávanie beží v čase $O(m \log
  \sigma)$.  Pridávanie jedného slova trvá $O(n_i \log \sigma +
  \sigma)$, lebo iba v poslednom existujúcom vrchole potrebujeme
  vkladať nový prvok do zoznamu v čase $O(\sigma)$. V ostatných
  krokoch buď nájdeme znak v zozname binárnym vyhľadávaním v čase
  $O(\log \sigma)$, alebo vytvoríme nový vrchol s jediným dieťaťom v
  čase $O(1)$. Všetky slová teda pridáme v čase $O(N \log \sigma + z \sigma)$. 

\item Vyvážené vyhľadávacie stromy, v ktorých klúčom sú znaky abecedy.
  Pamäť je $O(N)$, vyhľadávanie beží v čase $O(m \log \sigma)$ a vkladanie
  všetkých slov v čase $O(N \log \sigma)$.

\end{itemize}


\subsection{Viacero kľúčových slov}

Given several keywords, find documents that contain all of them
(intersection, AND). Let us consider 2 keywords, one with m documents,
other with n, m<n. Assume that for each keyword we have a sorted array
of occurrences (sorted e.g. by document ID, pagerank,...)  

Solution 1: Similar to merge in mergesort O(m+n):
\begin{lstlisting}
i=0; j=0;
while(i<m && j<n) {
  if(a[i]==b[j]) { print a[i]; i++; j++; }
  else if(a[i]<b[j]) { i++; } 
  else { j++; }
}
\end{lstlisting}

Sometimes arrays are long, result short - can we improve? Rewrite a little bit: 

\begin{lstlisting}
j = 0;
for(i=0; i<m; i++) {
    find smallest k>=j s.t. b[k]>=a[i]; (*)
    if(k==n) { break; }
    j=k;
    if(a[i]==b[j]) {
      print a[i]; 
      j++;
    }
}
\end{lstlisting}

How to do (*):

\begin{itemize}
\item linear search \verb'k=j; while(k<n && b[k]<a[i]) { k++; }' 
the same algorithm as before
\item binary search in b[j..n] $O(m\log n)$, faster for very small m

\item doubling search/galloping search Bentley, Yao 1976 (general
  idea), Demaine, Lopez-Ortiz, Munro 2000 (application to
  intersection, more complex alg.), see also Baeza-Yates, Salinger
  (nice overview):
\end{itemize}

\begin{lstlisting}
step = 1; k = j; k2=k;
while(k<n && b[k]<a[i]) {
   k2=k; k=j+step; step*=2; 
}
binary search in b[k2..k];
\end{lstlisting}

If k=j+x, doubling search needs O(log x) steps. Overall running time
of the algorithm: doubling search at most times, each time eliminates
some number of elements, log(x1)+log(x2)+...log(xm) such that
x1+x2+...+xm<=n and the sum is maximized. Happens for equally sized
xi's, each n/m elements, $O(m\log(n/m))$ time. For constant m
logarithmic, for large m linear. Also better than simple merge if
different clusters of similar values in each cluster. If more than 2
keywords, iterate (possible starting with smallest lists), or extend
this algorithm.

\subsection{To do}

Viac textu v casti o invertovanom indexe, preložiť a sTeXovať časť o
viacerých kľúčových slovách.
