X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=1-kmp%2F1-kmp.tex;h=87c5c93bd6c22ab1e48ae493e60f92fb82eb7f37;hb=9313f25559824002b787897ee3f09a70082730e6;hp=a90d6437bc12a05ccb624fcf5ba549d19bce1e51;hpb=963b0128e558f45239820e76b86ddc383f113933;p=ads2.git diff --git a/1-kmp/1-kmp.tex b/1-kmp/1-kmp.tex index a90d643..87c5c93 100644 --- a/1-kmp/1-kmp.tex +++ b/1-kmp/1-kmp.tex @@ -128,172 +128,231 @@ bude nedefinovan Kdybychom takový automat mìli, mohli bychom pomocí nìj inkrementální algoritmus z~pøedchozí sekce popsat následovnì: -\s{Hledej($\sigma$):} +\s{Krok($I$, $x$):} \cmt{Jeden krok automatu: jsme ve stavu~$I$, pøeèetli jsme znak~$x$.} \algo -\:$S \leftarrow 0$. +\:Dokud $\iota[I] \neq x~\&~I \neq 0: I \leftarrow Z[I]$. +\:Pokud $\iota[I] = x$, pak $I \leftarrow 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$. \:Pro znaky $x\in\sigma$ postupnì provádíme: -\:$\indent$Dokud $\iota[S] \neq x~\&~S \neq 0: S \leftarrow Z[S]$. -\:$\indent$Pokud $\iota[S] = x$, pak $S \leftarrow S + 1$. -\:$\indent$Pokud $S = J$, ohlásíme výskyt. +\::$I \leftarrow \(I,x)$. +\::Pokud $I = J$, ohlásíme výskyt. \endalgo -\s{Invariant:} Stav algoritmu~$S$ v~ka¾dém okam¾iku øíká, jaký nejdel¹í +\s{Invariant:} Stav algoritmu~$I$ v~ka¾dém okam¾iku øíká, jaký nejdel¹í prefix jehly je suffixem zatím pøeètené èásti sena. (To u¾ víme z~úvah o~inkrementálním algoritmu.) -Z~invariantu ihned plyne, ¾e algoritmus správnì ohlásí v¹echny výskyty. -Jen musíme opravit drobnou chybu -- algoritmus se toti¾ obèas -zeptá na~dopøednou hranu z~posledního stavu. Pokud jsme právì ohlásili výskyt -(jsme tedy v~posledním stavu) a~pøijde nìjaký dal¹í znak, algoritmus se ptá, -zda je roven tomu, co je na~dopøedné hranì z~posledního stavu. Ta ale -neexistuje. Jednodu¹e to napravíme tak, ¾e pøidáme fiktivní hranu, -na~které se vyskytuje nìjaké \uv{nepísmenko} -- nìco, co se nerovná ¾ádnému -jinému písmenku. Zajistíme tak, ¾e se po~této hranì nikdy nevydáme. -Dodefinujeme tedy $\iota[J]$ odli¹nì od~v¹ech znakù.\foot{V jazyce C se toto -dodefinování provede vlastnì zadarmo, nebo» ka¾dý øetìzec je v~nìm ukonèen -znakem s~kódem nula, který se ve~vstupu nevyskytne\dots Algoritmus bude tedy -fungovat i~bez tohoto dodefinování. V jiných jazycích je ale tøeba na~nìj -nezapomenout!} - -\h{XXX dál následuje pùvodní, je¹tì neupravený text XXX} +\s{Dùsledek:} Algoritmus ohlásí v¹echny výskyty. Pokud jsme toti¾ právì +pøeèetli poslední znak nìjakého výskytu, je celá jehla suffixem zatím +pøeètené èásti sena, tak¾e se musíme nacházet v~posledním stavu. -Pojïme si rozmyslet, ¾e z~tohoto invariantu ihned plyne, ¾e algoritmus najde to, co má. Kdykoli toti¾ ohlásí nìjaký výskyt, tak tam tento výskyt opravdu je. Kdykoli pak má nìjaký výskyt ohlásit, tak se v~této situaci jako suffix toho právì pøeèteného textu vyskytuje hledané slovo, pøièem¾ hledané slovo je urèitì stav a~zároveò nejdel¹í ze v¹ech existujících stavù. Tak¾e invariant opravdu øíká, ¾e jsme právì v~koncovém stavu a~algoritmus nám tedy ohlásí výskyt. +Jen musíme opravit drobnou chybu -- tìsnì poté, co ohlásíme výskyt, se +algoritmus zeptá na~dopøednou hranu z~posledního stavu. Ta ale +neexistuje. Napravíme to jednodu¹e: pøidáme fiktivní dopøednou hranu, +na~ní¾ je napsán znak odli¹ný od~v¹ech skuteèných znakù. Tím zajistíme, +¾e se po této hranì nikdy nevydáme. Staèí tedy vhodnì dodefinovat $\iota[i]$.% +\foot{V jazyce C mù¾eme zneu¾ít toho, ¾e ka¾dý øetìzec je ukonèen znakem +s~nulovým kódem.} -\s{Lemma:} Funkce {\I Hledej} bì¾í v~èase $\O(S)$. +\s{Lemma:} Funkce \ bì¾í v~èase $\O(S)$. \proof -Funkce {\I Hledej} chodí po~dopøedných a~zpìtných hranách. Dopøedných hran projdeme urèitì maximálnì tolik, kolik je délka sena. Pro ka¾dý znak pøeètený ze sena toti¾ jdeme nejvý¹e jednou po~dopøedné hranì. Se zpìtnými hranami se to má tak, ¾e na~jeden pøeètený znak z~textu se mù¾eme po~zpìtné hranì vracet maximálnì $J$-krát. Z~tohoto by nám v¹ak vy¹la slo¾itost $\O(JS)$, èím¾ bychom si nepomohli. Zachrání nás ale pøímoèarý potenciál. Uvìdomme si, ¾e chùze po~dopøedné hranì zvý¹í $I$ o~jedna a~chùze po~zpìtné hranì $I$ sní¾í alespoò o~jedna. Vzhledem k~tomu, ¾e $I$ není nikdy záporné a~na~zaèátku je nulové, zjistíme, ¾e krokù zpìt mù¾e být maximálnì tolik, kolik krokù dopøedu. Èasová slo¾itost hledání je tedy lineární vzhledem k~délce sena. \qed - -Nyní nám zbývá na~první pohled malièkost -- toti¾ zkonstruovat automat. Zkonstruovat dopøedné hrany zvládneme zjevnì snadno, jsou toti¾ explicitnì popsané hledaným slovem. Tì¾¹í u¾ to bude pro hrany zpìtné. Vyu¾ijeme k~tomu následující pozorování: +Výpoèet funkce mù¾eme rozdìlit na prùchody dopøednými a zpìtnými hranami. +S~dopøednými je to snadné -- za~ka¾dý z~$S$ znakù sena projdeme po nejvý¹e +jedné dopøedné hranì. To o~zpìtných hranách neplatí, ale pomù¾e nám, ¾e ka¾dá +dopøedná hrana vede o~právì~1 stav doprava a ka¾dá zpìtná o~aspoò~1 stav +doleva. Proto je v¹ech prùchodù po~zpìtných hranách nejvý¹e tolik, kolik +jsme pro¹li dopøedných hran, tak¾e také nejvý¹e~$S$. +\qed -\s{Pozorování:} -Pøedstavme si, ¾e automat u¾ máme hotový a~tím, ¾e budeme sledovat jeho chování, chceme zjistit, jak v~nìm vedou zpìtné hrany. -Vezmìme si nìjaký stav~$\beta$. To, kam z~nìj vede zpìtná hrana zjistíme tak, ¾e spustíme automat na~øetìzec $\beta$~bez prvního písmenka a~stav, ve~kterém se automat zastaví, je pøesnì ten, kam má vést i~zpìtná hrana z~$\beta$. Jinými slovy víme, ¾e $z(\beta) = \alpha (\beta[1:])$. -Proè takováto vìc funguje? V¹imìme si, ¾e definice $z$ a~to, co nám o~$\alpha$ øíká invariant, je témìø toto¾né -- $z(\beta)$ je nejdel¹í vlastní suffix $\beta$, který je stavem, $\alpha(\beta)$ je nejdel¹í suffix $\beta$, který je stavem. Jediná odli¹nost je v~tom, ¾e definice $z$ narozdíl od~definice $\alpha$ zakazuje nevlastní suffixy. Jak nyní vylouèit suffix $\beta$, který by byl roven $\beta$ samotné? Zkrátíme $\beta$ o~první znak. Tím pádem v¹echny suffixy $\beta$ bez prvního znaku jsou stejné jako v¹echny vlastní suffixy $\beta$. - -K èemu je toto pozorování dobré? Rozmysleme si, ¾e pomocí nìj u¾ doká¾eme zkonstruovat zpìtné hrany. Není to ale trochu divné, kdy¾ pøi simulování automatu na~øetìzec bez prvního znaku u¾ zpìtné hrany potøebujeme? Není. Za chvíli zjistíme, ¾e takto mù¾eme zji¹»ovat zpìtné hrany postupnì -- a~to tak, ¾e pou¾íváme v¾dy jenom ty, které jsme u¾ sestrojili. - -Takovémuhle pøístupu, kdy pøi konstruování chtìného u¾ pou¾íváme to, co chceme sestrojit, ale pouze ten kousek, který ji¾ máme hotový, se v~angliètinì øíká {\I bootstrapping}\foot{Z~tohoto slova vzniklo i~{\I bootování} poèítaèù, kdy operaèní systém v~podstatì zavádí sám sebe. Bootstrap znamená èesky ¹truple -- tedy oèko na~konci boty, které slou¾í k~usnadnìní nazouvání. A~jak souvisí ¹truple s~algoritmem? To se zase musíme vrátit k~pøíbìhùm o~baronu Prá¹ilovi, mezi nimi¾ je i~ten, ve~kterém baron Prá¹il vypráví o~tom, jak sám sebe vytáhl z~ba¾iny za ¹truple. Stejnì tak i~my budeme algoritmus konstruovat tím, ¾e se budeme sami vytahovat za ¹truple, tedy bootstrappovat.}. -V¹imnìme si, ¾e pøi výpoètu se vstupem $\beta$ projde automat jenom prvních $\vert \beta \vert$ stavù. Automat se evidentnì nemù¾e dostat dál, proto¾e na~ka¾dý krok dopøedu (doprava) spotøebuje písmenko $\beta$. Tak¾e krokù doprava je maximálnì tolik, kolik je $\vert \beta \vert$. Jinými slovy kdybychom ji¾ mìli zkonstruované zpìtné hrany pro prvních $\vert \beta \vert$ stavù (tedy $0 \dots \vert \beta \vert - 1$), tak pøi tomto výpoètu, který potøebujeme na~zkonstruování zpìtné hrany z~$\beta$, je¹tì tuto zpìtnou hranu nemù¾eme potøebovat. Vystaèíme si s~tìmi, které ji¾ máme zkonstruované. - -Nabízí se tedy zaèít zpìtnou hranou z~prvního znaku (která vede evidentnì do~$\varepsilon$), pak postupnì brát dal¹í stavy a~pro ka¾dý z~nich si spoèítat, kdy spustíme automat na~jméno stavu bez prvního znaku a~tím získáme dal¹í zpìtnou hranu. Toto funguje, ale je to kvadratické \dots. Máme toti¾ $J$ stavù a~pro ka¾dý z~nich nám automat bì¾í v~èase a¾ lineárním s~$J$. Jak z~toho ven? - -Z~prvního stavu povede zpìtná funkce do~$\varepsilon$. Pro dal¹í stavy chceme spoèítat zpìtnou funkci. Z~druhého stavu $\iota[0:2]$ tedy automat spustíme na~$\iota[1:2]$, dále pak na~$\iota[1:3]$, $\iota[1:4]$, atd. Ty øetìzce, pro které potøebujeme spo¹tìt automat, abychom dostali zpìtné hrany, jsou tedy ve~skuteènosti takové, ¾e ka¾dý dal¹í dostaneme roz¹íøením pøedchozího o~jeden znak. To jsou ale pøesnì ty stavy, kterými projde automat pøi zpracovávání øetìzce $\iota$ od~prvního znaku dál. Jedním prùchodem automatu nad jehlou bez prvního písmenka se tím pádem rovnou dozvíme v¹echny údaje, které potøebujeme. -Z~pøedchozího pozorování plyne, ¾e nikdy nebudeme potøebovat zpìtnou hranu, kterou jsme je¹tì nezkonstruovali a~jeliko¾ víme, ¾e jedno prohledání trvá lineárnì s~délkou toho, v~èem hledáme, tak toto celé pobì¾í v~lineárním èase. Dostaneme tedy následující algoritmus: - -\s{Konstrukce zpìtné funkce:} +\s{Konstrukce automatu:} +Algoritmus je tedy lineární, ale potøebuje, aby mu nìkdo zkonstruoval +automat. Dopøedné hrany vytvoøíme snadno, ale jak si poøídit ty zpìtné? + +Podnikneme my¹lenkový pokus: Pøedstavme si, ¾e automat u¾ máme hotový, ale nevidíme, +jak vypadá uvnitø. Chtìli bychom zjistit, jak v~nìm vedou zpìtné hrany, ov¹em jediné, +co umíme, je spustit automat na nìjaký øetìzec a zjistit, v~jakém stavu skonèil. + +Tvrdíme, ¾e pro zji¹tìní zpìtné hrany ze~stavu~$\alpha$ staèí automatu pøedlo¾it +øetìzec $\alpha[1:{}]$. Definice zpìtné funkce je toti¾ nápadnì podobná invariantu, +který jsme o~funkci \ dokázali. Obojí hovoøí o~nejdel¹ím suffixu daného +slova, který je prefixem jehly. Jediný rozdíl je v~tom, ¾e v~pøípadì zpìtné funkce +uva¾ujeme pouze vlastní suffixy, zatímco invariant pøipou¹tí i nevlastní. To ov¹em +snadno vyøe¹íme \uv{ukousnutím} prvního znaku jména stavu. + +Pokud chceme objevit v¹echny zpìtné hrany, staèí automat spou¹tìt postupnì +na øetìzce $\iota[1:1]$, $\iota[1:2]$, $\iota[1:3]$, atd. Jeliko¾ funkce \ +je lineární, stálo by nás to dohromady $\O(J^2)$. Pokud si ale v¹imneme, ¾e ka¾dý +ze~zmínìných øetìzcù je prefixem toho následujícího, je jasné, ¾e staèí spustit +automat jen jednou na øetìzec $\iota[1:{}]$ a jen zaznamenávat, kterými stavy +jsme pro¹li. + +To je zajímavé pozorování, øeknete si, ale jak nám pomù¾e ke~konstrukci automatu, +kdy¾ samo u¾ hotový automat potøebuje? Pomù¾e pìkný trik: pokud hledáme zpìtnou +hranu z~$I$-tého stavu, spou¹tíme automat na slovo délky~$I-1$, tak¾e se mù¾eme +dostat pouze do prvních~$I-1$ stavù a vùbec nám nevadí, ¾e v~tom $I$-tém je¹tì +není zpìtná hrana hotova.% +\foot{Konstruovat nìjaký objekt pomocí tého¾ objektu je osvìdèený postup, který +si u¾ vyslou¾il i svùj vlastní název. V~angliètinì se mu øíká {\I bootstrapping} +a z~tohoto názvu vzniklo i bootování poèítaèù, proto¾e pøi nìm operaèní systém +vlastnì do pamìti zavádí sám sebe. Kde se toto slovo vzalo? Bootstrap znamená èesky +{\I ¹truple} -- to je takové to oèko na patì boty, které usnadòuje nazouvání. +A~v~jednom z~pøíbìhù o~baronu Prá¹ilovi sly¹íme barona vyprávìt, jak se uvíznuv +v~ba¾inì zachránil tím, ¾e se vytáhl za ¹truple. Krásný popis bootování, není-li¾ +pravda?} + +Konstrukce automatu tedy bude vypadat tak, ¾e nejdøíve sestrojíme pouze dopøedné +hrany, pak rozpracovaný automat spustíme na øetìzec $\iota[1:{}]$ a podle toho, +jakými stavy prochází, doplòujeme zpìtné hrany. A~jeliko¾ vyhledávání je lineární, +celá konstrukce trvá $\O(J)$. + +Hotový algoritmus mù¾eme zapsat následovnì: + +\s{Konstrukce zpìtných hran:} \algo \:$Z[0] \leftarrow ?$, $Z[1] \leftarrow 0$. \:$I \leftarrow 0$. -\:Pro $k = 2 \dots J$: -\::$I \leftarrow \( I , \iota [k])$. -\::$Z[k] \leftarrow I$. +\:Pro $K = 2, \ldots, J-1$: +\::$I \leftarrow \(I, \iota[K])$. +\::$Z[K] \leftarrow I$. \endalgo -Zaèínáme tím, ¾e nastavíme zpìtnou hranu z~prvních dvou stavù, pøièem¾ $z[0]$ je nedefinované, proto¾e tuto zpìtnou hranu nikdy nepou¾íváme. Dále postupnì simulujeme výpoèet automatu nad slovem bez prvního znaku a~po ka¾dém kroku se dozvíme novou zpìtnou hranu. {\I Krokem} automatu pak není nic jiného ne¾ vnitøek (3. a~4. bod) na¹í hledací procedury. To, kam jsme se dostali, pak zaznamenáme jako zpìtnou funkci z~$k$. -Èili pou¹tíme automat na~jehlu bez prvního písmenka, provedeme v¾dy jeden krok automatu (pøes dal¹í písmenko jehly) a~zapamatujeme si, jakou zpìtnou funkci jsme zrovna dostali. Díky pozorováním navíc víme, ¾e zpìtné hrany konstruujeme správnì, nikdy nepou¾ijeme zpìtnou hranu, kterou jsme je¹tì nesestrojili a~víme i~to, ¾e celou konstrukci zvládneme v~lineárním èase s~délkou jehly. +A~jsme hotovi výsledky shrnout do následující vìty: \s{Vìta:} Algoritmus KMP najde v¹echny výskyty v~èase $O(J+S)$. \proof -Lineární èas s~délkou jehly potøebujeme na~postavení automatu, lineární èas s~délkou sena pak potøebujeme na~samotné vyhledání. - -\h{Rabinùv-Karpùv algoritmus} - -Nyní si uká¾eme je¹tì jeden algoritmus na~hledání jedné jehly, který nebude mít v~nejhor¹ím pøípadì lineární slo¾itost, ale bude ji mít prùmìrnì. Bude daleko jednodu¹¹í a~uká¾e se, ¾e je v~praxi daleko rychlej¹í. Bude to algoritmus zalo¾ený na~hashování. - - -Pøedstavme si, ¾e máme seno délky $S$ a~jehlu délky $J$, a~vezmìme si nìjakou hashovací funkci, které dáme na~vstup $J$-tici znakù (tedy podslova dlouhá jako jehla). Tato hashovací funkce nám je pak zobrazí do~mno¾iny $\{0,\ldots,N-1\}$ pro nìjaké dost velké~$N$. Jak nám toto pomù¾e pøi hledání jehly? Vezmeme si libovolné \uv{okénko} délky $J$ a~ne¾ budeme zji¹»ovat, zda se v~nìm jehla vyskytuje, tak si spoèítáme hashovací funkci a~porovnáme ji s~hashem jehly. Èili ptáme se, jestli je hash ze sena od~nìjaké pozice $I$ do~pozice $I+J$ roven hashi jehly -- formálnì: $h(\sigma [I: I+J ]) = h(\iota)$. Teprve tehdy, kdy¾ zjistíme, ¾e se hodnota hashovací fce shoduje, zaèneme doopravdy porovnávat øetìzce. - -Není to ale nìjaká hloupost? Mù¾e nám vùbec takováto konstrukce pomoci? Není to tak, ¾e na~spoèítání hashovací funkce z~$J$ znakù, potøebujeme tìch $J$ znakù pøeèíst, co¾ je stejnì rychlé, jako rovnou øetìzce porovnávat? Pou¾ijeme trik, který bude spoèívat v~tom, ¾e si zvolíme ¹ikovnou hashovací funkci. Udìláme to tak, abychom ji mohli pøi posunutí \uv {okénka} o~jeden znak doprava v~konstantním èase pøepoèítat. Chceme umìt z~$h(x_1 \dots x_j)$ spoèítat $h(x_2 \dots x_{j+1})$. -Na~zaèátku si tedy spoèítáme hash jehly a~první $J$-tice znakù sena. Pak ji¾ jenom posouváme \uv {okénko} o~jedna, pøepoèítáme hashovací funkci a~kdy¾ se shoduje s~hashem jehly, tak porovnáme. Budeme pøitom vìøit tomu, ¾e pokud se tam jehla nevyskytuje, pak máme hashovací funkci natolik rovnomìrnou, ¾e pravdìpodobnost toho, ¾e se pøesto strefíme do~hashe jehly, je $1/N$. Jinými slovy jenom v~jednom z~øádovì $N$ pøípadù budeme porovnávat fale¹nì -- tedy provedeme porovnání a~vyjde nám, ¾e výsledek je neshoda. V~prùmìrném pøípadì tedy mù¾eme stlaèit slo¾itost a¾ témìø k~lineární. - -Podívejme se teï na~prùmìrnou èasovou slo¾itost. Budeme urèitì potøebovat èas na~projití jehly a~sena. Navíc strávíme nìjaký èas nad fale¹nými porovnáními, kterých bude v~prùmìru na~ka¾dý $N$-tý znak sena jedno porovnání s~jehlou -- tedy $SJ / N$, pøièem¾ $N$ mù¾eme zvolit dost velké na~to, abychom tento èlen dostali pod nìjakou rozumnou konstantu... Nakonec budeme potøebovat jedno porovnání na~ka¾dý opravdový výskyt, èemu¾ se nevyhneme. Pøipoèteme tedy je¹tì $J \cdot$ {\I $\sharp$výskytù}. Dostáváme tedy: $ \O(J+S+SJ/N+J \cdot$ {\I $\sharp$výskytù}). - -Zbývá malièkost -- toti¾ kde vzít hashovací funkci, která toto v¹e splòuje. Jednu si uká¾eme. Bude to vlastnì takový hezký polynom: -$$h(x_1 \dots x_j) := \left(\sum_{I=1}^{J} x_I \cdot p^{J-I}\right) \bmod N.$$ -Jinak zapsáno se tedy jedná o: -$$(x_1 \cdot p^{J-1} + x_2 \cdot p^{J-2} + \dots + x_J \cdot p^0 ) \bmod N.$$ -Po posunutí okénka o~jedna chceme dostat: -$$(x_2 \cdot p^{J-1} + x_3 \cdot p^{J-2} + \dots + x_J \cdot p^1 + x_{J+1} \cdot p^0 ) \bmod N.$$ -Kdy¾ se ale podíváme na~èleny tìchto dvou polynomù, zjistíme, ¾e se li¹í jen o~málo. Pùvodní polynom staèí pøenásobit~$p$, odeèíst první èlen s~$x_1$ a~naopak pøièíst chybìjící èlen $x_{J+1}$. Dostáváme tedy: -$$h(x_2 \dots x_{J+1}) = (p \cdot h(x_1 \dots x_J) - x_1 \cdot p^J + x_{J+1}) \bmod N.$$ -Pøepoèítání hashovací funkce tedy není nic jiného, ne¾ pøenásobení té minulé~$p$, odeètení nìjakého násobku toho znaku, který vypadl z~okénka, a~pøiètení toho znaku, o~který se okénko posunulo. Pokud tedy máme k~dispozici aritmetické operace v~konstantním èase, zvládneme konstantnì pøepoèítávat i~hashovací funkci. - -Tato hashovací funkce se dokonce nejen hezky poèítá, ale dokonce se i~opravdu \uv{hezky} chová (tedy \uv{rozumnì} náhodnì), pokud zvolíme vhodné~$p$. To bychom mìli zvolit tak, aby bylo rozhodnì nesoudìlné s~$N$ -- tedy $\(p, N) = 1$. Aby se nám navíc dobøe projevilo modulo obsa¾ené v~hashovací funkci, mìlo by být~$p$ relativnì velké (lze dopoèítat, ¾e optimum je mezi $2/3 \cdot N$ a~$3/4 \cdot N$). S~takto zvoleným~$p$ se tato hashovací funkce chová velmi pøíznivì a~v~praxi má celý algoritmus takøka lineární èasovou slo¾itost (prùmìrnou). - -\h{Hledání více øetìzcù najednou} -Nyní si zahrajeme tuté¾ hru, ov¹em v~trochu slo¾itìj¹ích kulisách. Podíváme se na~algoritmus, který si poradí i~s více ne¾ jednou jehlou. -Mìjme tedy jehly $\iota_1 \dots \iota_n$, a~jejich délky $J_i = \vert \iota_i \vert $. Dále budeme potøebovat seno $\sigma$ délky $S=\vert \sigma \vert$. - -Pøedtím, ne¾ se pustíme do~vlastního vyhledávacího algoritmu, mo¾ná bychom si mìli ujasnit, co vlastnì bude jeho výstupem. U problému hledání jedné jehly to bylo jasné -- byla to nìjaká mno¾ina pozic v~senì, na~kterých zaèínaly výskyty jehly. Jak tomu ale bude zde? Sice bychom také mohli vrátit pouze mno¾inu pozic, ale my budeme chtít malièko víc. Budeme toti¾ chtít vìdìt i~to, která jehla se na~které pozici vyskytuje. Výstup tedy bude vypadat následovnì: $V = \{(i,j)~\vert~\sigma[i:i+J_j]= \iota_j \}$. - -Zde se v¹ak skrývá jedna drobná zrada. Budeme se asi muset vzdát nadìje, ¾e najdeme algoritmus, jeho¾ slo¾itost je lineární v~celkové délce v¹ech jehel a~sena. Výstup toti¾ mù¾e být del¹í ne¾ lineární. Mù¾e se nám klidnì stát, ¾e na~jedné pozici v~senì se bude vyskytovat více rùzných jehel -- pokud bude jedna jehla prefixem jiné (co¾ jsme nikde nezakázali), tak máme povinnost ohlásit oba výskyty. Vzhledem k~tomu budeme hledat takový algoritmus, který bude lineární v~délce vstupu plus délce výstupu, co¾ je evidentnì to nejlep¹í, èeho mù¾eme dosáhnout. - -Algoritmus, který si nyní uká¾eme, vymysleli nìkdy v~roce 1975 pan Aho a~paní Corasicková. Bude to takové zobecnìní Knuthova-Morrisova-Prattova algoritmu. - -\h{Algoritmus Aho-Corasicková} - -Opìt se budeme sna¾it sestrojit nìjaký vyhledávací automat a~nìjakým zpùsobem tento automat pou¾ít k~procházení sena. Podívejme se nejprve na~pøíklad. Budeme chtít vyhledávat tato slova: |ara|, |bar|, |arab|, |baraba|, |barbara|. Mìjme tedy tìchto pìt jehel a~rozmysleme si, jak by vypadal nìjaký automat, který by tato slova umìl zatím jenom rozpoznávat. Pro jedno slovo automat vypadal jako cesta, zde u¾ to bude strom. (viz obrázek). - -\figure{ara_strom_blank.eps}{Vyhledávací automat -- strom.}{1in} - -Navíc budeme muset do~automatu zanést, kde nìjaké slovo konèí. V~pùvodním automatu pro jedno slovo to bylo jednoduché -- ono jedno jediné slovo odpovídalo poslednímu vrcholu cesty. Tady se v¹ak slova mohou vyskytovat vícekrát a~konèit nejenom v~listech ale i~v~nìjakém vnitøním vrcholu (co¾ se stane tehdy, pokud je jedno hledané slovo prefixem jiného hledaného slova). Formálnì to nebudeme dokazovat, ale snadno nahlédneme, ¾e listy stromu odpovídají hledaným slovùm, ale opaènì to neplatí. - -\figure{ara_strom_end.eps}{Vyhledávací automat s~konci slov.}{1in} - -Dále bychom mìli do~automatu pøidat zpìtné hrany. Jejich definice bude úplnì stejná jako u automatu pro hledání jednoho slova. Jinými slovy z~ka¾dého stavu pùjde zpìtná hrana do~nejdel¹ího vlastního suffixu, který je stavem. Èili kdy¾ budeme mít nìjaké jméno stavu, budeme se ho sna¾it co nejménì (ale alespoò o~znak) zkrátit zleva, abychom zase dostali jméno stavu. Z~koøene -- prázdného stavu -- pak evidentnì ¾ádná zpìtná hrana nepovede. - -\figure{ara_strom_final.eps}{Vyhledávací automat se zpìtnými hranami.}{1,25in} - -Zbývá nám je¹tì si rozmyslet, jakým zpùsobem bude ná¹ automat hlásit výstup. Opìt smìøujeme k~tomu, aby se automat po~pøeètení nìjakého kusu textu nacházel ve~stavu odpovídajícímu nejdel¹ímu mo¾nému suffixu toho textu. Zatímco u hledání jediné jehly bylo hlá¹ení výskytù jednoduché -- kdykoliv jsme se dostali na~konec \uv{automatové cestièky} tady to bude opìt slo¾itìj¹í. - -První, co se nabízí, je vyu¾ít toho, ¾e jsme si oznaèili nìjaké vrcholy, kde hledaná slova konèí. Co tedy zkusit hlásit výskyt tohoto slova v¾dy, kdy¾ pøijdeme do~nìjakého oznaèeného vrcholu? Tento zpùsob v¹ak nefunguje, pokud se uvnitø nìkteré jehly skrývá jehla vnoøená. Napøíklad po~pøeètení slova |bara|, nám ná¹ souèasný automat neøíká, ¾e bychom mìli nìjaké slovo ohlásit, a~pøitom tam evidentì konèí podøetìzec |ara|. Stejnì tak pokud pøeèteme |barbara|, u¾ si nev¹imneme toho, ¾e tam konèí zároveò i~|ara|. Pouhé \uv{hlá¹ení teèek} tedy nefunguje. - -Dále si mù¾eme v¹imnout toho, ¾e v¹echna slova, která by se mìla v~daném stavu hlásit, jsou suffixy jména tohoto stavu. Pøitom víme, ¾e zpìtná hrana jméno stavu zkracuje zleva. Tak¾e speciálnì v¹echny suffixy daného stavu, které jsou také stavy, se dají najít tak, ¾e se vydáme po~zpìtných hranách do~koøene. Nabízí se tedy v¾dy projít cestu po~zpìtných hranách a¾ do~koøene a~hlásit v¹echny \uv{teèky}. Tento zpùsob by nám v¹ak celý algoritmus znaènì zpomalil, proto¾e cesta do~koøene mù¾e být relativnì dlouhá, ale teèek na~ní obvykle bude málo. - -Mohli bychom také zkusit si pro ka¾dý stav $\beta$ pøedpoèítat mno¾inu $cache(\beta)$, která by obsahovala v¹echna slova, která máme hlásit, kdy¾ se ve~stavu $\beta$ nacházíme. Pokud pak do~tohoto stavu vstoupíme, podíváme se na~tuto mno¾inu a~vypí¹eme v¹e, co v~ní je. Výpis nám bude evidentnì trvat lineárnì k~velikosti mno¾iny, celkovì tedy lineárnì k~velikosti výstupu. Problém je ale ten, ¾e jednotlivé cache mohou být hodnì velké, tak¾e je nestihneme sestrojit v lineárním èase. (Rozmyslete si pøíklad slovníku, kdy se to stane.) - -To, co nám ale ji¾ opravdu pomù¾e, bude zavedení zkratek. V¹imli jsme si, ¾e po~zpìtných hranách mù¾eme projít do~koøene a~hlásit v¹echny nalezené teèky. Vadilo nám ale, ¾e se mù¾e stát, ¾e budeme dlouho po~cestì chodit a~pøi tom ¾ádné teèky nenalézat. Zavedeme si proto zkratky k~nejbli¾¹í teèce. - -\s{Definice} (zkratková hrana): -Budeme mít tedy nìjakou funkci $slovo(\beta) :=$ slovo, které konèí ve~stavu $\beta$ (nebo $\emptyset$, pokud ¾ádné takové slovo není). Dále pak funkci $out(\beta) :=$ nejbli¾¹í vrchol dosa¾itelný po~zpìtných hranách, èili nejdel¹í vlastní suffix stavu $\beta$, v~nìm¾ je definovaná funkce $slovo$. Trochu lid¹tìji øeèeno, ten nejbli¾¹í dosa¾itelný vrchol, ve~kterém je teèka. - -Po pøidání tìchto zkratkových hran ji¾ máme reprezentaci, ve~které opravdu umíme v~daném stavu vyjmenovat v¹echna slova, která máme vypsat, a~to v~èase lineárním s~tím, kolik tìch slov je. +Lineární èas s~délkou jehly potøebujeme na~postavení automatu, lineární èas +s~délkou sena pak potøebujeme na~samotné vyhledání. +\qed + +\h{Hledání více øetìzcù najednou: algoritmus Aho-Corasicková} + +Nyní si zahrajeme tuté¾ hru, ov¹em v~trochu slo¾itìj¹ích kulisách. Tentokrát +bude jehel vícero: $\iota_1, \ldots, \iota_N$, jejich délky oznaèíme $J_I = \vert \iota_I \vert $. +Opìt dostaneme nìjaké seno~$\sigma$ délky $S=\vert \sigma \vert$ a chceme nalézt +v¹echny výskyty jehel v~senì. + +Pøedtím, ne¾ se pustíme do~vlastního vyhledávacího algoritmu, mìli bychom si +ujasnit, co bude jeho výstupem. Dokud byla jehla jedna jediná, bylo to jasné -- +chtìli jsme nalézt mno¾inu v¹ech pozic v~senì, na~kterých zaèínaly výskyty +jehly. Jak tomu bude zde? Budeme chtít vìdìt, která jehla se vyskytuje na které +pozici. Jinými slovy budeme chtít vypsat v¹echny dvojice $(K,I)$ takové, +¾e $\sigma[K:K+J_I]= \iota_I$. + +Zde se v¹ak skrývá jedna drobná zrada. Budeme se asi muset vzdát nadìje +na algoritmus, jeho¾ slo¾itost je lineární v~celkové délce v¹ech jehel +a~sena. Výstup toti¾ mù¾e být del¹í ne¾ lineární. Pokud je toti¾ jedna +jehla suffixem druhé, na jedné pozici v~senì mohou konèit výskyty obou. +Proto budeme hledat algoritmus, který bude lineární v~délce vstupu plus +délce výstupu, co¾ je evidentnì to nejlep¹í, èeho mù¾eme dosáhnout. + +Algoritmus, který si nyní uká¾eme, objevili v~roce 1975 pan Aho a~paní +Corasicková. Je elegantním zobecnìním Knuthova-Morrisova-Prattova algoritmu pro +více øetìzcù. + +\s{Vyhledávací automat:} +Opìt se budeme sna¾it sestrojit vyhledávací automat, jeho¾ stavy budou +odpovídat prefixùm jehel a dopøedné hrany roz¹iøování prefixù o~jeden znak. +Tentokrát navíc nebude jasnì definovaný koncový stav, oznaèíme si proto +v¹echny stavy, které odpovídají nìkteré z~jehel (na pøíkladu na obrázku +je vidìt, ¾e to nemusí být jen listy). + +\figure{ara_strom_zkr.eps}{Vyhledávací automat pro slova |ara|, |bar|, |arab|, |baraba| a |barbara|.}{1.25in} + +Dále potøebujeme zpìtné hrany (na obrázku èerné ¹ipky). +Jejich definice bude úplnì stejná jako u~automatu KMP. +Z~ka¾dého stavu pùjde zpìtná hrana do~jeho nejdel¹ího vlastního suffixu, který je také +stavem. Èili se budeme sna¾it jméno stavu zkracovat zleva tak dlouho, ne¾ dostaneme +opìt jméno stavu. Z~koøene -- prázdného stavu -- pak evidentnì ¾ádná zpìtná hrana nepovede. + +Funkce pro hledání v~senì bude vypadat stejnì jako u~KMP: zaène v~poèáteèním +stavu (to je koøen stromu), postupnì bude roz¹iøovat seno o~dal¹í písmenka, +poka¾dé zkusí jít dopøednou hranou a pokud to nejde, bude se vracet po~zpìtných +hranách tak dlouho, a¾ buïto bude existovat vhodná dopøedná hrana, nebo se vrátí +do koøene stromu a tehdy nový znak zahodí. + +Stejnì jako u~KMP nahlédneme, ¾e procházení sena trvá $\O(S)$ a ¾e platí analogický +invariant, toti¾ ¾e se v~ka¾dém okam¾iku nacházíme ve~stavu, který odpovídá nejdel¹ímu +suffixu zatím pøeèteného sena, který je prefixem nìkteré jehly. + +\s{Hlá¹ení výskytù:} +Jediné, co se bude od KMP li¹it, je, kdy ohlásit výskyt. U~KMP to bylo snadné: kdykoliv +jsme dospìli do posledního stavu, znamenalo to nalezení jehly. Nabízí se hlásit +výskyt, kdykoliv dojdeme do stavu oznaèeného jako koncový. To ale nefunguje: +pokud ná¹ ukázkový automat pøeète seno |bara|, skonèí ve stavu~|bara|, a~pøitom +by mìl ohlásit výskyt jehly |ara|. Stejnì tak pøeèteme-li |barbara|, nev¹imneme +si, ¾e na tém¾e místì konèí i |ara|. + +Platí ale, ¾e v¹echna slova, která bychom mìli v~daném stavu ohlásit, jsou suffixy +jména tohoto stavu. Mohli bychom je tedy najít tak, ¾e se vydáme po zpìtných hranách +a¾ do koøene a kdykoliv projdeme pøes koncový vrchol, ohlásíme výskyt. To ov¹em +trvá pøíli¹ dlouho -- jistì by se stávalo, ¾e bychom podnikli dlouhou cestu do koøene +a nena¹li na ní ani jeden výskyt. + +Dal¹í, co se nabízí, je pøedpoèítat si pro ka¾dý stav~$\beta$ mno¾inu slov ${\cal S}(\beta)$, +jejich¾ výskyty máme v~tomto stavu hlásit. To by fungovalo, ale existují mno¾iny jehel, +pro které bude celková velikost mno¾in ${\cal S}(\beta)$ superlineární. Museli bychom se +tedy vzdát lákavé mo¾nosti stavby automatu v~lineárním èase. (Rozmyslete si, jak by +takové jehly vypadaly.) + +Jak to tedy vyøe¹íme? Zavedeme zkratky (na obrázku zelenì): \s{Definice:} -Vyhledávací automat sestává ze stromu dopøedných hran (vrcholy jsou prefixy jehel, hrany odpovídají roz¹íøení o~písmenko), zpìtných hran ($z(\beta) :=$ nejdel¹í vlastní suffix slova $\beta$, který je stavem) a~zkratkových hran. - -Automat pak bude na~na¹em pøíkladu vypadat takto (zkratkové hrany jsou znázornìny zelenì): - -\figure{ara_strom_zkr.eps}{Vyhledávací automat se zkratkovými hranami.}{1,25in} - -Nyní u¾ nám zbývá jenom vlastní algoritmus -- nejdøív popí¹eme algoritmus, který bude hledat pomocí takového automatu, a~potom se pustíme do~toho, jak se takový automat staví. +{\I Zkratková hrana} ze~stavu~$\alpha$ vede do nejbli¾¹ího stavu $\zeta(\alpha)$ dosa¾itelného +z~$\alpha$ po zpìtných hranách, který je koncový. + +Jinými slovy, $\zeta(\alpha)$ nám øekne, jaký je nejdel¹í vlastní suffix slova~$\alpha$, který +je jehlou. Pokud takový suffix neexistuje, ¾ádná zkratková hrana ze~stavu~$\alpha$ nepovede. +Pomocí zkratkových hran mù¾eme snadno vyjmenovat v¹echny výskyty. Budeme postupovat stejnì, +jako bychom procházeli po v¹ech zpìtných hranách, jen budeme dlouhé úseky zpìtných hran, na~nich¾ +není nic k~hlá¹ení, pøeskakovat v~konstantním èase. + +\s{Reprezentace automatu:} +Vyhledávací automat se tedy sestává ze stromu dopøedných hran, ze zpìtných +hran a ze~zkratkových hran. Ne¾ vyslovíme samotný algoritmus AC, rozmysleme si, jak automat +ulo¾it do pamìti. Pro ka¾dý stav si budeme pamatovat: +\itemize\ibull +\:$I$ -- poøadové èíslo stavu (tøeba v~poøadí, jak vrcholy vznikaly), +\:$\(I)$ -- kam z~nìj vede zpìtná hrana (vyu¾íváme toho, ze mù¾e být nejvý¹e jedna, tak¾e si zapamatujeme + èíslo stavu, do nìj¾ vede), +\:$\(I)$ -- kam z~nìj vede zkratková hrana (takté¾), +\:$\(I)$ -- zda tu konèí nìjaké slovo (a~pokud ano, tak které), +\:$\(I,x)$ -- kam vede dopøedná hrana oznaèená písmenem~$x$ (pro malé abecedy si to + mù¾eme pamatovat v~poli, pro velké tøeba v~he¹ovací tabulce nebo stromu). +\endlist -Nejprve si nadefinujeme, jak vypadá jeden krok automatu. Bude to vlastnì nìjaká funkce, která dostane stav a~písmenko. Ona nás pak pomocí tohoto písmenka posune po~automatu. ($f(\alpha, x)$ bude dopøedná hrana ze stavu $\alpha$ oznaèená písmenem~$x$) +\>Celý algoritmus pro zpracování sena automatem pak bude vypadat takto: -\s{Krok ($\alpha$, $x$):} +\s{Krok($I$, $x$):} \cmt{Jeden krok automatu: jsme ve stavu~$I$, pøeèetli jsme znak~$x$.} \algo -\:Dokud $f(\alpha, x) = \emptyset~\&~\alpha \neq \~~\alpha \leftarrow z(\alpha)$. -\:Pokud $f(\alpha, x) \neq \emptyset:~~\alpha \leftarrow f(\alpha, x)$. -\:Vrátíme výsledek. +\:Dokud $\(I, x) = \emptyset~\&~I \ne \$: $I \leftarrow \(I)$. +\:Pokud $\(I, x) \ne \emptyset$: $I \leftarrow \(I,x)$. +\:Vrátíme nový stav~$I$. \endalgo -\s{Hledání:} +\s{Hledej($\sigma$):} \cmt{Spu¹tìní automatu na øetìzec~$\sigma$.} \algo -\:$\alpha \leftarrow \$. -\:Pro znaky $x$ ze slova $\sigma$: -\::$\alpha \leftarrow \(\alpha, x)$. -\::$\beta \leftarrow \alpha$ -\::Dokud $\beta \neq \emptyset$: -\:::Je-li $\(\beta) \neq \emptyset$: -\::::Ohlásíme $\(\beta)$. -\:::$\beta \leftarrow \(\beta)$. +\:$I \leftarrow \$. +\:Pro znaky $x\in\sigma$ postupnì provádíme: +\::$I \leftarrow \(I, x)$. +\::$K \leftarrow I$. +\::Dokud $K \neq \emptyset$: +\:::Je-li $\(K) \neq \emptyset$: +\::::Ohlásíme $\(K)$. +\:::$K \leftarrow \(K)$. \endalgo -Algoritmus hledání vlastnì není nic jiného, ne¾ prosté projití po~zelených zkratkových hranách ze stavu $\alpha$, ve~kterém právì jsme, a~ohlá¹ení v¹eho, co po~cestì najdeme. +\>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. -V ka¾dém okam¾iku se automat nachází ve~stavu, který odpovídá nejdel¹ímu mo¾nému suffixu toho, co jsme u¾ pøeèetli. Dùkaz tohoto invariantu je stejný jako u verze automatu pro hledání pouze jedné jehly, nebo» vychází pouze z~definice zpìtných hran. Podobnì nahlédneme, ¾e èasová slo¾itost vyhledávací procedury je lineární v~délce sena plus to, co spotøebujeme na~hlá¹ení výskytù. Nejprve na~chvíli zapomeneme, ¾e nìjaké výskyty hlásíme a~spoèítáme jenom kroky. Ty mohou vést dopøedu a~zpátky. Krok dopøedu prodlu¾uje jméno stavu o~jedna, krok dozadu zkracuje aspoò o~jedna. Tudí¾ krokù dozadu je maximálnì tolik, co krokù dopøedu a~krokù dopøedu je maximálnì tolik, kolik je délka sena. V¹echny kroky dohromady tedy trvají $\O(S)$. Hlá¹ení výskytù pak trvá $\O(S~+ \vert V \vert)$. Celé hledání tedy trvá lineárnì v~délce vstupu a~výstupu. +\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. @@ -319,7 +378,29 @@ To, \s{Vìta:} Algoritmus Aho-Corasicková najde v¹echny výskyty v~èase $$\O\left(\sum_i~\iota_i~+~S~+~\sharp\\right).$$ -Je¹tì se na~závìr zamysleme, jak bychom si takový automat ukládali do~pamìti. Urèitì se nám bude hodit si stavy nìjak oèíslovat (tøeba v~poøadí, v~jakém budou vznikat). Potom funkce pro zpìtné a~zkratkové hrany mohou být reprezentované polem indexovaným èíslem stavu. Funkce {\I Slovo}, která øíká, jaké slovo ve~stavu konèí, zase mù¾e být pole indexované stavem, které nám øekne poøadové èíslo slova ve~slovníku. Pro dopøedné hrany v~ka¾dém vrcholu pak mù¾eme mít pole indexované písmenky abecedy, které nám pro ka¾dé písmenko øekne, buï ¾e taková hrana není, nebo nám øekne, kam tato hrana vede. Je vidìt, ¾e takovéto pole se hodí pro pomìrnì malé abecedy. U¾ pro abecedu A-Z~bude velikosti 26 a~z~vìt¹iny bude prázdné, tak¾e bychom plýtvali pamìtí. V praxi se proto èasto pou¾ívá hashovací tabulka. Pøípadnì bychom mohli mít i~jen jednu velkou spoleènou hashovací tabulku, která bude reprezentovat funkci celou, ve~které budou zahashované dvojice (stav, písmenko). Tìchto dvojic je evidentnì tolik, kolik hran stromu, èili lineárnì s~velikostí slovníku, a~je to asi nejkompaktnìj¹í reprezentace. +\h{Rabinùv-Karpùv algoritmus} + +Nyní si uká¾eme je¹tì jeden algoritmus na~hledání jedné jehly, který nebude mít v~nejhor¹ím pøípadì lineární slo¾itost, ale bude ji mít prùmìrnì. Bude daleko jednodu¹¹í a~uká¾e se, ¾e je v~praxi daleko rychlej¹í. Bude to algoritmus zalo¾ený na~hashování. + + +Pøedstavme si, ¾e máme seno délky $S$ a~jehlu délky $J$, a~vezmìme si nìjakou hashovací funkci, které dáme na~vstup $J$-tici znakù (tedy podslova dlouhá jako jehla). Tato hashovací funkce nám je pak zobrazí do~mno¾iny $\{0,\ldots,N-1\}$ pro nìjaké dost velké~$N$. Jak nám toto pomù¾e pøi hledání jehly? Vezmeme si libovolné \uv{okénko} délky $J$ a~ne¾ budeme zji¹»ovat, zda se v~nìm jehla vyskytuje, tak si spoèítáme hashovací funkci a~porovnáme ji s~hashem jehly. Èili ptáme se, jestli je hash ze sena od~nìjaké pozice $I$ do~pozice $I+J$ roven hashi jehly -- formálnì: $h(\sigma [I: I+J ]) = h(\iota)$. Teprve tehdy, kdy¾ zjistíme, ¾e se hodnota hashovací fce shoduje, zaèneme doopravdy porovnávat øetìzce. + +Není to ale nìjaká hloupost? Mù¾e nám vùbec takováto konstrukce pomoci? Není to tak, ¾e na~spoèítání hashovací funkce z~$J$ znakù, potøebujeme tìch $J$ znakù pøeèíst, co¾ je stejnì rychlé, jako rovnou øetìzce porovnávat? Pou¾ijeme trik, který bude spoèívat v~tom, ¾e si zvolíme ¹ikovnou hashovací funkci. Udìláme to tak, abychom ji mohli pøi posunutí \uv {okénka} o~jeden znak doprava v~konstantním èase pøepoèítat. Chceme umìt z~$h(x_1 \dots x_j)$ spoèítat $h(x_2 \dots x_{j+1})$. +Na~zaèátku si tedy spoèítáme hash jehly a~první $J$-tice znakù sena. Pak ji¾ jenom posouváme \uv {okénko} o~jedna, pøepoèítáme hashovací funkci a~kdy¾ se shoduje s~hashem jehly, tak porovnáme. Budeme pøitom vìøit tomu, ¾e pokud se tam jehla nevyskytuje, pak máme hashovací funkci natolik rovnomìrnou, ¾e pravdìpodobnost toho, ¾e se pøesto strefíme do~hashe jehly, je $1/N$. Jinými slovy jenom v~jednom z~øádovì $N$ pøípadù budeme porovnávat fale¹nì -- tedy provedeme porovnání a~vyjde nám, ¾e výsledek je neshoda. V~prùmìrném pøípadì tedy mù¾eme stlaèit slo¾itost a¾ témìø k~lineární. + +Podívejme se teï na~prùmìrnou èasovou slo¾itost. Budeme urèitì potøebovat èas na~projití jehly a~sena. Navíc strávíme nìjaký èas nad fale¹nými porovnáními, kterých bude v~prùmìru na~ka¾dý $N$-tý znak sena jedno porovnání s~jehlou -- tedy $SJ / N$, pøièem¾ $N$ mù¾eme zvolit dost velké na~to, abychom tento èlen dostali pod nìjakou rozumnou konstantu... Nakonec budeme potøebovat jedno porovnání na~ka¾dý opravdový výskyt, èemu¾ se nevyhneme. Pøipoèteme tedy je¹tì $J \cdot$ {\I $\sharp$výskytù}. Dostáváme tedy: $ \O(J+S+SJ/N+J \cdot$ {\I $\sharp$výskytù}). + +Zbývá malièkost -- toti¾ kde vzít hashovací funkci, která toto v¹e splòuje. Jednu si uká¾eme. Bude to vlastnì takový hezký polynom: +$$h(x_1 \dots x_j) := \left(\sum_{I=1}^{J} x_I \cdot p^{J-I}\right) \bmod N.$$ +Jinak zapsáno se tedy jedná o: +$$(x_1 \cdot p^{J-1} + x_2 \cdot p^{J-2} + \dots + x_J \cdot p^0 ) \bmod N.$$ +Po posunutí okénka o~jedna chceme dostat: +$$(x_2 \cdot p^{J-1} + x_3 \cdot p^{J-2} + \dots + x_J \cdot p^1 + x_{J+1} \cdot p^0 ) \bmod N.$$ +Kdy¾ se ale podíváme na~èleny tìchto dvou polynomù, zjistíme, ¾e se li¹í jen o~málo. Pùvodní polynom staèí pøenásobit~$p$, odeèíst první èlen s~$x_1$ a~naopak pøièíst chybìjící èlen $x_{J+1}$. Dostáváme tedy: +$$h(x_2 \dots x_{J+1}) = (p \cdot h(x_1 \dots x_J) - x_1 \cdot p^J + x_{J+1}) \bmod N.$$ +Pøepoèítání hashovací funkce tedy není nic jiného, ne¾ pøenásobení té minulé~$p$, odeètení nìjakého násobku toho znaku, který vypadl z~okénka, a~pøiètení toho znaku, o~který se okénko posunulo. Pokud tedy máme k~dispozici aritmetické operace v~konstantním èase, zvládneme konstantnì pøepoèítávat i~hashovací funkci. + +Tato hashovací funkce se dokonce nejen hezky poèítá, ale dokonce se i~opravdu \uv{hezky} chová (tedy \uv{rozumnì} náhodnì), pokud zvolíme vhodné~$p$. To bychom mìli zvolit tak, aby bylo rozhodnì nesoudìlné s~$N$ -- tedy $\(p, N) = 1$. Aby se nám navíc dobøe projevilo modulo obsa¾ené v~hashovací funkci, mìlo by být~$p$ relativnì velké (lze dopoèítat, ¾e optimum je mezi $2/3 \cdot N$ a~$3/4 \cdot N$). S~takto zvoleným~$p$ se tato hashovací funkce chová velmi pøíznivì a~v~praxi má celý algoritmus takøka lineární èasovou slo¾itost (prùmìrnou). %% Cvièení: velké abecedy