\input ../lecnotes.tex

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

\h{Zopakujeme si základní znaèení}
\itemize\ibull
\:$\iota_1 \ldots \iota_k$ - jehly
\:$\sigma$ text (seno)
\endlist

\h{Hledání výskytu v¹ech slov}
\itemize\ibull
\:Chceme najít v¹echny $(i,j)$ takové ¾e $\iota_i=\sigma[j:j+\vert\iota_i\vert]$
\:Postavíme vyhledávací automat
\endlist

\h{Vyhledávací automat} 
Teï si popí¹eme, jak se takovýto vyhledávací automat vytváøí. Vyhledávací automat je vlastnì obecný $n$-ární strom, do kterého jsou pøidány zpìtné hrany.

\s{Zpìtná hrana z$(\alpha)$ }:= nejdel¹í vlastní sufix slova $\alpha$, který je stavem.

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

\h{Hledání jehel v kupì sena}
Konkrétní algoritmus vyhledávání by se dal popsat takto:
\algo
\:$s \leftarrow koren$ (zaèínáme v koøeni)
\:$\forall$ c písmenka $\sigma$
\::$s \leftarrow krok(s,c)$
\::je-li $slovo(s) \ne 0 \Rightarrow vypi¹(slovo(s))$
\::$v \leftarrow out(s)$
\::dokud $v \ne 0 $
\:::vypi¹ $slovo(v)$
\:::$v \leftarrow out(v)$
\endalgo

\s{krok($s$,$c$)}:= jeden $krok$ vytváøení vyhledávacího algoritmu 

\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

\s{Výstup z automatu}
\itemize\ibull

\:\s{BARBARA} - konèí \s{BARBARA} ale taky \s{ARA}, ale o tom nevíme.
\:Slovo mù¾e konèit i tehdy, pokud v automatu není zaznaèen konec.
\endlist
\>Øeknìme si nìkolik návrhù na vypisování nalezených slov a¾ se dostaneme k tomu nejlep¹ímu.

\s{Vypisování nalezených slov}
\itemize\ibull
\:slovo, které v daném stavu konèí - nefunguje
\:projít v¹echy zpìtné hrany - funguje, ale pomalé
\:pøepoèítat mno¾iny - najít mno¾inu slov, aby celková velikost slov byla vìt¹í ne¾ lineární - nestihneme konstrukci
\:$slovo(s)$ = index $\iota_i$, která konèí ve stavu S, nebo $\emptyset$
\par $out(s)$ = nejbli¾¹í vrchol , do kterého se dá 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ýma hranama}{1.3in}
\endlist

\h{Slo¾itost}
\itemize\ibull
\:kroky 2.-5. mají èasouvou slo¾itost $O(s)$, kterou jednodu¹e doká¾eme pomocí potenciálu - kroku nahoru $ \leq $ kroku dolu $= max(\vert \sigma \vert) $
\:kroky 6.-8. mají èasovou slo¾itost $O($poèet výskytù$)$, co¾ je celkem logické, proto¾e rychleji opravdu nejdou vèechny výskyty vypsat
\endlist

\s{Konstrukce automatu} (Aho, Coracisková)
\algo
\:postavíme strom dopøedných hran r $\leftarrow$ koøen
\:spoèteme $slovo(\ast)$
\:spoèteme $z(\ast)$: $z(\beta)=\alpha(\beta[1:]) \{\beta[1:]$ slovo $\beta$ bez prvního písmene$\}$
\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, Q \leftarrow \{ synové(r) \}, \forall v \in Q : z(v) \leftarrow r$
\:dokud $ Q \ne 0$
\::$u\leftarrow$ vyber z $Q$ (7-9 ¹ipka)
\::pro syny $v$ vrcholu $u$:
\:::$z \leftarrow krok(z(u)$, znak $n \geq uv)$
\:::$z(v)\leftarrow R$

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

\s{Vìta:}
Algoritmus A-C najde v¹echny výskyty slov $\iota_1, \ldots, \iota_k$ ve slove $\sigma$ v èase $$O(\Sigma \vert \iota_i \vert + \vert \sigma \vert + \# výskytù)$$

\s{Reprezentace v pamìti}
\itemize\ibull
\:pole se seznamem synù
\:hashovací tabulka $(stav-znak) \rightarrow f(stav-znak)$ - pro velké abecedy
\endlist

\h{Polynomy a násobení}
Mìjme dva polynomy definované jako
$$P(x) = \sum_{j=0}^{n-1} p_j x^j$$
$$Q(x) = \sum_{j=0}^{n-1} q_j x^j$$
Provedení operace $R=P*R$ je ekvivalentní s $R = \sum_{j,k} p_j q_k k^{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^2)$ operací.

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

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

\s{Vyhodnocováni polynomu} (metodou rozdìl a panuj)

BÚNO $n=2^m$
$$P(x_j) = p_0 x^0 + p_1 x^1 + \ldots + p_{n-1} x^{n-1}$$
$$P(x_j) = (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})$$
$$P(x_j) = (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)$$

\>polynom s $n$ koeficienty v $n$ bodech $\rightarrow$ $2$ polynomy s $n/2$ koeficienty v $n/2$ bodech
$$T(n) = 2T(n/2) + O(n)$$
$$T(n) = O(n \log n)$$

\bye


