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 ov¹em úlohu zobecníme a uká¾eme si, jak v kupce sena vyhledat více ne¾ jednu jehlu.
   6
   7 \h{Zopakujeme si základní znaèení}
   8 \itemize\ibull
   9 \:$\iota_1, \ldots, \iota_k$ -- vyhledávaná slova (jehly)
  10 \:$\sigma$ -- text, kde se hledá (seno)
  11 \endlist
  12
  13 \h{Hledání výskytu v¹ech slov}
  14 Nejprve si øekneme, 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.
  15
  16 \h{Vyhledávací automat}
  17 {\I Vyhledávací automat} je vlastnì 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 tohto vyhledávacího stromu pøidáme zpìtné hrany a \uv{zkratky}.
  18
  19 \s{Definice:} {\I Stav} je pozice ve stromì, která odpovídá nejdel¹ímu prefixu vyhovující jehly v senì (platí rovnì¾ stejný invariant z pøedchozí pøedná¹ky).
  20
  21 \s{Definice:} {\I 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, 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.
  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øedpoèí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 \:$\<slovo>(s) =$ index slova $\iota$, které konèí ve stavu $s$, nebo 0, \par
  34 $\<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í \uv{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$ vypí¹eme $\<slovo>(s)$.
  44 \::$v \leftarrow out(s)$.
  45 \::Dokud $v \ne 0 $:
  46 \:::Vypí¹eme $\<slovo>(v)$.
  47 \:::$v \leftarrow \<out>(v)$.
  48 \endalgo
  49
  50 \>$\<krok>(s,c) :=$ jeden krok ve vyhledávacím automatu:
  51 \algo
  52 \:Dokud $\neg \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 \h{Reprezentace v pamìti}
  58 První mo¾nost jak reprezentovat vyhledávací automat je pole se seznamem synù. 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.
  59
  60 \h{Slo¾itost}
  61 \itemize\ibull
  62 \: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ù $ \leq \vert \sigma \vert$, kde  $\vert \sigma \vert$ je délka sena.
  63 \:Kroky 6--8 mají èasovou slo¾itost $\O(\<poèet výskytù>)$, proto¾e rychleji opravdu nelze v¹echny výskyty vypsat.
  64 \endlist
  65
  66 \s{Konstrukce automatu (Aho, Corasicková)}
  67 \algo
  68 \:Postavíme strom dopøedných hran, $r \leftarrow$ koøen stromu.
  69 \:Spoèteme $\<slovo>(\ast)$ (spoèteme funkci \<slovo> pro v¹chny stavy).
  70 \:Spoèteme $z(\ast)$: $z(\beta)=\alpha(\beta[1:])$.
  71 \itemize\ibull
  72 \:$z(\beta) = \alpha(\beta[1:])$ -- v¹echny zpìtné hrany vedou do vy¹¹ích hladin
  73 \:$z(v) = \<krok>(z(u),c)$
  74 \endlist
  75 \figure{Graphic100.eps}{$\<z>(v) = \<krok>(z(u),c)$}{0.7in}
  76 \:$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$.
  77 \:Dokud fronta $Q$ není prázdná:
  78 \::$u\leftarrow$ vybereme z $Q$.
  79 \::Pro syny $v$ vrcholu $u$:
  80 \:::$R \leftarrow \<krok>(z(u)$, znak na hranì \<uv>).
  81 \:::$z(v)\leftarrow R$.
  82
  83 \figure{Graphic101.eps}{}{0.7in}
  84 \:::Je-li $slovo(R) \not= 0 \Rightarrow out(v) \leftarrow R$, jinak $out(v) \leftarrow out(R)$.
  85 \figure{Graphic102.eps}{}{0.7in}
  86 \endalgo
  87 \figure{vyhl_automat_full.eps}{Vyhledávací automat -- kompletní}{1in}
  88
  89 \s{Vìta:}
  90 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 + \<poèet výskytù>).$$
  91
  92 \h{Polynomy a násobení}
  93 \>Mìjme dva polynomy definované jako:
  94 $$P(x) = \sum_{j=0}^{n-1} p_j x^j, \quad Q(x) = \sum_{j=0}^{n-1} q_j x^j.$$
  95 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í.
  96
  97 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
  98 ve~více ne¾ $k$ bodech.
  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 \ss{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 $Q(x_0), \ldots, Q(x_k)$.
 106 Poté $\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)
 110
 111 \>BÚNO $n=2^m$. Uva¾me polynom:
 112 $$P(x) = p_0 x^0 + p_1 x^1 + \ldots + p_{n-1} x^{n-1}.$$
 113 Tento polynom si mu¾eme rozdìlit, na dvì èásti. V~levé budeme mít èleny se sudými exponenty a v~pravé budou èleny s exponenty lichými:
 114 $$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}).$$
 115 Z pravé strany mù¾eme vytknout $x$ a dostaneme:
 116 $$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})$$
 117 $$ \vdots $$
 118 $$P(x) = L(x^2) + xN(x^2),$$
 119 $$P(-x) = L(x^2) - xN(x^2),$$
 120 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}$.
 121 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øí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:
 122 $$T(n) = 2T(n/2) + \O(n).$$
 123 Ten mù¾eme vyøe¹it s pou¾itím Master Theoremu z~ADS~I a dostaneme:
 124 $$T(n) = \O(n \log n).$$
 125
 126 \bye
 127
 128