From 803253be8a92091997e531f78824c2ff0f6b7268 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 18 Dec 2007 09:24:08 +0100 Subject: [PATCH] Korektury kapitoly o algoritmu AC. --- 7-ac/7-ac.tex | 81 +++++++++++++++++++++++++-------------------------- 1 file changed, 40 insertions(+), 41 deletions(-) diff --git a/7-ac/7-ac.tex b/7-ac/7-ac.tex index c53379b..09fe571 100644 --- a/7-ac/7-ac.tex +++ b/7-ac/7-ac.tex @@ -2,9 +2,7 @@ \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. +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 @@ -15,21 +13,22 @@ jehlu. \h{Hledání výskytu v¹ech slov} 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} -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. +\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í suffix\foot{definováno na 6. pøedná¹ce} 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} \h{Výstup z automatu} -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. +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ø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á. +\: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{\($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} @@ -37,74 +36,73 @@ Te \>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 -\:$s \leftarrow$ \ ($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 \ $\ne 0 \Rightarrow$ \ -\::$v \leftarrow out(s)$ -\::dokud $v \ne 0 $ -\:::vypi¹ \ -\:::$v \leftarrow$ \ +\:$s \leftarrow$ \ ($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 \ $\ne 0 \Rightarrow$ \. +\::$v \leftarrow out(s)$. +\::Dokud $v \ne 0 $: +\:::Vypi¹ \. +\:::$v \leftarrow$ \. \endalgo -\s{\}:= jeden \ ve vyhledávacím automatu +\s{\}:= jeden \ ve vyhledávacím automatu \algo -\:Dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow$ \ -\:Pokud $\exists f(s,c)$: $s \leftarrow$ \ -\:Vrátíme $s$ +\:Dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow$ \. +\:Pokud $\exists f(s,c)$: $s \leftarrow$ \. +\:Vrátíme $s$. \endalgo -\s{Reprezentace v pamìti} -\itemize\ibull -\:pole se seznamem synù -\:hashovací tabulka \<(stav,znak)> $\rightarrow$ \ -- pro velké abecedy -\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$ \, kde se "ztratí" pou¾ívání hashovací funkce. \h{Slo¾itost} \itemize\ibull -\: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 -\:kroky 6.--8. mají èasovou slo¾itost \, 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$(\), proto¾e rychleji opravdu nejdou v¹echny výskyty vypsat \endlist \s{Konstrukce automatu} (Aho, Corasicková) \algo -\:postavíme strom dopøedných hran $r \leftarrow$ koøen stromu -\:spoèteme \($\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 \($\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 \:\ \endlist \figure{Graphic100.eps}{\}{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$ \($z(u)$, znak na hranì \) -\:::$z(v)\leftarrow R$ +\:Dokud fronta $Q$ není prázdná: +\::$u\leftarrow$ vyber z $Q$. +\::Pro syny $v$ vrcholu $u$: +\:::$R \leftarrow$ \($z(u)$, znak na hranì \). +\:::$z(v)\leftarrow R$. \figure{Graphic101.eps}{}{0.7in} -\:::je-li $slovo(R) \not= 0 \Rightarrow out(v) \leftarrow R$, jinak $out(v) = out(R)$ +\:::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:} -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 + \# \)$$ +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 + \)$$ \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$$ -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í. +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 + +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} -\s{Plán:} +\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)$. -\>$\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$ +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$ \s{Vyhodnocování polynomù} (metodou Rozdìl a panuj)\par \>BÚNO $n=2^m$\par @@ -117,6 +115,7 @@ $$P(x_j) = (p_0 + p_2 x^2 + \ldots + p_{n-2}x^{n-2}) + x(p_1 + p_3 x^2 + \ldots $$ \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$. 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)$$ Co¾ mù¾eme vyøeøit s pou¾itím Master Theoremu z ADS 1 a dostáváme -- 2.39.2