X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=7-ac%2F7-ac.tex;h=d0293751da1618bc672687139f1050156787ce05;hb=075a28c6e7227aeaf9f0486e099ba18da0a9c289;hp=f8408a307e89186501fcc120efb19cb36be02018;hpb=f81463b774c133e8023c605dfc96be9343f5d5c1;p=ads2.git diff --git a/7-ac/7-ac.tex b/7-ac/7-ac.tex index f8408a3..d029375 100644 --- a/7-ac/7-ac.tex +++ b/7-ac/7-ac.tex @@ -2,126 +2,126 @@ \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 +Na minulých predná¹kách jsme si ukázali, jak se v~textu (senì) vyhledává slovo (jehlu). Teï si ov¹em úlohu zobecníme a uká¾eme si, jak v kupce sena hledat souèasnì více ne¾ jednu jehlu. \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 +\:$\iota_1, \ldots, \iota_k$ -- vyhledávaná slova (jehly) délek $ J_i= \vert\iota_i\vert $ +\:$\sigma$ -- text (seno) délky $ S= \vert\sigma\vert $ \endlist +Nejprve si øekneme, jak chceme, aby vypadal výstup. Výstupem pro nás budou v¹echny uspoøádané dvojice $(i,j)$ ($i$ je index jehly, kterou jsme nalezli, a $j$ je poèáteèní pozice v senì, kde se jehla nachází) takové, ¾e $$\iota_i=\sigma[j:j+J_i].$$ Postavme si proto vyhledávací automat podobný tomu, který jsme vidìli na minulé pøedná¹ce. Tento automat nám v¹echny takové uspoøádané dvojice najde. + -\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. +\h{Vyhledávací automat} +Vyhledávací automat je 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 tohoto vyhledávacího stromu pøidáme zpìtné hrany a \uv{zkratky}. -\s{Zpìtná hrana z$(\alpha)$ }:= nejdel¹í vlastní sufix slova $\alpha$, který je stavem. +\s{\I{Stavy}} automatu jsou urèeny vrcholy stromu, pro které platí rovnì¾ stejný {\I{invariant}} z pøedchozí pøedná¹ky.\par +\s{\I{Zpìtná hrana}} $z$($\alpha$) := nejdel¹í vlastní suffix\foot{definováno na minulé pøedná¹ce} slova $\alpha$, který je stavem.\par \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: +\h{Výstup z automatu} +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. +Napøíklad ve stavu, kde konèí slovo BARBARA, konèí také slovo ARA, ale o tom nevíme. +Druhý problém nastává, kdy¾ v automatu není informace o~konci slova. Pøíkladem je seno BARAB (jednoduché k~nahlédnutí, viz obrázek). +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: +\itemize\ibull +\:Projdeme v¹echy zpìtné hrany a vypí¹eme slova, je¾ v daných stavech konèí. Toto øe¹ení funguje, ale je pomalé, proto¾e poka¾dé procházíme v¹echny zpìtné hrany. +%\:Pøedpoèítání mno¾in slov. Najdeme mno¾inu slov tak, aby celková velikost slov byla vìt¹í ne¾ lineární. Funkèní, ale konstrukce je pomalá. +\:Pro následující øe¹ení, jen¾ spoèívá v nalezení zkratek ve stromì, si zavedeme toto znaèení:\par +\s{\($s$)} = index slova $\iota$, které konèí ve stavu $s$, nebo $\emptyset$ \par +\s{\($s$)} = nejbli¾¹í vrchol, do kterého se lze z $s$ dostat po zpìtných hranách a \ $\ne 0$ (konèí tam slovo) +\figure{Graphic2.eps}{Vyhledávací automat se zpìtnými hranami}{1.3in} +\endlist + +\>Podle posledního bodu vytvoøíme algoritmus na vyhledávání \uv{jehel v senì}. \algo -\:$s \leftarrow koren$ (zaèínáme v koøeni) -\:$\forall$ c písmenka $\sigma$ -\::$s \leftarrow krok(s,c)$ -\::je-li \ $\ne 0 \Rightarrow$ \ -\::$v \leftarrow out(s)$ -\::dokud $v \ne 0 $ -\:::vypi¹ \ -\:::$v \leftarrow$ \ +\:$s \leftarrow$ \ ($s$ bude aktuální stav vyhledávacího automatu). +\:Procházíme v¹echny písmena $c$ v senì $\sigma$: +\::$s \leftarrow krok(s,c)$. +\::Je-li $\(s) \ne 0$, vypí¹eme $\(s)$. +\::$v \leftarrow \(s)$. +\::Dokud $v \ne 0$: +\:::Vypí¹eme $\(v)$. +\:::$v \leftarrow \(v)$. \endalgo -\s{\}:= jeden \ vytváøení vyhledávacího algoritmu - +\s{\}:= jeden \ vyhledávacího automatu: \algo -\:dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow$ \ -\:pokud $\exists$ \: $s \leftarrow$ \ -\:vrátíme s +\:Dokud $\not\exists f(s,c) \wedge s \ne$ \: $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 -\:\ = 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 \ $\ne 0$ (konèí tam slovo) -\figure{Graphic2.eps}{Vyhledávací automat -- se zpìtnými hranami}{1.3in} -\endlist +\h{Reprezentace v pamìti} +První mo¾nost, jak reprezentovat vyhledávací automat, je jednorozmìrné pole vrcholù stromu, v nìm¾ ukládáme seznam synù pro ka¾dý vrchol. 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 $(\,\) \rightarrow f(\,\)$, kde se \uv{ztratí} pou¾ívání hashovací funkce. \h{Slo¾itost} \itemize\ibull -\:kroky 2.-5. mají èasouvou slo¾itost \, kterou jednodu¹e doká¾eme pomocí potenciálu - kroku nahoru $ \leq $ kroku dolu $= max(\vert \sigma \vert) $ -\:kroky 6.-8. mají èasovou slo¾itost \, co¾ je celkem logické, proto¾e rychleji opravdu nejdou vèechny výskyty vypsat +\:Kroky 2.--5. mají èasovou slo¾itost $\O(\vert \sigma \vert)$, kterou jednodu¹e doká¾eme pomocí potenciálu -- poèet krokù nahoru je men¹í nebo roven poètu krokù dolù. A to je maximálnì $S$. +\:Kroky 6.--8. mají èasovou slo¾itost $\O(\)$, proto¾e rychleji doopravdy nelze v¹echny výskyty vypsat. \endlist -\s{Konstrukce automatu} (Aho, Coracisková) +\s{Konstrukce automatu} (Aho, Corasicková) \algo -\:postavíme strom dopøedných hran r $\leftarrow$ koøen -\:spoèteme \$(\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 -\:\ -\endlist -\figure{Graphic100.eps}{z(v)=Krok(z(u),c)}{0.7in} -\:$z(r) \leftarrow 0, Q \leftarrow \{$ \ $\}, \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$ \, 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} +\:Postavíme strom dopøedných hran, $r \leftarrow$ koøen stromu. +\:Spoèteme $\(\ast)$ -- oznaèíme si stavy, kde konèí slova. +\:Spoèteme $z(\ast)$: $z(\beta)=\alpha(\beta[1:])$: + {\parindent=6em \itemize\ibull + \:\>\>\>$z(\beta) = \alpha(\beta[1:])$ -- v¹echny zpìtné hrany vedou do vy¹¹ích hladin + \:$z(v) = \(z(u),c)$ + \endlist} +\figure{Graphic100.eps}{$z(v) = \(z(u),c)$}{0.7in} +\:$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$. +\:Dokud fronta $Q$ není prázdná: +\::$u\leftarrow$ vybereme z~$Q$. +\::Pro syny $v$ vrcholu $u$: +\:::$R \leftarrow \(z(u))$ [znak na hranì \]. +\:::$z(v)\leftarrow R$. + +\figure{Graphic101.eps}{$z(v) = R$}{0.7in} +\:::Je-li $slovo(R) \not= 0 \Rightarrow \(v) \leftarrow R$, jinak $\(v) \leftarrow \(R)$. +\figure{Graphic102.eps}{Nastavení $\(v)$}{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$ \ -- pro velké abecedy -\endlist +Algoritmus Aho-Corasicková najde v¹echny výskyty slov $\iota_1, \ldots, \iota_k$ ve~slovì $\sigma$ v~èase $\O(\sum_i \vert \iota_i \vert + \vert \sigma \vert + \)$. \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í. +\>Mìjme dva polynomy definované jako: +$$P(x) = \sum_{j=0}^{n-1} p_j x^j, \quad Q(x) = \sum_{j=0}^{n-1} q_j x^j.$$ +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í. -\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$ +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 +ve~více ne¾ $k$ bodech. -\figure{polynom.eps}{Polynom}{2in} +\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$. -\s{Vyhodnocováni polynomu} (metodou rozdìl a panuj) +\figure{polynom.eps}{Polynom}{2in} -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)$$ +\ss{Plán:} -\>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)$$ +\>Nech» $k=2^{n-1}$. Zvolíme èísla $x_0, \ldots, x_k$ libovolná, ale rùzná, a spoèteme $P(x_0)$, \dots, $P(x_k)$ a $Q(x_0), \ldots, Q(x_k)$. +Poté $\forall j: y_j=P(x_j)Q(x_j)$ +musíme najít polynom $R$ stupnì $\leq k: \forall j: R(x_j)=y_j$. -\bye +\s{Vyhodnocování polynomù} (metodou Rozdìl a panuj) +\>BÚNO $n=2^m$. Uva¾me polynom: +$$P(x) = p_0 x^0 + p_1 x^1 + \ldots + p_{n-1} x^{n-1}.$$ +Tento polynom si mu¾eme rozdìlit na dvì èasti. V levé budeme mít èleny se sudými exponenty a v~pravé budou èleny s~exponenty lichými: +$$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}).$$ +Z pravé strany mù¾eme vytknout $x$ a dostaneme: +$$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}),$$ +$$ \vdots $$ +$$P(x) = L(x^2) + xN(x^2),$$ +$$P(-x) = L(x^2) - xN(x^2),$$ +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}$ místo~$\bb{R}$. +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: +$$T(n) = 2T(n/2) + \O(n).$$ +Ten mù¾eme vyøe¹it s pou¾itím Master Theoremu z~ADS~I a dostaneme: +$$T(n) = \O(n \log n).$$ +\bye