-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 $\<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 \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ì):