+\s{Vìta:} Algoritmus KMP najde v¹echny výskyty v~èase $O(J+S)$.
+Linéá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í.
+
+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í.
+
+\h{Rabinùv -- Karpùv algoritmus}
+
+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$-tice znakù (tedy podslova dlouhá jako jehla). Tato hashovací funkce nám je pak zobrazí do~nìjaké velké mno¾iny èísel. 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í fci a~porovnáme jí 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, tak zaèneme doopravdy porovnávat øetìzce.
+
+Není to ale nìjaká hloupost? Mù¾e nám vùbec takováto konstrukce pomoct? 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 jí mohli pøi posunutí \uv {okénka} o~jedna 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 od~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 \sharp výskytù$. Dostáváme tedy: $ \O(J+S+SJ/N+J \cdot \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) := (\sum_{I=1}^{J} x_I \cdot p^{J-I})~mod~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 )~mod~N$$
+Po posunutí okénka o~jedna, pak 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 )~mod~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})~mod~N$$
+Pøepoèítání hashovací funkce tedy není nc 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 zvoli tak, aby bylo rozhodnì nesoudìlné s~$N$ -- tedy $NSD(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 a~3/4 $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{Více jehel}
+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é mohly 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~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 povinost 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~70. letech 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: {\I 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 cestièka, zde u¾ to bude strom.
+
+\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 urèitì 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.}{1in}
+
+Zbývá nám si je¹tì 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í pouze jedné jehly bylo hlá¹ení výskytù jednoduché a~to prostì tím, ¾e 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 {\I 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 {\I ARA}. Stejnì tak pokud pøeèteme {\I BARBARA}, u¾ si nev¹imneme toho, ¾e tam konèí zároveò i~{\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 toho jména stavu. Pøi tom víme, ¾e zpìtná hrana nám zkracuje zleva. Tak¾e speciálnì v¹echny suffixy daného stavu, které jsou také stavy, se dají najít tak, ¾e se z~toho stavu, kde právì jsme, 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ì zpomalilo, proto¾e cestièka do~koøene mù¾e být relativnì dlouhá, ale teèek na~ní mù¾e být jen 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 evidentì trvat lineárnì k~velikosti mno¾inky, celkovì pak tedy lineárnì k~velikosti výstupu. Problém je ale ten, ¾e jednotlivé cache mohou být hodnì velké.
+
+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, v~kterém je teèka.
+
+Po pøidání tìchto zkratkových hran ji¾ máme reprezentaci, v~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.
+
+\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.}{1in}
+
+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í.
+
+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ísm. $x$)
+
+\s{Krok ($\alpha$, $x$):}
+\algo
+\:Dokud $f(\alpha, x) = \emptyset~\&~\alpha \neq koøen:~~\alpha \leftarrow z(\alpha)$.
+\:Pokud $f(\alpha, x) \neq \emptyset:~~\alpha \leftarrow f(\alpha, x)$.
+\:Vrátíme výsledek.
+\endalgo
+
+\s{Hledání:}
+\algo
+\:$\alpha \leftarrow koøen$.
+\:Pro znaky $x$ ze slova $\sigma$:
+\::$\alpha \leftarrow krok(\alpha, x)$.
+\::Dokud $\alpha \neq \emptyset$:
+\:::Je-li $slovo(\alpha) \neq \emptyset$:
+\::::ohlásíme $slovo(\alpha)$.
+\::::$\alpha \leftarrow out(\alpha)$.
+\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.
+
+V ka¾dém okam¾iku se automat nachází ve~stavu, který odpovídá nejmen¹í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ézt dopøedu a~zpátky. Kroky 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)$. Velé hledání tedy trvá lineárnì v~délce vstupu a~výstupu.
+
+Zbývá nám u¾ jen konstrukce automatu. Opìt pou¾ijeme trik, ¾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 rùznì køí¾em mezi jednotlivými vìtvemi automatu. Mohlo by se nám tedy klidnì stát, ¾e pøi hledání nìjakého slova potøebujeme zpìtnou hranu, která vede vlastnì do~jiného slova, které jmse 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:}
+\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 frontu $F$ a~vlo¾íme do~ní syny koøene
+\:$\forall v~\in F:~~z(v) \leftarrow r, out(v) \leftarrow \emptyset$
+\:Dokud $F \neq \emptyset$:
+\::Vybereme $u$ z~forny $F$
+\::Pro v¹echny syny $v$ vrcholu $u$:
+\:::$q \leftarrow krok(z(u), písmeno na~hranì uv)$
+\:::$z(v) \leftarrow q$
+\:::Pokud $slovo(q) \neq \emptyset$, pak $out(v) \leftarrow q$
+\::::jinak $out(v) \leftarrow out(q)$.
+\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ètu nad v¹emi tìmi slovy. To u¾ ale víme, ¾e je lineární v~celkové délce tìch slov. Konstrukce automatu tedy trvá ménì nebo rovno tomu, co hledání v¹ech $\iota_i$, co¾ je $\O(\sum_{i} \iota_i)$.
+
+\s{Vìta:} Algoritmus Aho-Corasicková najde v¹echny výskyty v~èase $\O(\sum_i~\iota_i~+~S~+~\sharp výskytù)$
+
+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 slovo, která øíká, jaké slovo ve~stavu konèí zase mù¾e být pouze pole indexované stavem, které nám øekne poøadové èíslo slova ve~slovníku. A~pro dopøedné hrany v~ka¾dém vrcholu mít pole indexované písmenky abecedy, které nám pro ka¾dé písmenko øekne buï taková hrana není, nebo nám øekne, kam vede. Je vidìt, ¾e takovéto pole se hodí pro pomìrnì malé abecedy. U¾ pro abecedu A-Z~bude velikosti 26 a~zvì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.
projects / ads2.git / blobdiff