3 \prednaska{7}{Vyhledávání v textu}{(zapsali J. Kunèar, M. Demin a J. Chludil)}
5 \h{Zopakujeme si základní znaèení}
7 \:$\iota_1 \ldots \iota_k$ - jehly
11 \h{Hledání výskytu v¹ech slov}
13 \:Chceme najít v¹echny $(i,j)$ takové ¾e $\iota_i=\sigma[j:j+\vert\iota_i\vert]$
14 \:Postavíme vyhledávací automat
17 \h{Vyhledávací automat}
18 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.
20 \s{Zpìtná hrana z$(\alpha)$ }:= nejdel¹í vlastní sufix slova $\alpha$, který je stavem.
22 \figure{vyhl_automat_dopr.eps}{Vyhledávací automat}{1in}
24 \h{Hledání jehel v kupì sena}
25 Konkrétní algoritmus vyhledávání by se dal popsat takto:
27 \:$s \leftarrow koren$ (zaèínáme v koøeni)
28 \:$\forall$ c písmenka $\sigma$
29 \::$s \leftarrow krok(s,c)$
30 \::je-li $slovo(s) \ne 0 \Rightarrow vypi¹(slovo(s))$
31 \::$v \leftarrow out(s)$
34 \:::$v \leftarrow out(v)$
37 \s{krok($s$,$c$)}:= jeden $krok$ vytváøení vyhledávacího algoritmu
40 \:dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow z(s)$
41 \:pokud $\exists f(s,c) : s \leftarrow f(s,c)$
48 \:\s{BARBARA} - konèí \s{BARBARA} ale taky \s{ARA}, ale o tom nevíme.
49 \:Slovo mù¾e konèit i tehdy, pokud v automatu není zaznaèen konec.
51 \>Øeknìme si nìkolik návrhù na vypisování nalezených slov a¾ se dostaneme k tomu nejlep¹ímu.
53 \s{Vypisování nalezených slov}
55 \:slovo, které v daném stavu konèí - nefunguje
56 \:projít v¹echy zpìtné hrany - funguje, ale pomalé
57 \:pøepoèítat mno¾iny - najít mno¾inu slov, aby celková velikost slov byla vìt¹í ne¾ lineární - nestihneme konstrukci
58 \:$slovo(s)$ = index $\iota_i$, která konèí ve stavu S, nebo $\emptyset$
59 \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)
60 \figure{Graphic2.eps}{Vyhledávací automat - se zpìtnýma hranama}{1.3in}
65 \: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) $
66 \: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
69 \s{Konstrukce automatu} (Aho, Coracisková)
71 \:postavíme strom dopøedných hran r $\leftarrow$ koøen
72 \:spoèteme $slovo(\ast)$
73 \:spoèteme $z(\ast)$: $z(\beta)=\alpha(\beta[1:]) \{\beta[1:]$ slovo $\beta$ bez prvního písmene$\}$
75 \:$z(\beta) = \alpha(\beta[1:])$ - v¹echny zpìtné hrany vedou do vy¹¹ích hladin
76 \:$z(v) = krok(z(u),c)$
78 \figure{Graphic100.eps}{z(v)=Krok(z(u),c)}{0.7in}
79 \:$z(r) \leftarrow 0, Q \leftarrow \{ synové(r) \}, \forall v \in Q : z(v) \leftarrow r$
81 \::$u\leftarrow$ vyber z $Q$ (7-9 ¹ipka)
82 \::pro syny $v$ vrcholu $u$:
83 \:::$z \leftarrow krok(z(u)$, znak $n \geq uv)$
84 \:::$z(v)\leftarrow R$
86 \figure{Graphic101.eps}{}{0.7in}
87 \:::je-li $slovo(z) \not= 0 \Rightarrow out(v) \leftarrow z$, jinak $out(v) = out(z)$
88 \figure{Graphic102.eps}{}{0.7in}
90 \figure{vyhl_automat_full.eps}{Vyhledávací automat - kompletní}{1in}
93 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ù)$$
95 \s{Reprezentace v pamìti}
97 \:pole se seznamem synù
98 \:hashovací tabulka $(stav-znak) \rightarrow f(stav-znak)$ - pro velké abecedy
101 \h{Polynomy a násobení}
102 Mìjme dva polynomy definované jako
103 $$P(x) = \sum_{j=0}^{n-1} p_j x^j$$
104 $$Q(x) = \sum_{j=0}^{n-1} q_j x^j$$
105 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í.
107 \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$
109 \figure{polynom.eps}{Polynom}{2in}
111 \s{Vyhodnocováni polynomu} (metodou rozdìl a panuj)
114 $$P(x_j) = p_0 x^0 + p_1 x^1 + \ldots + p_{n-1} x^{n-1}$$
115 $$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})$$
116 $$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})$$
118 $$P(x) = L(x^2) + xN(x^2)$$
119 $$P(-x) = L(x^2) + xN(x^2)$$
121 \>polynom s $n$ koeficienty v $n$ bodech $\rightarrow$ $2$ polynomy s $n/2$ koeficienty v $n/2$ bodech
122 $$T(n) = 2T(n/2) + O(n)$$
123 $$T(n) = O(n \log n)$$