Korektury kapitoly o algoritmu AC.

[ads2.git] / 7-ac / 7-ac.tex

diff --git a/7-ac/7-ac.tex b/7-ac/7-ac.tex
index f8408a307e89186501fcc120efb19cb36be02018..09fe571d583b15e7c59840e5dffa48bac9a9cd36 100644 (file)
--- a/7-ac/7-ac.tex
+++ b/7-ac/7-ac.tex
@@ -2,124 +2,123 @@
 
 \prednaska{7}{Vyhledávání v textu}{(zapsali J. Kunèar, M. Demin a J. Chludil)}
 
 
 \prednaska{7}{Vyhledávání v textu}{(zapsali J. Kunèar, M. Demin a J. Chludil)}
 

+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.
+

 \h{Zopakujeme si základní znaèení}
 \itemize\ibull
 \h{Zopakujeme si základní znaèení}
 \itemize\ibull

-\:$\iota_1 \ldots \iota_k$ -- jehly
-\:$\sigma$ text (seno)
+\:$\iota_1, \ldots, \iota_k$ -- jehly
+\:$\sigma$ -- text (seno)

 \endlist
 
 \h{Hledání výskytu v¹ech slov}
 \endlist
 
 \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
-\endlist
+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.

 
 

-\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 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 "zkratky".

 
 

-\s{Zpìtná hrana z$(\alpha)$ }:= nejdel¹í vlastní sufix slova $\alpha$, který je stavem.
+\s{Stav} je pozice ve stromì, která odpovídá nejdel¹ímu prefixu vyhovující jehly v senì (platí rovnì¾ stejný \s{invariant} z pøedchozí pøedná¹ky).\par
+\s{Zpìtná hrana} $z$($\alpha$) := nejdel¹í vlastní suffix\foot{definováno na 6. pøedná¹ce} slova $\alpha$, který je stavem.\par

 
 \figure{vyhl_automat_dopr.eps}{Vyhledávací automat}{1in}
 
 
 \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í zaznaèen konec 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, jen¾ v daných stavech konèí. Toto øe¹ení funguje, ale je pomalé, proto¾e procházíme v¹echny zpìtné hrany.
+\: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á.
+\:\s{\<slovo>($s$)} = index slova $\iota$, které konèí ve stavu $s$, nebo $\emptyset$ \par
+\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)
+\figure{Graphic2.eps}{Vyhledávací automat -- se zpìtnými hranami}{1.3in}
+\endlist
+
+\>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ì".

 \algo
 \algo

-\:$s \leftarrow koren$ (zaèínáme v koøeni)
-\:$\forall$ c písmenka $\sigma$
-\::$s \leftarrow krok(s,c)$
-\::je-li \<slovo(s)> $\ne 0 \Rightarrow$ \<vypi¹(slovo(s))>
-\::$v \leftarrow out(s)$
-\::dokud $v \ne 0 $
-\:::vypi¹ \<slovo(v)>
-\:::$v \leftarrow$ \<out(v)>
+\:$s \leftarrow$ \<koøen> ($s$ je 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 \<slovo(s)> $\ne 0 \Rightarrow$ \<vypi¹(slovo(s))>.
+\::$v \leftarrow out(s)$.
+\::Dokud $v \ne 0 $:
+\:::Vypi¹ \<slovo(v)>.
+\:::$v \leftarrow$ \<out(v)>.

 \endalgo
 
 \endalgo
 

-\s{\<krok(s,c)>}:= jeden \<krok> vytváøení vyhledávacího algoritmu 
-
+\s{\<krok(s,c)>}:= jeden \<krok> ve vyhledávacím automatu

 \algo
 \algo

-\:dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow$ \<z(s)>
-\:pokud $\exists$ \<f(s,c)>: $s \leftarrow$ \<f(s,c)>
-\:vrátíme s
+\:Dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow$ \<z(s)>.
+\:Pokud $\exists f(s,c)$: $s \leftarrow$ \<f(s,c)>.
+\:Vrátíme $s$.

 \endalgo
 
 \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
-\:\<slovo(s)> = 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 \<slovo(v)> $\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 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 "ztratí" pou¾ívání hashovací funkce.

 
 \h{Slo¾itost}
 \itemize\ibull
 
 \h{Slo¾itost}
 \itemize\ibull

-\: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) $
-\: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
+\: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ù je maximálnì $\vert \sigma \vert$, kde  $\vert \sigma \vert$ je délka sena
+\:kroky 6.--8. mají èasovou slo¾itost $O$(\<poèet výskytù>), proto¾e rychleji opravdu nejdou v¹echny výskyty vypsat

 \endlist
 
 \endlist
 

-\s{Konstrukce automatu} (Aho, Coracisková)
+\s{Konstrukce automatu} (Aho, Corasicková)

 \algo
 \algo

-\:postavíme strom dopøedných hran r $\leftarrow$ koøen
-\:spoèteme \<slovo>$(\ast)$
-\:spoèteme $z(\ast)$: $z(\beta)=\alpha(\beta[1:]) \{\beta[1:]$ slovo $\beta$ bez prvního písmene$\}$
+\:Postavíme strom dopøedných hran, $r \leftarrow$ koøen stromu.
+\:Spoèteme \<slovo>($\ast$).
+\:Spoèteme $z(\ast)$: $z(\beta)=\alpha(\beta[1:])$.

 \itemize\ibull
 \:$z(\beta) = \alpha(\beta[1:])$ - v¹echny zpìtné hrany vedou do vy¹¹ích hladin
 \:\<z(v) = krok(z(u),c)>
 \endlist
 \itemize\ibull
 \:$z(\beta) = \alpha(\beta[1:])$ - v¹echny zpìtné hrany vedou do vy¹¹ích hladin
 \:\<z(v) = krok(z(u),c)>
 \endlist

-\figure{Graphic100.eps}{z(v)=Krok(z(u),c)}{0.7in}
-\:$z(r) \leftarrow 0, Q \leftarrow \{$ \<synové(r)> $\}, \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$ \<krok(z(u)>, znak $n \geq uv)$
-\:::$z(v)\leftarrow R$
+\figure{Graphic100.eps}{\<z(v) = krok(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$ vyber z $Q$.
+\::Pro syny $v$ vrcholu $u$:
+\:::$R \leftarrow$ \<krok>($z(u)$, znak na hranì \<uv>).
+\:::$z(v)\leftarrow R$.

 
 \figure{Graphic101.eps}{}{0.7in}
 
 \figure{Graphic101.eps}{}{0.7in}

-\:::je-li $slovo(z) \not= 0 \Rightarrow out(v) \leftarrow z$, jinak $out(v) = out(z)$
+\:::Je-li $slovo(R) \not= 0 \Rightarrow out(v) \leftarrow R$, jinak $out(v) = out(R)$.

 \figure{Graphic102.eps}{}{0.7in}
 \endalgo
 \figure{vyhl_automat_full.eps}{Vyhledávací automat -- kompletní}{1in}
 
 \s{Vìta:}
 \figure{Graphic102.eps}{}{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$ \<f(stav-znak)> -- pro velké abecedy
-\endlist
+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ù>)$$

 
 \h{Polynomy a násobení}
 Mìjme dva polynomy definované jako
 
 \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í.
+$$P(x) = \sum_{j=0}^{n-1} p_j x^j, Q(x) = \sum_{j=0}^{n-1} q_j x^j$$
+Násobení dvou polynomù $R=P*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í, teda na spoèítaní celého polynomu $R$ potøebujeme $\Theta(n^2)$ operací.\par

 
 

-\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ènosti existence polynomu nejvý¹e $k$-tého stupnì, pokud známe hodnoty v alespoò $k$ bodech.
+
+\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$

 
 \figure{polynom.eps}{Polynom}{2in}
 
 
 \figure{polynom.eps}{Polynom}{2in}
 

-\s{Vyhodnocováni polynomu} (metodou rozdìl a panuj)
+\s{Plán:}
+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)$.
+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$

 
 

-BÚNO $n=2^m$
+\s{Vyhodnocování polynomù} (metodou Rozdìl a panuj)\par
+\>BÚNO $n=2^m$\par
+\>Uvá¾me polynom:

 $$P(x_j) = p_0 x^0 + p_1 x^1 + \ldots + p_{n-1} x^{n-1}$$
 $$P(x_j) = p_0 x^0 + p_1 x^1 + \ldots + p_{n-1} x^{n-1}$$

+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.

 $$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}) + (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_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)$$
 $$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)$$

-
-\>polynom s $n$ koeficienty v $n$ bodech $\rightarrow$ $2$ polynomy s $n/2$ koeficienty v $n/2$ bodech
+Kde $L(x)$ a $N(x)$ jsou polynomy stupnì $n/2$. Umonìním $x^2$ se nám poru¹í párování $x$ a $-x$, proto musíme poèítat v $\bb{C}$.
+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:

 $$T(n) = 2T(n/2) + O(n)$$
 $$T(n) = 2T(n/2) + O(n)$$

+Co¾ mù¾eme vyøeøit s pou¾itím Master Theoremu z ADS 1 a dostáváme

 $$T(n) = O(n \log n)$$
 
 \bye
 $$T(n) = O(n \log n)$$
 
 \bye