\input ../lecnotes.tex

\prednaska{7}{Vyhledávání v textu}{(zapsali J. Kunèar, M. Demin a J. Chludil)}

Na minulých predná¹kách jsme si ukázali, jak se v~textu (senì) vyhledává slovo (jehlu). Teï si ov¹em úlohu zobecníme a uká¾eme si, jak v kupce sena hledat souèasnì více ne¾ jednu jehlu.

\h{Hledání výskytu v¹ech slov}

\itemize\ibull
\:$\iota_1, \ldots, \iota_k$ -- vyhledávaná slova (jehly) délek $ J_i= \vert\iota_i\vert $
\:$\sigma$ -- text (seno) délky $ S= \vert\sigma\vert $
\endlist
Nejprve si øekneme, jak chceme, aby vypadal výstup. Výstupem pro nás budou v¹echny uspoøádané dvojice $(i,j)$ ($i$ je index jehly, kterou jsme nalezli, a $j$ je poèáteèní pozice v senì, kde se jehla nachází) takové, ¾e $$\iota_i=\sigma[j:j+J_i].$$ Postavme si proto vyhledávací automat podobný tomu, který jsme vidìli na minulé pøedná¹ce. Tento automat nám v¹echny takové uspoøádané dvojice najde.


\h{Vyhledávací automat}
Vyhledávací automat je strom\foot{http://en.wikipedia.org/wiki/Trie}, kde ka¾dý vrchol mù¾e mít stupeò a¾ do velikosti abecedy a kde jednotlivé hrany odpovídají písmenùm této abecedy. Vrcholy, ve kterých konèí slovo, jsou oznaèené (na obrazcích èernì). Dále si èasem do tohoto vyhledávacího stromu pøidáme zpìtné hrany a \uv{zkratky}.

\s{\I{Stavy}} automatu jsou urèeny vrcholy stromu, pro které platí rovnì¾ stejný {\I{invariant}} z pøedchozí pøedná¹ky.\par
\s{\I{Zpìtná hrana}} $z$($\alpha$) := nejdel¹í vlastní suffix\foot{definováno na minulé pøedná¹ce} slova $\alpha$, který je stavem.\par

\figure{vyhl_automat_dopr.eps}{Vyhledávací automat}{1in}

\h{Výstup z automatu}
Pøi vypisování výsledkù mu¾eme narazit na urèité problémy, které jsou dobøe vidìt na následujícím obrázku. První problém urèitì nastane, proto¾e v automatu není pøesnì øeèeno, které slovo konèí v jakém vrcholu.
Napøíklad ve stavu, kde konèí slovo BARBARA, konèí také slovo ARA, ale o tom nevíme.
Druhý problém nastává, kdy¾ v automatu není informace o~konci slova. Pøíkladem je seno BARAB (jednoduché k~nahlédnutí, viz obrázek).
Teï nám nezbývá nic jiného, ne¾ najít øe¹ení tìchto záludných problémù. Øe¹e¹í se nám naskýtá hned nìkolik:
\itemize\ibull
\:Projdeme v¹echy zpìtné hrany a vypí¹eme slova, je¾ v daných stavech konèí. Toto øe¹ení funguje, ale je pomalé, proto¾e poka¾dé procházíme v¹echny zpìtné hrany.
%\:Pøedpoèítání mno¾in slov. Najdeme mno¾inu slov tak, aby celková velikost slov byla vìt¹í ne¾ lineární. Funkèní, ale konstrukce je pomalá.
\:Pro následující øe¹ení, jen¾ spoèívá v nalezení zkratek ve stromì, si zavedeme toto znaèení:\par 
\s{\<slovo>($s$)} = index slova $\iota$, které konèí ve stavu $s$, nebo $\emptyset$ \par
\s{\<out>($s$)} = nejbli¾¹í vrchol, do kterého se lze z $s$ dostat po zpìtných hranách a \<slovo(v)> $\ne 0$ (konèí tam slovo)
\figure{Graphic2.eps}{Vyhledávací automat se zpìtnými hranami}{1.3in}
\endlist

\>Podle posledního bodu vytvoøíme algoritmus na vyhledávání \uv{jehel v senì}.
\algo
\:$s \leftarrow$ \<koøen> ($s$ bude aktuální stav vyhledávacího automatu).
\:Procházíme v¹echny písmena $c$ v senì $\sigma$:
\::$s \leftarrow krok(s,c)$.
\::Je-li $\<slovo>(s) \ne 0$, vypí¹eme $\<slovo>(s)$.
\::$v \leftarrow \<out>(s)$.
\::Dokud $v \ne 0$:
\:::Vypí¹eme $\<slovo>(v)$.
\:::$v \leftarrow \<out>(v)$.
\endalgo

\s{\<krok(s,c)>}:= jeden \<krok> vyhledávacího automatu:
\algo
\:Dokud $\not\exists f(s,c) \wedge s \ne$ \<koøen>: $s \leftarrow z(s)$.
\:Pokud $\exists f(s,c)$: $s \leftarrow f(s,c)$.
\:Vrátíme $s$.
\endalgo

\h{Reprezentace v pamìti}
První mo¾nost, jak reprezentovat vyhledávací automat, je jednorozmìrné pole vrcholù stromu, v nìm¾ ukládáme seznam synù pro ka¾dý vrchol. Je to jednoduchá varianta, ale má nevýhodu pro velké abecedy, proto¾e procházení seznamu synù mù¾e trvat neúmìrnì dlouho. Proto se nabízí druhá mo¾nost a to hashovací tabulka $(\<stav>,\<znak>) \rightarrow f(\<stav>,\<znak>)$, kde se \uv{ztratí} pou¾ívání hashovací funkce.

\h{Slo¾itost}
\itemize\ibull
\:Kroky 2.--5. mají èasovou slo¾itost $\O(\vert \sigma \vert)$, kterou jednodu¹e doká¾eme pomocí potenciálu -- poèet krokù nahoru je men¹í nebo roven poètu krokù dolù. A to je maximálnì $S$.
\:Kroky 6.--8. mají èasovou slo¾itost $\O(\<poèet výskytù>)$, proto¾e rychleji opravdu nelze v¹echny výskyty vypsat.
\endlist

\s{Konstrukce automatu} (Aho, Corasicková)
\algo
\:Postavíme strom dopøedných hran, $r \leftarrow$ koøen stromu.
\:Spoèteme $\<slovo>(\ast)$ -- oznaèíme si stavy, kde konèí slova.
\:Spoèteme $z(\ast)$: $z(\beta)=\alpha(\beta[1:])$:
    {\parindent=6em \itemize\ibull
    \:\>\>\>$z(\beta) = \alpha(\beta[1:])$ -- v¹echny zpìtné hrany vedou do vy¹¹ích hladin
    \:$z(v) = \<krok>(z(u),c)$
    \endlist}
\figure{Graphic100.eps}{$\<z>(v) = \<krok>(z(u),c)$}{0.7in}
\:$z(r) \leftarrow 0$, do fronty $Q$ pøiøadíme v¹echny syny $r$, pro v¹echny $v$ prvky $Q: z(v) \leftarrow r$.
\:Dokud fronta $Q$ není prázdná:
\::$u\leftarrow$ vybereme z~$Q$.
\::Pro syny $v$ vrcholu $u$:
\:::$R \leftarrow \<krok>(z(u))$ [znak na hranì \<uv>].
\:::$z(v)\leftarrow R$.

\figure{Graphic101.eps}{}{0.7in}
\:::Je-li $slovo(R) \not= 0 \Rightarrow \<out>(v) \leftarrow R$, jinak $\<out>(v) \leftarrow \<out>(R)$.
\figure{Graphic102.eps}{}{0.7in}
\endalgo
\figure{vyhl_automat_full.eps}{Vyhledávací automat -- kompletní}{1in}

\s{Vìta:}
Algoritmus Aho-Corasicková najde v¹echny výskyty slov $\iota_1, \ldots, \iota_k$ ve~slovì $\sigma$ v~èase $\O(\sum_i \vert \iota_i \vert + \vert \sigma \vert + \<poèet výskytù>)$.

\h{Polynomy a násobení}
\>Mìjme dva polynomy definované jako:
$$P(x) = \sum_{j=0}^{n-1} p_j x^j, \quad Q(x) = \sum_{j=0}^{n-1} q_j x^j.$$
Násobení dvou polynomù $R=P \cdot Q$ je ekvivalentní s operací $R = \sum_{j,k} p_j q_k x^{j+k}$. Pøièem¾ na vypoèítání èlenu $r_l = \sum_{j=0}^l p_j q_{l-j}$ pou¾ijeme $\Theta(n)$ operací, tedy na spoèítaní celého polynomu $R$ potøebujeme $\Theta(n^2)$ operací.

Podíváme se na jinou mo¾nost, jak tento problém øe¹it. Poslou¾í nám k~tomu následující vìta o jednoznaèné existenci polynomu nejvý¹e $k$-tého stupnì, pokud známe hodnoty
ve~více ne¾ $k$ bodech.

\s{Vìta:} Jsou-li $x_0, \ldots, x_k \in \bb{R} $ navzájem ruzná a $y_0, \ldots, y_k \in \bb{R}$, pak $\exists !$ polynom $P$ stupnì $\leq k : \forall j: P(x_j) = y_j$.

\figure{polynom.eps}{Polynom}{2in}

\ss{Plán:}
\>Nech» $k=2n-1$, zvolíme $x_0, \ldots, x_k$  libovolná, ale rùzná, a spoèteme $P(x_0), \ldots, P(x_k)$ a $Q(x_0), \ldots, Q(x_k)$.
Poté $\forall j: y_j=P(x_j)Q(x_j)$
musíme najít polynom $R$ stupnì $\leq k: \forall j: R(x_j)=y_j$.

\s{Vyhodnocování polynomù} (metodou Rozdìl a panuj)

\>BÚNO $n=2^m$. Uva¾me polynom:
$$P(x) = p_0 x^0 + p_1 x^1 + \ldots + p_{n-1} x^{n-1}.$$
Tento polynom si mu¾eme rozdìlit na dvì èasti. V levé budeme mít èleny se sudými exponenty a v~pravé budou èleny s~exponenty lichými:
$$P(x) = (p_0 + p_2 x^2 + \ldots + p_{n-2}x^{n-2}) + (p_1 x^1 + p_3 x^3 + \ldots + p_{n-1} x^{n-1}).$$
Z pravé strany mù¾eme vytknout $x$ a dostaneme:
$$P(x) = (p_0 + p_2 x^2 + \ldots + p_{n-2}x^{n-2}) + x(p_1 + p_3 x^2 + \ldots + p_{n-1} x^{n-2}),$$
$$ \vdots $$
$$P(x) = L(x^2) + xN(x^2),$$
$$P(-x) = L(x^2) - xN(x^2),$$
kde $L(x)$ a $N(x)$ jsou polynomy stupnì $n/2$. Umocnìním $x^2$ se nám poru¹í párování $x$ a $-x$, proto musíme poèítat v~$\bb{C}$ místo~$\bb{R}$.
V~tomto pøípadì jsme z~polynomu s~$n$ koeficienty v~$n$ bodech dostali $2$ polynomy s~$n/2$ koeficienty v~$n/2$ bodech. Z~toho vyplývá èasová slo¾itost definována vztahem:
$$T(n) = 2T(n/2) + \O(n).$$
Ten mù¾eme vyøe¹it s pou¾itím Master Theoremu z~ADS~I a dostaneme:
$$T(n) = \O(n \log n).$$

\bye
