From 488e4bbc010355f92fd562345dd3889076f6552f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 15 Jan 2012 22:25:24 +0100 Subject: [PATCH] KMP: Dokonceni algoritmu AC --- 1-kmp/1-kmp.tex | 91 ++++++++++++++++++++++++++++++++----------------- 1 file changed, 59 insertions(+), 32 deletions(-) diff --git a/1-kmp/1-kmp.tex b/1-kmp/1-kmp.tex index 87c5c93..2fd259b 100644 --- a/1-kmp/1-kmp.tex +++ b/1-kmp/1-kmp.tex @@ -130,16 +130,16 @@ z~p \s{Krok($I$, $x$):} \cmt{Jeden krok automatu: jsme ve stavu~$I$, pøeèetli jsme znak~$x$.} \algo -\:Dokud $\iota[I] \neq x~\&~I \neq 0: I \leftarrow Z[I]$. -\:Pokud $\iota[I] = x$, pak $I \leftarrow I + 1$. +\:Dokud $\iota[I] \neq x~\&~I \neq 0: I \= Z[I]$. +\:Pokud $\iota[I] = x$, pak $I \= I + 1$. \:Vrátíme nový stav~$I$. \endalgo \s{Hledej($\sigma$):} \cmt{Spu¹tìní automatu na øetìzec~$\sigma$.} \algo -\:$I \leftarrow 0$. +\:$I \= 0$. \:Pro znaky $x\in\sigma$ postupnì provádíme: -\::$I \leftarrow \(I,x)$. +\::$I \= \(I,x)$. \::Pokud $I = J$, ohlásíme výskyt. \endalgo @@ -215,11 +215,11 @@ Hotov \s{Konstrukce zpìtných hran:} \algo -\:$Z[0] \leftarrow ?$, $Z[1] \leftarrow 0$. -\:$I \leftarrow 0$. +\:$Z[0] \= ?$, $Z[1] \= 0$. +\:$I \= 0$. \:Pro $K = 2, \ldots, J-1$: -\::$I \leftarrow \(I, \iota[K])$. -\::$Z[K] \leftarrow I$. +\::$I \= \(I, \iota[K])$. +\::$Z[K] \= I$. \endalgo A~jsme hotovi výsledky shrnout do následující vìty: @@ -331,52 +331,79 @@ ulo \s{Krok($I$, $x$):} \cmt{Jeden krok automatu: jsme ve stavu~$I$, pøeèetli jsme znak~$x$.} \algo -\:Dokud $\(I, x) = \emptyset~\&~I \ne \$: $I \leftarrow \(I)$. -\:Pokud $\(I, x) \ne \emptyset$: $I \leftarrow \(I,x)$. +\:Dokud $\(I, x) = \emptyset~\&~I \ne \$: $I \= \(I)$. +\:Pokud $\(I, x) \ne \emptyset$: $I \= \(I,x)$. \:Vrátíme nový stav~$I$. \endalgo \s{Hledej($\sigma$):} \cmt{Spu¹tìní automatu na øetìzec~$\sigma$.} \algo -\:$I \leftarrow \$. +\:$I \= \$. \:Pro znaky $x\in\sigma$ postupnì provádíme: -\::$I \leftarrow \(I, x)$. -\::$K \leftarrow I$. +\::$I \= \(I, x)$. +\::$K \= I$. \::Dokud $K \neq \emptyset$: \:::Je-li $\(K) \neq \emptyset$: \::::Ohlásíme $\(K)$. -\:::$K \leftarrow \(K)$. +\:::$K \= \(K)$. \endalgo \>Jak u¾ jsme nahlédli, v¹echny kroky automatu dohromady trvají $\O(S)$. Mimo to je¹tì hlásíme výskyty, co¾ trvá $\O(\)$. Zbývá ukázat, jak automat sestrojit. -\h{XXX --- Pod tímto místem nepøepsáno --- XXX} - -Zbývá nám u¾ jen konstrukce automatu. Opìt vyu¾ijeme faktu, ¾e zpìtná hrana ze stavu $\beta$ vede tam, kam by se dostal automat pøi hledání $\beta$ bez prvního písmenka. Tak¾e zase chceme nìco, jako simulovat výpoèet toho automatu na~slovech bez prvního písmenka a~doufat v~to, ¾e si vystaèíme s~tou èástí automatu, kterou jsme u¾ postavili. Tentokrát to v¹ak nemù¾eme dìlat jedno slovo po~druhém, proto¾e zpìtné hrany mohou vést køí¾em mezi jednotlivými vìtvemi automatu. Mohlo by se nám tedy stát, ¾e pøi hledání nìjakého slova potøebujeme zpìtnou hranu, která vede do~jiného slova, které jsme je¹tì nezkonstruovali. Tak¾e tento postup sel¾e. Mù¾eme v¹ak vyu¾ít toho, ¾e ka¾dá zpìtná hrana vede ve~stromu alespoò o~jednu hladinu vý¹. Mù¾eme tak strom konstruovat po~hladinách. Lze si to tedy pøedstavit tak, ¾e paralelnì spustíme vyhledávání v¹ech slov bez prvních písmenek a~v¾dycky udìláme jeden podkrok ka¾dého z~tìch hledání, co¾ nám dá zpìtné hrany z~dal¹ího patra stromu. - \s{Konstrukce automatu:} +Stejnì jako u~KMP, i zde nahlédneme, ¾e zpìtná hrana ze stavu $\beta$ vede tam, +kam by se dostal automat pøi hledání slova $\beta$ bez prvního znaku. Opìt bychom +tedy chtìli zaèít sestrojením dopøedných hran a pak spu¹tìním je¹tì nehotového +automatu doplòovat hrany zpìtné, doufajíce, ¾e si vystaèíme s~u¾ sestrojenou +èástí automatu. + +Pøi konstrukci zpìtných hran tedy chceme automatem vyhledávat v¹echny jehly +bez prvních znakù. To v¹ak nemù¾eme dìlat jednu jehlu po druhé, proto¾e zpìtné +hrany mohou vést køí¾em mezi jednotlivými vìtvemi stromu. Mohlo by se nám tedy +stát, ¾e pøi hledání nìjakého slova potøebujeme zpìtnou hranu, která vede +do~jiného slova, které jsme je¹tì nezkonstruovali. Proto tento postup sel¾e. + +Mù¾eme v¹ak vyu¾ít toho, ¾e ka¾dá zpìtná hrana vede ve~stromu alespoò o~jednu +hladinu vý¹, a strom konstruovat po~hladinách. To si lze pøedstavit tak, ¾e +paralelnì spustíme vyhledávání v¹ech slov bez prvních písmenek a~v¾dycky udìláme +jeden krok ka¾dého z~tìchto hledání, co¾ nám dá zpìtné hrany v~dal¹ím patøe stromu. + +Kdykoliv vytvoøíme zpìtnou hranu, sestrojíme také zkratkovou hranu z~tého¾ +vrcholu. Pokud vede zpìtná hrana z~$S$ do~$Q$ a $\(Q) \ne \emptyset$, +musí vést zkratka z~$S$ také do~$Q$. Pokud v~$Q$ ¾ádné slovo neskonèí, musí +zkratka z~$S$ vést do tého¾ vrcholu, jako zkratka z~$Q$. + +\s{Algoritmus: Konstrukce automatu} \algo -\:Zalo¾íme prázdný strom, $r \leftarrow$ jeho koøen. -\:Vlo¾íme do~stromu slova $\iota_1 \dots \iota_n$, nastavíme $slovo(*)$. -\:$z(r) \leftarrow \emptyset$, $out(r) \leftarrow \emptyset$. +\:Zalo¾íme prázdný strom, $R \=$ jeho koøen. +\:Vlo¾íme do~stromu slova $\iota_1 \dots \iota_n$, nastavíme $\$ ve~v¹ech stavech. +\:$\(R) \= \emptyset$, $\(R) \= \emptyset$. \:Zalo¾íme frontu $F$ a~vlo¾íme do~ní syny koøene. -\:$\forall v~\in F:~~z(v) \leftarrow r, \(v) \leftarrow \emptyset$. +\:Pro v¹echny syny~$S$ koøene: $\(S) \= R$, $\(S) \= \emptyset$. \:Dokud $F \neq \emptyset$: -\::Vybereme $u$ z~fronty $F$. -\::Pro v¹echny syny $v$ vrcholu $u$: -\:::$q \leftarrow \(z(u), \)$. -\:::$z(v) \leftarrow q$. -\:::Pokud $slovo(q) \neq \emptyset$, pak $out(v) \leftarrow q$. -\::::Jinak $out(v) \leftarrow out(q)$. -\:::Vlo¾íme $v$ do~fronty $F$. +\::Vybereme $I$ z~fronty $F$. +\::Pro v¹echny syny $S$ vrcholu $I$: +\:::$Q \= \(\(I), \hbox{písmeno na~hranì $IS$})$. +\:::$\(S) \= Q$. +\:::Pokud $\(Q) \neq \emptyset$: $\(S) \= Q$. +\:::Jinak $\(S) \= \(Q)$. +\:::Vlo¾íme $S$ do~fronty $F$. \endalgo -To, ¾e tento algoritmus zkonstruuje zpìtné hrany jak má, vyplývá z~toho, ¾e nedìláme nic jiného, ne¾ ¾e spou¹tíme výpoèty po~hladinách na~v¹echna hledaná slova bez prvního písmenka. Stejnì tak to, ¾e dobìhne v~lineárním èase, je takté¾ dùsledkem toho, ¾e efektivnì spou¹tíme v¹echny tyto výpoèty. Jen nìkdy udìláme najednou krok dvou èi více výpoètù (napøíklad |araba| a~|arbara| se poèítají na~zaèátku, dokud jsou stejné, jen jednou). Èasová slo¾itost této konstrukce je tedy men¹í nebo rovna souètu èasových slo¾itostí výpoètù nad v¹emi tìmi slovy. To u¾ ale víme, ¾e je lineární v~celkové délce tìchto slov. Konstrukce automatu tedy trvá nejvý¹e tolik, co hledání v¹ech $\iota_i$, co¾ je $\O(\sum_{i} \iota_i)$. +Jeliko¾ tento algoritmus pouze napøeskáèku hledá v¹echny jehly, musí být jeho +èasová slo¾itost shora omezena souètem slo¾itostí hledání jehel, co¾, jak u¾ +víme, je pro ka¾dou jehlu lineární s~její délkou. Dokonce mù¾e dobìhnout i +rychleji, jeliko¾ jsou-li dva ze simulovaných výpoètù v~tém¾e stavu, poèítáme +krok automatu pouze jednou (to je vidìt tøeba na spoleèném zaèátku slov |araba| +a |arbara|). + +Chování celého algoritmu shrneme do následující vìty: -\s{Vìta:} Algoritmus Aho-Corasicková najde v¹echny výskyty v~èase -$$\O\left(\sum_i~\iota_i~+~S~+~\sharp\\right).$$ +\s{Vìta:} Algoritmus Aho-Corasicková najde v¹echny výskyty v~èase +$\O\left(\sum_i J_i + S + V \right)$, kde $J_1,\ldots,J_n$ jsou délky +jednotlivých jehel, $S$ je délka sena a $V$ poèet ohlá¹ených výskytù. \h{Rabinùv-Karpùv algoritmus} -- 2.39.2