6-kmp/6-kmp.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{6}{Vyhledávání v textu}{(zapsal K. Ka¹èák, M. Klauèo, M. Vachna)}
   4
   5 \s{Úkol:} V textu najít v¹echny výskyty hledaného slova(hledaných slov).
   6
   7 \h{Hloupý algoritmus}
   8
   9 Algoritmus prochází sekvenènì textem a hledaným vzorovým slovem. Pøi neshodì se ve vzorovem slovì vrací na zaèátek a v textu pokraèuje znakem, v kterém nastala neshoda. Èasová slo¾itost je $\O(S)$, kde $S$ je délka textu. Tento algoritmus funguje pouze jen pro vzorové slová bez opakujících se znakù.
  10
  11 \s{Pøíklad:} Hledání vzorového slova $JEHLA$ v textu $VKUPCEJEJEHLA$. Ve chvíli kdy máme prefix $JE$ a na vstupu dostaneme $J$, dochází k neshodì a pokraèujeme v hledání od tohoto znaku.
  12
  13 \h{Neefektivní algoritmus}
  14
  15 Algoritmus prochází text od zaèátku a¾ do konce a pro ka¾dou pozici v textu zkontroluje, zda na této pozici nezaèíná hledané slovo. Tak pro ka¾dou pozici provede a¾ $S$ porovnání znakù, èili celkem a¾ $SJ$ porovnání. Proto je èasová slo¾itost $\O(SJ)$, kde $S$ je délka textu a $J$ délka vzorového slova.
  16
  17 \h{Chytrý algoritmus}
  18
  19 Algoritmus je vylep¹ením Neefektivního algoritmu, konkretnì zpùsobu jakým sa vrací v textu pøi neshodì mezi znakem textu a
  20 znakem vzorového slova.
  21
  22 \s{Pøíklad:} Pro vzorové slovo $AJAAJAK$ jsme na¹li v textu prefix $AJAAJA$. Oèakávame $K$.
  23 \itemize\ibull
  24 \:Kdy¾ ale dostaneme $A$ a budeme mít prefix $AJAAJAA$, vracíme se v textu za první $AJA$, tedy prefix zkrátíme na $AJAA$ a pokraèujeme v hledání.
  25 \:Kdy¾ je nasledující znak $J$ a budeme mít prefix $AJAAJAJ$, vracíme se v textu za $AJAAJ$, tedy prefix zkrátíme na $AJ$ a pokraèujeme v hledání.
  26 \:V pøípadì, ¾e dostaneme jiný znak, v textu se nevracíme a pokraèujeme dal¹ím znakem v textu.
  27 \endlist
  28
  29 \s{Definice a znaèení pro øetìzce(slová):}
  30 \itemize\ibull
  31 \s{Definice:}
  32 \itemize\ibull
  33 \:Abeceda $\sum$ je koneèná mno¾ina znakù, s kterých tvoøíme text, øetìzece, slová jako koneèné posloupnosti znakù z $\sum$. Pøíkladem extrémních abeced je lineární abeceda slo¾ená s nul a jednièek. Pøíklad s druhého konce je abecade, která má jako znaky slova èeského jazyka. V algoritmech nebudeme uva¾ovat velikost abecedy (poèet znakù).
  34 \:$\sum$* je mno¾ina v¹ech slov nad abecedou $\sum$.
  35 \endlist
  36 \s{Znaèení:}
  37 \itemize\ibull
  38 \:Slová budeme znaèit malými písmenami øecké abecedy $\alpha$,$\beta$... a znaky velkými písmenami latinky $A$,$B$... .
  39 \:Prázdné slovo znaèíme písmenem $\epsilon$.
  40 \:Délka slova $\vert \alpha  \vert$ pro $\alpha \in \sum*$ je poèet znakù.
  41 \:Zøetìzení $\alpha\beta$ vznikne zapsáním slov $\alpha$ a $\beta$ za sebe. Platí $\alpha\epsilon=\epsilon\alpha=\alpha$, $\vert \alpha\beta  \vert=\vert \alpha \vert+\vert \beta \vert$.
  42 \:$\alpha[i]$ je $i$-té písmeno slova $\alpha$, indexuje se od $0$.
  43 \:$\alpha[i:j]$ je podslovo tvoøené písmenami $\alpha[i]$,...,$\alpha[j-1]$. Pøíklady: $\alpha[i:i+1]=\alpha[i]$, $\alpha[i:i]=\epsilon$, $\alpha[:]=\alpha$.
  44 \:$\alpha[:j]$ je prefix obsahující prvních $j$ znakù slova $\alpha$.
  45 \:$\alpha[i:]$ je suffix obsahující znaky slova $\alpha$ poèínaje $i$-tým znakem.
  46 \:Ka¾dé slovo je prefixem i suffixem sebe sama, takovému prefixu/suffixu øíkáme vlastní. V¹em ostatním nevlastní.
  47 \:Prázdné slovo je podslovem, prefixem i suffixem ka¾dého slova vèetnì prázdného slova.
  48 \endlist
  49 \endlist
  50
  51 \s{Problém:}
  52 \itemize\ibull
  53 \s{IN:}
  54 \itemize\ibull
  55 \:$\iota$ slovo (jehla) délky $J=\vert \iota \vert$
  56 \:$\sigma$ text (seno) délky $S=\vert \sigma \vert$
  57 \endlist
  58 \s{OUT:}
  59 \itemize\ibull
  60 \:$\left\{ i\vert \sigma[i:i+J]=\iota \right\}$
  61 \endlist
  62 \endlist
  63
  64 \h{Vyhledávací automat (Knuth, Morris, Pratt)}
  65 Vyhledávací automat bude vlastnì graf jeho¾ vrcholy reprezentují stavy. Jména stavù budou v¹echny prefixy slova $\iota$. Poèáteèný stav je prázdny slovo $\epsilon$ a koneèný je samotná $\iota$. Dopøední hrany grafu budú popisovat pøechod mezi stavy v smysle zvìt¹ení délky jména stavu (dopøedná funkce $d(\alpha , X)$), tedy ka¾dá taková hrana bude oznaèena písmenem $X$  a bude popisovat dané zvìt¹ení délky jména stavu, tedy $\alpha \rightarrow \alpha X$. Zpìtné hrany grafu budú popisovat pøechod ( zpìtná funkce $z(\alpha)$) mezi stavem $\alpha$ a nejdel¹ím vlastním suffixem $\alpha$, který je prefixem $\iota$, kdy¾ nastane neshoda.
  66
  67 \figure{vautomat.eps}{Vyhledávací automat}{5.5in}
  68
  69 \s{Vyhledávaní:}
  70 \algo
  71 \:$\alpha \leftarrow \epsilon$.
  72 \:pro $C\in\sigma$ postupnì:
  73 \:$\indent$dokud $\neg \exists d(\alpha , C) \wedge \alpha\neq\epsilon : \alpha \leftarrow z(\alpha)$
  74 \:$\indent$dokud $\exists d(\alpha , C) \Rightarrow \alpha \leftarrow d(\alpha , C)$
  75 \:$\indent$kdy¾ $\alpha = \iota \Rightarrow$ hledané slovo je v textu
  76 \endalgo
  77
  78 \s{Alternatíva:}
  79 \algo
  80 \:$k \leftarrow 0$.
  81 \:pro $C\in\sigma$ postupnì:
  82 \:$\indent$dokud $C\neq \iota[k] \wedge k>0: k \leftarrow z(k)$
  83 \:$\indent$dokud $C=\iota[k] \Rightarrow k++$
  84 \:$\indent$kdy¾ $k = J \Rightarrow$ hledané slovo je v textu
  85 \endalgo
  86
  87 \s{Invariant:} Stav po pøeètení vstupu $\beta$. $\alpha(\beta)$ $=$ nejdel¹í suffix $\beta$, který je prefixem $\iota$.
  88 S invariantu vyplýva korektnost vyhledávací èásti KMP algoritmu.
  89
  90 \proof
  91 Dùkaz indukcí. Na zaèátku pro prázdny naètený vstup platí invariant, tedy prázdny suffix $\beta$ je prefixem $\iota$. V kroku $n$ máme naètený vstup $\beta$ a k nìmu naèteme znak $C$. Jestli si odmyslíme $C$, tedy kdy¾ si od jména stavu odmyslíme posledné písmenko, dostaneme znovu jméno stavu. Tak stav, který pasuje na konec vstupu bez toho $C$ je stav, který pasuje na konec pùvodního vstupu, toho o jeden znak krat¹ího. Tím pádem to musí být nìco, co je maximálnì tak dlouhé jako pùvodní stav, u kterého jsme byli, proto¾e to byl nejdel¹í, který pasoval. Staèí procházet postupnì v¹echny stavy, které pasují na konec toho vstupu od nejdel¹ího k nejkrat¹ímu a vzít první, který se dá roz¹íøit o $C$. To je pøesnì to, co algoritmus dìlá. Preto¾e zpìtná funkce øekne nejbli¾¹í krat¹í jméné stavu. Tak¾e algoritmus iteruje pøes stavy, které tam pasují, a¾ najde jeden, který se dá roz¹íøit o $C$ a jeliko¾ iteroval od ty nejdel¹í, tak to je logicky ten nejdel¹í, který tam pasuje.
  92 \qed
  93
  94 \s{Lemma:} Vyhledávaní dobìhne v èase $\O(S)$.
  95
  96 \proof
  97 Pro ka¾dý znak vstupního textu mohou nastat dva pøípady. Znak roz¹iruje aktuální prefix, nebo musíme pou¾ít zpìtnou funkci(ypìtnou hranu). Roz¹irování trvá konstantnì mnoho èasu, zatímco zpìtná funkce mu¾e být pro jeden znak volána a¾ $J$-krát. Pøi ka¾dém volání klesne délka aktuálního stavu minimálne o jedna a zároven platí, ¾e kdykoliv stav prodlu¾ujeme, roste právì o jeden znak. Proto v¹ech zkrácení dohromady mu¾e být nejvý¹e tolik, kolik bylo v¹ech prodlou¾ení, t.j. kolik jsme pøeèetli znaku textu. Celkem je tedy poèet krokù lineární vzhledem k délce textu.
  98 \qed
  99
 100 \s{Konstrukce zpìtné funkce:}
 101 \algo
 102 \:sestrojíme dopøedné hrany
 103 \:$z( \epsilon ) \leftarrow 0$, $z( \iota [0]) \leftarrow \epsilon $
 104 \:$\indent$ $\alpha \leftarrow \epsilon$
 105 \:pro $i = 1$ do $J$
 106 \:$\indent$$\alpha \leftarrow krok( \alpha , \iota [i])$
 107 \:$\indent$$z( \iota [0:i+1]) \leftarrow \alpha$
 108 \endalgo
 109
 110 \s{Vysvìtlení:} V¹imnìte si, ¾e $z(i)$ je pøesnì stav, do nej¾ se dostaneme pøi spu¹tìní na¹eho vyhledávacího algoritmu na øetìzec $\iota [2:i]$, èili na $i$-tý prefix bez prvního písmenka. Proè to tak je? Zpìtná funkce øíká, jaký je nejdel¹í vlastní suffix daného stavu, který je také stavem, zatímco $\alpha$ oznaèuje nejdel¹í suffix textu, který je stavem. Tyto dvì vìci se pøeci li¹í jen v tom, ¾e ta druhá pøipou¹tí i nevlastní suffixy, a právì tomu zabráníme odstranìním prvního znaku. Tak¾e $z()$ získáme tak, ¾e spustíme vyhledávání na èást samotného slova $\iota$. Jen¾e k vyhledávání zase potøebujeme zpìtnou funkci $z$. Proto budeme zpìtnou funkci vytváøet postupne od nejkrat¹ích prefixu. Zøejmì $z(1) = \epsilon$. Pokud ji¾ máme $z(i)$, pak výpoèet $z(i+1)$ odpovídá spu¹tení automatu na slovo délky i a pritom budeme zpìtnou funkci potøebovat jen pro stavy délky $i$ nebo men¹í, pro které ji ji¾ máme hotovou.
 111
 112 Navíc nemusíme pro jednotlivé prefixy spou¹tìt výpoèet v¾dy znovu od zaèátku, proto¾e $(i+1)$-ní prefix
 113 je prodlou¾ením $i$-tého prefixu o jeden znak. Staèí tedy spustit algoritmus na celý øetìzec $\iota[1:J]$ a sledovat, jakými stavy bude procházet. A to budou pøesnì hodnoty zpìtné funkce. Vytvoøení zpìtné funkce se tak nakonec zredukovalo na jediné vyhledávání v textu o délce $J-1$, a proto pobe¾í v case $\O(J)$. Èasová slo¾itost celého algoritmu tedy bude $\O(S+J)$.
 114
 115 \h{Algoritmus Rabin \& Karp}
 116 Tenhle algoritmus funguje tak, ¾e porovnává hash hledaného øetìzce s hashem aktuálního podøetìzce v textu a aktuální podøetìzec porovná se vzorkem pouze v pøípadì, kdy¾ mají shodný hash. Kdy¾ si zvolíme tu správnou hashovací funkci, budeme moci vypoèítat hash následujíciho podøetìzce na základe hashe toho aktuálního. Jako hashovací funkci $h: \sum^J \rightarrow Z$ pou¾ijeme následující: $h(x_{0},...,x_{j-1}) = ( \sum_{i=1}^J x_{i}.p^{J-i})$ $mod$ $N$, kde $N$ je velikost prostoru do kterého hashujeme. Jak zjistíme hash následujícího podøetìzce?
 117 \itemize\ibull
 118 \:$h = x_{0}.p^{J} + x_{1}.p^{J-1} + ... + x_{J-1}.p^{1}$
 119 \:$h1 = x_{1}.p^{J} + x_{2}.p^{J-1} + ...       + x_{J}.p^{1}$
 120 \:$h1 = (h - x_{0}.p^{J}).p + x_{J}.p^{1}$
 121 \endlist
 122 Èasová slo¾itost je v nejlep¹ím pøípadì lineární vzhledem k délce textu, zatímco nejhor¹í pøípad mú¾e trvat a¾ $\O(JS)$.
 123
 124 \bye