7-ac/7-ac.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{7}{Vyhledávání v textu}{(zapsali J. Kunèar, M. Demin a J. Chludil)}
   4
   5 \h{Zopakujeme si základní znaèení}
   6 \itemize\ibull
   7 \:$\iota_1 \ldots \iota_k$ -- jehly
   8 \:$\sigma$ text (seno)
   9 \endlist
  10
  11 \h{Hledání výskytu v¹ech slov}
  12 \itemize\ibull
  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
  15 \endlist
  16
  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.
  19
  20 \s{Zpìtná hrana z$(\alpha)$ }:= nejdel¹í vlastní sufix slova $\alpha$, který je stavem.
  21
  22 \figure{vyhl_automat_dopr.eps}{Vyhledávací automat}{1in}
  23
  24 \h{Hledání jehel v kupì sena}
  25 Konkrétní algoritmus vyhledávání by se dal popsat takto:
  26 \algo
  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)$
  32 \::dokud $v \ne 0 $
  33 \:::vypi¹ \<slovo(v)>
  34 \:::$v \leftarrow$ \<out(v)>
  35 \endalgo
  36
  37 \s{\<krok(s,c)>}:= jeden \<krok> vytváøení vyhledávacího algoritmu
  38
  39 \algo
  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)>
  42 \:vrátíme s
  43 \endalgo
  44
  45 \s{Výstup z automatu}
  46 \itemize\ibull
  47
  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.
  50 \endlist
  51 \>Øeknìme si nìkolik návrhù na vypisování nalezených slov a¾ se dostaneme k tomu nejlep¹ímu.
  52
  53 \s{Vypisování nalezených slov}
  54 \itemize\ibull
  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ými hranami}{1.3in}
  61 \endlist
  62
  63 \h{Slo¾itost}
  64 \itemize\ibull
  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
  67 \endlist
  68
  69 \s{Konstrukce automatu} (Aho, Coracisková)
  70 \algo
  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$\}$
  74 \itemize\ibull
  75 \:$z(\beta) = \alpha(\beta[1:])$ - v¹echny zpìtné hrany vedou do vy¹¹ích hladin
  76 \:\<z(v) = krok(z(u),c)>
  77 \endlist
  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$
  80 \:dokud $ Q \ne 0$
  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$
  85
  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}
  89 \endalgo
  90 \figure{vyhl_automat_full.eps}{Vyhledávací automat -- kompletní}{1in}
  91
  92 \s{Vìta:}
  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ù)$$
  94
  95 \s{Reprezentace v pamìti}
  96 \itemize\ibull
  97 \:pole se seznamem synù
  98 \:hashovací tabulka \<(stav-znak)> $\rightarrow$ \<f(stav-znak)> -- pro velké abecedy
  99 \endlist
 100
 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í.
 106
 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$
 108
 109 \figure{polynom.eps}{Polynom}{2in}
 110
 111 \s{Vyhodnocováni polynomu} (metodou rozdìl a panuj)
 112
 113 BÚNO $n=2^m$
 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})$$
 117 $$ \vdots $$
 118 $$P(x) = L(x^2) + xN(x^2)$$
 119 $$P(-x) = L(x^2) + xN(x^2)$$
 120
 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)$$
 124
 125 \bye
 126
 127