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 Na minulých predná¹kách jsme si ukázali, jak se v textu vyhledává slovo. Teï si
   6 ov¹em úlohu zobecníme a uká¾eme si, jak v~kupce sena vyhledat více ne¾ jednu
   7 jehlu.
   8
   9 \h{Zopakujeme si základní znaèení}
  10 \itemize\ibull
  11 \:$\iota_1, \ldots, \iota_k$ -- jehly
  12 \:$\sigma$ -- text (seno)
  13 \endlist
  14
  15 \h{Hledání výskytu v¹ech slov}
  16 Nejprve si øeknìme, jak chceme aby vypadal výstup a poté jak ho dosáhnout. Výstupem pro nás budou v¹echny uspoøádané dvojice $(i,j)$ takové, ¾e $$\iota_i=\sigma[j:j+\vert\iota_i\vert]$$ Postavme si proto vyhledávací automat, který najde v¹echny takové uspoøádané dvojice.
  17
  18 \h{Vyhledávací automat}
  19 Vyhledávací automat je vlastnì obecný $n$-ární strom, kde jednotlivé hrany odpovedají písmenùm a vrcholy, ve kterých konèí slovo, jsou oznaèené (na obrazcích èernì). Do tohto vyhledávacího stromu budeme postupnì pøidávat zpìtné hrany.
  20
  21 \s{Zpìtná hrana} $z$($\alpha$) := nejdel¹í vlastní suffix\foot{definováno na 6. pøedná¹ce} slova $\alpha$, který je stavem.
  22
  23 \figure{vyhl_automat_dopr.eps}{Vyhledávací automat}{1in}
  24
  25 \h{Výstup z automatu}
  26 Pøi vypisování výsledkù mu¾eme narazit na urèité problémy. První problém urèitì nastane, proto¾e v automatu není pøesnì øeèeno, které slovo konèí v jakém vrcholu.
  27 Napøíklad ve stavu, kde konèí slovo BARBARA, konèí také slovo ARA, ale o tom nevíme.
  28 Druhý problém nastává, kdy¾ v automatu není zaznaèen konec slova. Pøíkladem je seno BARAB (jednoduché k nahlédnutí viz. obrázek).
  29 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:
  30 \itemize\ibull
  31 \:Projdeme v¹echy zpìtné hrany a vypí¹eme slova, jen¾ v daných stavech konèí. Toto øe¹ení funguje, ale je pomalé, proto¾e procházíme v¹echny zpìtné hrany.
  32 \:Pøepoèítání mno¾in. Najdeme mno¾inu slov tak, aby celková velikost slov byla vìt¹í ne¾ lineární. Funkèní, ale konstrukce je pomalá.
  33 \:\s{\<slovo>($s$)} = index slova $\iota$, které konèí ve stavu $s$, nebo $\emptyset$ \par
  34 \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)
  35 \figure{Graphic2.eps}{Vyhledávací automat -- se zpìtnými hranami}{1.3in}
  36 \endlist
  37
  38 \>Jako vhodné øe¹ení tohoto problému se naskýtá poslední bod. Podle nìho vytvoøíme algoritmus na vyhledávání "jehel v senì".
  39 \algo
  40 \:$s \leftarrow$ \<koøen> ($s$ je aktuální stav vyhledávacího automatu)
  41 \:procházíme v¹echny písmena $c$ v senì $\sigma$
  42 \::$s \leftarrow krok(s,c)$
  43 \::je-li \<slovo(s)> $\ne 0 \Rightarrow$ \<vypi¹(slovo(s))>
  44 \::$v \leftarrow out(s)$
  45 \::dokud $v \ne 0 $
  46 \:::vypi¹ \<slovo(v)>
  47 \:::$v \leftarrow$ \<out(v)>
  48 \endalgo
  49
  50 \s{\<krok(s,c)>}:= jeden \<krok> ve vyhledávacím automatu
  51 \algo
  52 \:Dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow$ \<z(s)>
  53 \:Pokud $\exists f(s,c)$: $s \leftarrow$ \<f(s,c)>
  54 \:Vrátíme $s$
  55 \endalgo
  56
  57 \s{Reprezentace v pamìti}
  58 \itemize\ibull
  59 \:pole se seznamem synù
  60 \:hashovací tabulka \<(stav,znak)> $\rightarrow$ \<f(stav,znak)> -- pro velké abecedy
  61 \endlist
  62
  63 \h{Slo¾itost}
  64 \itemize\ibull
  65 \:kroky 2.--5. mají èasovou slo¾itost $O(\vert \sigma \vert)$, kterou jednodu¹e doká¾eme pomocí potenciálu -- poèet krokù nahoru $ \leq $ poèet krokù dolù $= max(\vert \sigma \vert) $, kde  $\vert \sigma \vert$ je délka sena
  66 \:kroky 6.--8. mají èasovou slo¾itost \<O(poèet výskytù)>, proto¾e rychleji opravdu nejdou v¹echny výskyty vypsat
  67 \endlist
  68
  69 \s{Konstrukce automatu} (Aho, Corasicková)
  70 \algo
  71 \:postavíme strom dopøedných hran $r \leftarrow$ koøen stromu
  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$, do fronty $Q$ pøiøadíme v¹echny syny $r$, pro v¹echny $v$ prvky $Q: z(v) \leftarrow r$
  80 \:dokud fronta $Q$ není prázdná:
  81 \::$u\leftarrow$ vyber z $Q$
  82 \::pro syny $v$ vrcholu $u$:
  83 \:::$R \leftarrow$ \<krok>($z(u)$, znak na hranì \<uv>)
  84 \:::$z(v)\leftarrow R$
  85
  86 \figure{Graphic101.eps}{}{0.7in}
  87 \:::je-li $slovo(R) \not= 0 \Rightarrow out(v) \leftarrow R$, jinak $out(v) = out(R)$
  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_i \vert \iota_i \vert + \vert \sigma \vert + \# \<výskytù>)$$
  94
  95 \h{Polynomy a násobení}
  96 Mìjme dva polynomy definované jako
  97 $$P(x) = \sum_{j=0}^{n-1} p_j x^j, Q(x) = \sum_{j=0}^{n-1} q_j x^j$$
  98 Násobení dvou polynomù $R=P*Q$ je ekvivalentní s operací $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)$ operací, teda na spoèítaní celého polynomu $R$ potøebujeme $\Theta(n^2)$ operací.
  99
 100 \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$
 101
 102 \figure{polynom.eps}{Polynom}{2in}
 103
 104 \s{Plán:}
 105 Nech» $k=2n-1$, zvolíme $x_0, \ldots, x_k$  libolné, ale rùzná a spoèteme $P(x_0), \ldots, P(x_k)$ a $P(y_0), \ldots, P(y_k)$.
 106 \>$\forall j: y_j=P(x_j)Q(x_j)$
 107 \>musíme najít polynom $R$ stupnì $\leq k: \forall j: R(x_j)=y_j$
 108
 109 \s{Vyhodnocování polynomù} (metodou Rozdìl a panuj)\par
 110 \>BÚNO $n=2^m$\par
 111 \>Uvá¾me polynom:
 112 $$P(x_j) = p_0 x^0 + p_1 x^1 + \ldots + p_{n-1} x^{n-1}$$
 113 Tento polynom si mu¾eme rozdelit, na 2 èasti. V levé budeme mít èleny s exponentem sudým a v pravé budou èleny s lichými koeficienty.
 114 $$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})$$
 115 Z pravé strany mù¾eme vytknout $x$ a dostaneme:
 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 Musíme si ale uvìdomit, ¾e tyto vztahy platí pouze, kdy¾ existuje pár $-x$ a $x$ v tìlese, nad kterým poèítáme. V tomto pøípade jsme z polynomu s $n$ koeficienty v $n$ bodech dostali $2$ polynomy s $n/2$ koeficienty v $n/2$ bodech. Z èeho¾ vyplývá èasová slo¾itost definována vztahem:
 121 $$T(n) = 2T(n/2) + O(n)$$
 122 Co¾ mù¾eme vyøeøit s pou¾itím Master Theoremu z ADS 1 a dostáváme
 123 $$T(n) = O(n \log n)$$
 124
 125 \bye
 126
 127