3 \prednaska{1}{Vyhledávání v~textu}{}
7 Uva¾ujme následující problém: máme nìjaký text~$\sigma$ délky~$S$ (seno), chceme v~nìm najít
8 v¹echny výskyty nìjakého podøetìzce~$\iota$ délky~$J$ (jehly). Seno pøitom bude øádovì del¹í
11 Triviální øe¹ení pøesnì podle definice by vypadalo následovnì: Zkusíme v¹echny mo¾né pozice,
12 kde by se v~senì mohla jehla nacházet, a pro ka¾dou z~nich otestujeme, zda tam opravdu je.
13 Pozic je øádovì~$S$, ka¾dé porovnání stojí a¾~$J$, celkovì tedy algoritmus bì¾í v~èase
14 $\O(SJ)$. (Rozmyslete si, jak by vypadaly vstupy, pro které skuteènì spotøebujeme tolik èasu.)
16 Zkusme jiný pøístup: nalezneme v~senì první znak jehly a od tohoto místa budeme porovnávat
17 dal¹í znaky. Pokud se pøestanou shodovat, pøepneme opìt na hledání prvního znaku. Jen¾e odkud?
18 Pokud od místa, kde nastala neshoda, sel¾e to tøeba pøi hledání jehly |kokos| v~senì |clanekokokosu|
19 -- neshoda nastane za~|koko| a zbylý |kos| nás neuspokojí. Nebo se mù¾eme vrátit a¾ k~výskytu
20 prvního znaku a pokraèovat tìsnì za ním, jen¾e to je toté¾, co dìlal triviální algoritmus,
21 tak¾e je to také stejnì pomalé.
23 V~této kapitole si uká¾eme algoritmus, který je o~trochu slo¾itìj¹í, ale nalezne v¹echny
24 výskyty v~èase $\O(S+J)$. Pak ho zobecníme, aby umìl hledat více rùzných jehel najednou.
28 Aby se nám o~øetìzcových algoritmech lépe psalo, udìlejme si nejprve poøádek
29 v~terminologii okolo øetìzcù.
33 \:{\I Abeceda $\Sigma$} je nìjaká koneèná mno¾ina {\I znakù,} z~nich¾ se
34 skládají na¹e øetìzce.
35 \:{\I $\Sigma^*$} je mno¾ina v¹ech {\I slov} neboli {\I øetìzcù} nad abecedou~$\Sigma$,
36 co¾ jsou koneèné posloupnosti znakù ze~$\Sigma$.
40 Abeceda mù¾e být tvoøena tøeba písmeny |a| a¾~|z| nebo bity |0| a~|1|.
41 Potkáme ov¹em i rozlehlej¹í abecedy: napøíklad dnes bì¾ná znaková sada UniCode
42 má $2^{16}=65\,536$ znakù, v~novìj¹ích verzích dokonce $2^{31}\approx 2\cdot 10^9$ znakù. Je¹tì extrémnìj¹ím
43 zpùsobem pou¾ívají øetìzce lingvisté: na èeský text se nìkdy dívají jako na~øetìzec
44 nad abecedou, její¾ prvky jsou èeská slova.
46 Pro na¹e úèely budeme pøedpokládat, ¾e abeceda je \uv{rozumnì malá}, èím¾ myslíme, ¾e
47 její velikost je konstantní a navíc dostateènì malá na to, abychom si mohli dovolit
48 ukládat do pamìti pole indexovaná znakem.
52 \:{\I Slova} budeme znaèit malými písmenky øecké abecedy $\alpha$, $\beta$, \dots
53 \:{\I Znaky} oznaèíme malými písmeny latinky $a$, $b$, \dots{} \hfil\break
54 Znak budeme pou¾ívat i ve~smyslu jednoznakového øetìzce.
55 \:{\I Èísla} budeme znaèit velkými písmeny $A$, $B$, \dots
56 \:{\I Délka slova} $\vert \alpha \vert$ udává, kolika znaky je slovo tvoøeno.
57 \:{\I Prázdné slovo} znaèíme písmenem $\varepsilon$, je to jediné slovo délky~0.
58 \:{\I Zøetìzení} $\alpha\beta$ vznikne zapsáním slov $\alpha$ a~$\beta$ za sebe. Platí $\vert \alpha\beta \vert=\vert \alpha \vert+\vert \beta \vert$, $\alpha\varepsilon=\varepsilon\alpha=\alpha$.
59 \:$\alpha[k]$ je $k$-tý znak slova $\alpha$, indexujeme od~$0$ do~$\vert\alpha\vert-1$.
60 \:$\alpha[k:\ell]$ je {\I podslovo} zaèínající $k$-tým znakem a konèící tìsnì pøed~$\ell$-tým.
61 Tedy $\alpha[k:\ell] = \alpha[k]\alpha[k+1]\ldots\alpha[\ell-1]$. Pokud $k\ge\ell$, je podslovo
62 prázdné. Pokud nìkterou z~mezí vynecháme, míní se $k=0$ nebo $\ell=\vert\alpha\vert$.
63 \:$\alpha[{}:\ell]$ je {\I prefix} (pøedpona) tvoøený prvními $\ell$ znaky øetìzce.
64 \:$\alpha[k:{}]$ je {\I suffix} (pøípona) od $k$-tého znaku do~konce øetìzce.
65 \:$\alpha[:] = \alpha$.
68 \>Dodejme je¹tì, ¾e prázdné slovo je prefixem, suffixem i~podslovem jakéhokoliv slova vèetnì sebe sama.
69 Ka¾dé slovo je také prefixem, suffixem i~podslovem sebe sama. To se ne v¾dy hodí, pak budeme hovoøit
70 o~{\I vlastním} prefixu, suffixu èi podslovì, èím¾ myslíme, ¾e alespoò jeden znak nebude obsahovat.
72 \h{Inkrementální algoritmus}
74 Vra»me se tedy zpìt k~pùvodnímu problému hledání podøetìzcù. Nejprve si
75 ujasnìme, co má být výstupem algoritmu. Budeme chtít nalézt mno¾inu v¹ech
76 indexù~$K$ takových, ¾e $\sigma[K:K+\vert\iota\vert] = \iota$. To je dostateènì
77 kompaktní výstup (nejvý¹e lineární s~délkou sena), a~pøitom obsahuje informace
80 Na hledání podøetìzce pou¾ijeme {\I inkrementální pøístup.} Tím se obecnì myslí,
81 ¾e chceme umìt roz¹íøit vstup o~dal¹í znak a pøepoèítat výstup. V~na¹em pøípadì
82 budeme pøidávat znak na konec sena a zapoèítáme pøípadný nový výskyt jehly, který
85 Abychom toho dosáhli, budeme si prùbì¾nì udr¾ovat informaci o~tom, jaký nejdel¹í
86 prefix jehly konèí právì pøidaným znakem. Tomu budeme øíkat {\I stav algoritmu.}
87 A~jakmile bude tento prefix roven celé jehle, ohlásíme výskyt.
89 Pøedstavme si tedy, ¾e jsme pøeèetli øetìzec~$\sigma$, který konèil stavem~$\alpha$.
90 Teï vstup roz¹íøíme o~znak~$x$ na~$\sigma x$. V~jakém stavu se nyní máme
91 nacházet? Pokud to nebude prázdný øetìzec, musí konèit na~$x$, tedy ho mù¾eme
92 napsat ve~tvaru $\alpha'x$.
94 V¹imneme si, ¾e $\alpha'$ musí být suffixem slova~$\alpha$: Jeliko¾ $\alpha' x$
95 je prefix jehly, je $\alpha'$ také prefix jehly. A~proto¾e $\alpha'x$ je suffixem~$\sigma x$,
96 musí $\alpha'$ být suffixem~$\sigma$. Tedy jak $\alpha$, tak $\alpha'$ jsou suffixy slova~$\alpha$,
97 které jsou souèasnì prefixy jehly. Ov¹em stav~$\alpha$ jsme vybrali jako nejdel¹í slovo
98 s~touto vlastností, tak¾e $\alpha'$~musí být nejvý¹e tak dlouhé, a~tudí¾ je prefixem~$\alpha$.
100 Staèilo by tedy probrat v¹echny suffixy slova~$\alpha$, které jsou prefixem jehly,
101 a~vybrat z~nich nejdel¹í, který po roz¹íøení o~znak~$x$ je stále prefixem jehly.
103 Abychom ale nemuseli suffixy procházet v¹echny, pøedpoèítáme {\I zpìtnou funkci~$z$.}
104 Ta nám pro ka¾dý prefix jehly øekne, jaký je jeho nejdel¹í vlastní suffix,
105 který je opìt prefixem jehly. To nám umo¾ní procházet rovnou kandidáty na nový stav:
106 staèí probrat øetìzce $\alpha$, $z(\alpha)$, $z(z(\alpha))$, \dots{} a pou¾ít první,
107 který lze roz¹íøit o~znak~$x$. Pokud nepùjde roz¹íøit ani jeden z~tìchto kandidátù,
108 novým stavem bude prázdný øetìzec.
110 Na~této my¹lence je zalo¾en následující algoritmus.
112 \h{Knuthùv-Morrisùv-Prattùv algoritmus (KMP)}
114 Algoritmus se opírá o~{\I vyhledávací automat.} To je orientovaný graf, jeho¾
115 vrcholy ({\I stavy} automatu) odpovídají prefixùm jehly. Vrcholy jsou spojeny
116 hranami dvou druhù: {\I dopøedné} popisují roz¹íøení prefixu pøidáním jednoho písmene,
117 {\I zpìtné} vedou podle zpìtné funkce, tedy z~ka¾dého stavu do jeho nejdel¹ího
118 vlastního suffixu, který je opìt stavem.
120 \figure{barb.eps}{Vyhledávací automat pro slovo |barbarossa|}{4.1in}
122 Reprezentace automatu bude pøímoèará: stavy oèíslujeme od~0 do~$J$, dopøedná hrana
123 povede v¾dy ze stavu~$S$ do~$S+1$ a bude odpovídat roz¹íøení prefixu o~pøíslu¹ný
124 znak jehly, tedy $\iota[S]$. Zpìtné hrany si budeme pamatovat v~poli~$Z$, tedy
125 $Z[S]$ bude øíkat èíslo stavu, do~nìj¾ vede zpìtná hrana ze~stavu~$S$, pøípadnì
126 bude nedefinované, pokud taková hrana neexistuje.
128 Kdybychom takový automat mìli, mohli bychom pomocí nìj inkrementální algoritmus
129 z~pøedchozí sekce popsat následovnì:
131 \s{Krok($I$, $x$):} \cmt{Jeden krok automatu: jsme ve stavu~$I$, pøeèetli jsme znak~$x$.}
133 \:Dokud $\iota[I] \neq x~\&~I \neq 0: I \leftarrow Z[I]$.
134 \:Pokud $\iota[I] = x$, pak $I \leftarrow I + 1$.
135 \:Vrátíme nový stav~$I$.
138 \s{Hledej($\sigma$):} \cmt{Spu¹tìní automatu na øetìzec~$\sigma$.}
141 \:Pro znaky $x\in\sigma$ postupnì provádíme:
142 \::$I \leftarrow \<Krok>(I,x)$.
143 \::Pokud $I = J$, ohlásíme výskyt.
146 \s{Invariant:} Stav algoritmu~$I$ v~ka¾dém okam¾iku øíká, jaký nejdel¹í
147 prefix jehly je suffixem zatím pøeètené èásti sena. (To u¾ víme z~úvah
148 o~inkrementálním algoritmu.)
150 \s{Dùsledek:} Algoritmus ohlásí v¹echny výskyty. Pokud jsme toti¾ právì
151 pøeèetli poslední znak nìjakého výskytu, je celá jehla suffixem zatím
152 pøeètené èásti sena, tak¾e se musíme nacházet v~posledním stavu.
154 Jen musíme opravit drobnou chybu -- tìsnì poté, co ohlásíme výskyt, se
155 algoritmus zeptá na~dopøednou hranu z~posledního stavu. Ta ale
156 neexistuje. Napravíme to jednodu¹e: pøidáme fiktivní dopøednou hranu,
157 na~ní¾ je napsán znak odli¹ný od~v¹ech skuteèných znakù. Tím zajistíme,
158 ¾e se po této hranì nikdy nevydáme. Staèí tedy vhodnì dodefinovat $\iota[i]$.%
159 \foot{V jazyce C mù¾eme zneu¾ít toho, ¾e ka¾dý øetìzec je ukonèen znakem
162 \s{Lemma:} Funkce \<Hledej> bì¾í v~èase $\O(S)$.
165 Výpoèet funkce mù¾eme rozdìlit na prùchody dopøednými a zpìtnými hranami.
166 S~dopøednými je to snadné -- za~ka¾dý z~$S$ znakù sena projdeme po nejvý¹e
167 jedné dopøedné hranì. To o~zpìtných hranách neplatí, ale pomù¾e nám, ¾e ka¾dá
168 dopøedná hrana vede o~právì~1 stav doprava a ka¾dá zpìtná o~aspoò~1 stav
169 doleva. Proto je v¹ech prùchodù po~zpìtných hranách nejvý¹e tolik, kolik
170 jsme pro¹li dopøedných hran, tak¾e také nejvý¹e~$S$.
173 \s{Konstrukce automatu:}
174 Algoritmus je tedy lineární, ale potøebuje, aby mu nìkdo zkonstruoval
175 automat. Dopøedné hrany vytvoøíme snadno, ale jak si poøídit ty zpìtné?
177 Podnikneme my¹lenkový pokus: Pøedstavme si, ¾e automat u¾ máme hotový, ale nevidíme,
178 jak vypadá uvnitø. Chtìli bychom zjistit, jak v~nìm vedou zpìtné hrany, ov¹em jediné,
179 co umíme, je spustit automat na nìjaký øetìzec a zjistit, v~jakém stavu skonèil.
181 Tvrdíme, ¾e pro zji¹tìní zpìtné hrany ze~stavu~$\alpha$ staèí automatu pøedlo¾it
182 øetìzec $\alpha[1:{}]$. Definice zpìtné funkce je toti¾ nápadnì podobná invariantu,
183 který jsme o~funkci \<Hledej> dokázali. Obojí hovoøí o~nejdel¹ím suffixu daného
184 slova, který je prefixem jehly. Jediný rozdíl je v~tom, ¾e v~pøípadì zpìtné funkce
185 uva¾ujeme pouze vlastní suffixy, zatímco invariant pøipou¹tí i nevlastní. To ov¹em
186 snadno vyøe¹íme \uv{ukousnutím} prvního znaku jména stavu.
188 Pokud chceme objevit v¹echny zpìtné hrany, staèí automat spou¹tìt postupnì
189 na øetìzce $\iota[1:1]$, $\iota[1:2]$, $\iota[1:3]$, atd. Jeliko¾ funkce \<Hledej>
190 je lineární, stálo by nás to dohromady $\O(J^2)$. Pokud si ale v¹imneme, ¾e ka¾dý
191 ze~zmínìných øetìzcù je prefixem toho následujícího, je jasné, ¾e staèí spustit
192 automat jen jednou na øetìzec $\iota[1:{}]$ a jen zaznamenávat, kterými stavy
195 To je zajímavé pozorování, øeknete si, ale jak nám pomù¾e ke~konstrukci automatu,
196 kdy¾ samo u¾ hotový automat potøebuje? Pomù¾e pìkný trik: pokud hledáme zpìtnou
197 hranu z~$I$-tého stavu, spou¹tíme automat na slovo délky~$I-1$, tak¾e se mù¾eme
198 dostat pouze do prvních~$I-1$ stavù a vùbec nám nevadí, ¾e v~tom $I$-tém je¹tì
199 není zpìtná hrana hotova.%
200 \foot{Konstruovat nìjaký objekt pomocí tého¾ objektu je osvìdèený postup, který
201 si u¾ vyslou¾il i svùj vlastní název. V~angliètinì se mu øíká {\I bootstrapping}
202 a z~tohoto názvu vzniklo i bootování poèítaèù, proto¾e pøi nìm operaèní systém
203 vlastnì do pamìti zavádí sám sebe. Kde se toto slovo vzalo? Bootstrap znamená èesky
204 {\I ¹truple} -- to je takové to oèko na patì boty, které usnadòuje nazouvání.
205 A~v~jednom z~pøíbìhù o~baronu Prá¹ilovi sly¹íme barona vyprávìt, jak se uvíznuv
206 v~ba¾inì zachránil tím, ¾e se vytáhl za ¹truple. Krásný popis bootování, není-li¾
209 Konstrukce automatu tedy bude vypadat tak, ¾e nejdøíve sestrojíme pouze dopøedné
210 hrany, pak rozpracovaný automat spustíme na øetìzec $\iota[1:{}]$ a podle toho,
211 jakými stavy prochází, doplòujeme zpìtné hrany. A~jeliko¾ vyhledávání je lineární,
212 celá konstrukce trvá $\O(J)$.
214 Hotový algoritmus mù¾eme zapsat následovnì:
216 \s{Konstrukce zpìtných hran:}
218 \:$Z[0] \leftarrow ?$, $Z[1] \leftarrow 0$.
220 \:Pro $K = 2, \ldots, J-1$:
221 \::$I \leftarrow \<Krok>(I, \iota[K])$.
222 \::$Z[K] \leftarrow I$.
225 A~jsme hotovi výsledky shrnout do následující vìty:
227 \s{Vìta:} Algoritmus KMP najde v¹echny výskyty v~èase $O(J+S)$.
230 Lineární èas s~délkou jehly potøebujeme na~postavení automatu, lineární èas
231 s~délkou sena pak potøebujeme na~samotné vyhledání.
234 \h{Hledání více øetìzcù najednou: algoritmus Aho-Corasicková}
236 Nyní si zahrajeme tuté¾ hru, ov¹em v~trochu slo¾itìj¹ích kulisách. Tentokrát
237 bude jehel vícero: $\iota_1, \ldots, \iota_N$, jejich délky oznaèíme $J_I = \vert \iota_I \vert $.
238 Opìt dostaneme nìjaké seno~$\sigma$ délky $S=\vert \sigma \vert$ a chceme nalézt
239 v¹echny výskyty jehel v~senì.
241 Pøedtím, ne¾ se pustíme do~vlastního vyhledávacího algoritmu, mìli bychom si
242 ujasnit, co bude jeho výstupem. Dokud byla jehla jedna jediná, bylo to jasné --
243 chtìli jsme nalézt mno¾inu v¹ech pozic v~senì, na~kterých zaèínaly výskyty
244 jehly. Jak tomu bude zde? Budeme chtít vìdìt, která jehla se vyskytuje na které
245 pozici. Jinými slovy budeme chtít vypsat v¹echny dvojice $(K,I)$ takové,
246 ¾e $\sigma[K:K+J_I]= \iota_I$.
248 Zde se v¹ak skrývá jedna drobná zrada. Budeme se asi muset vzdát nadìje
249 na algoritmus, jeho¾ slo¾itost je lineární v~celkové délce v¹ech jehel
250 a~sena. Výstup toti¾ mù¾e být del¹í ne¾ lineární. Pokud je toti¾ jedna
251 jehla suffixem druhé, na jedné pozici v~senì mohou konèit výskyty obou.
252 Proto budeme hledat algoritmus, který bude lineární v~délce vstupu plus
253 délce výstupu, co¾ je evidentnì to nejlep¹í, èeho mù¾eme dosáhnout.
255 Algoritmus, který si nyní uká¾eme, objevili v~roce 1975 pan Aho a~paní
256 Corasicková. Je elegantním zobecnìním Knuthova-Morrisova-Prattova algoritmu pro
259 \s{Vyhledávací automat:}
260 Opìt se budeme sna¾it sestrojit vyhledávací automat, jeho¾ stavy budou
261 odpovídat prefixùm jehel a dopøedné hrany roz¹iøování prefixù o~jeden znak.
262 Tentokrát navíc nebude jasnì definovaný koncový stav, oznaèíme si proto
263 v¹echny stavy, které odpovídají nìkteré z~jehel (na pøíkladu na obrázku
264 je vidìt, ¾e to nemusí být jen listy).
266 \figure{ara_strom_zkr.eps}{Vyhledávací automat pro slova |ara|, |bar|, |arab|, |baraba| a |barbara|.}{1.25in}
268 Dále potøebujeme zpìtné hrany (na obrázku èerné ¹ipky).
269 Jejich definice bude úplnì stejná jako u~automatu KMP.
270 Z~ka¾dého stavu pùjde zpìtná hrana do~jeho nejdel¹ího vlastního suffixu, který je také
271 stavem. Èili se budeme sna¾it jméno stavu zkracovat zleva tak dlouho, ne¾ dostaneme
272 opìt jméno stavu. Z~koøene -- prázdného stavu -- pak evidentnì ¾ádná zpìtná hrana nepovede.
274 Funkce pro hledání v~senì bude vypadat stejnì jako u~KMP: zaène v~poèáteèním
275 stavu (to je koøen stromu), postupnì bude roz¹iøovat seno o~dal¹í písmenka,
276 poka¾dé zkusí jít dopøednou hranou a pokud to nejde, bude se vracet po~zpìtných
277 hranách tak dlouho, a¾ buïto bude existovat vhodná dopøedná hrana, nebo se vrátí
278 do koøene stromu a tehdy nový znak zahodí.
280 Stejnì jako u~KMP nahlédneme, ¾e procházení sena trvá $\O(S)$ a ¾e platí analogický
281 invariant, toti¾ ¾e se v~ka¾dém okam¾iku nacházíme ve~stavu, který odpovídá nejdel¹ímu
282 suffixu zatím pøeèteného sena, který je prefixem nìkteré jehly.
285 Jediné, co se bude od KMP li¹it, je, kdy ohlásit výskyt. U~KMP to bylo snadné: kdykoliv
286 jsme dospìli do posledního stavu, znamenalo to nalezení jehly. Nabízí se hlásit
287 výskyt, kdykoliv dojdeme do stavu oznaèeného jako koncový. To ale nefunguje:
288 pokud ná¹ ukázkový automat pøeète seno |bara|, skonèí ve stavu~|bara|, a~pøitom
289 by mìl ohlásit výskyt jehly |ara|. Stejnì tak pøeèteme-li |barbara|, nev¹imneme
290 si, ¾e na tém¾e místì konèí i |ara|.
292 Platí ale, ¾e v¹echna slova, která bychom mìli v~daném stavu ohlásit, jsou suffixy
293 jména tohoto stavu. Mohli bychom je tedy najít tak, ¾e se vydáme po zpìtných hranách
294 a¾ do koøene a kdykoliv projdeme pøes koncový vrchol, ohlásíme výskyt. To ov¹em
295 trvá pøíli¹ dlouho -- jistì by se stávalo, ¾e bychom podnikli dlouhou cestu do koøene
296 a nena¹li na ní ani jeden výskyt.
298 Dal¹í, co se nabízí, je pøedpoèítat si pro ka¾dý stav~$\beta$ mno¾inu slov ${\cal S}(\beta)$,
299 jejich¾ výskyty máme v~tomto stavu hlásit. To by fungovalo, ale existují mno¾iny jehel,
300 pro které bude celková velikost mno¾in ${\cal S}(\beta)$ superlineární. Museli bychom se
301 tedy vzdát lákavé mo¾nosti stavby automatu v~lineárním èase. (Rozmyslete si, jak by
302 takové jehly vypadaly.)
304 Jak to tedy vyøe¹íme? Zavedeme zkratky (na obrázku zelenì):
307 {\I Zkratková hrana} ze~stavu~$\alpha$ vede do nejbli¾¹ího stavu $\zeta(\alpha)$ dosa¾itelného
308 z~$\alpha$ po zpìtných hranách, který je koncový.
310 Jinými slovy, $\zeta(\alpha)$ nám øekne, jaký je nejdel¹í vlastní suffix slova~$\alpha$, který
311 je jehlou. Pokud takový suffix neexistuje, ¾ádná zkratková hrana ze~stavu~$\alpha$ nepovede.
312 Pomocí zkratkových hran mù¾eme snadno vyjmenovat v¹echny výskyty. Budeme postupovat stejnì,
313 jako bychom procházeli po v¹ech zpìtných hranách, jen budeme dlouhé úseky zpìtných hran, na~nich¾
314 není nic k~hlá¹ení, pøeskakovat v~konstantním èase.
316 \s{Reprezentace automatu:}
317 Vyhledávací automat se tedy sestává ze stromu dopøedných hran, ze zpìtných
318 hran a ze~zkratkových hran. Ne¾ vyslovíme samotný algoritmus AC, rozmysleme si, jak automat
319 ulo¾it do pamìti. Pro ka¾dý stav si budeme pamatovat:
321 \:$I$ -- poøadové èíslo stavu (tøeba v~poøadí, jak vrcholy vznikaly),
322 \:$\<Zpìt>(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
323 èíslo stavu, do nìj¾ vede),
324 \:$\<Zkratka>(I)$ -- kam z~nìj vede zkratková hrana (takté¾),
325 \:$\<Slovo>(I)$ -- zda tu konèí nìjaké slovo (a~pokud ano, tak které),
326 \:$\<Dopøedu>(I,x)$ -- kam vede dopøedná hrana oznaèená písmenem~$x$ (pro malé abecedy si to
327 mù¾eme pamatovat v~poli, pro velké tøeba v~he¹ovací tabulce nebo stromu).
330 \>Celý algoritmus pro zpracování sena automatem pak bude vypadat takto:
332 \s{Krok($I$, $x$):} \cmt{Jeden krok automatu: jsme ve stavu~$I$, pøeèetli jsme znak~$x$.}
334 \:Dokud $\<Dopøedu>(I, x) = \emptyset~\&~I \ne \<koøen>$: $I \leftarrow \<Zpìt>(I)$.
335 \:Pokud $\<Dopøedu>(I, x) \ne \emptyset$: $I \leftarrow \<Dopøedu>(I,x)$.
336 \:Vrátíme nový stav~$I$.
339 \s{Hledej($\sigma$):} \cmt{Spu¹tìní automatu na øetìzec~$\sigma$.}
341 \:$I \leftarrow \<koøen>$.
342 \:Pro znaky $x\in\sigma$ postupnì provádíme:
343 \::$I \leftarrow \<Krok>(I, x)$.
345 \::Dokud $K \neq \emptyset$:
346 \:::Je-li $\<Slovo>(K) \neq \emptyset$:
347 \::::Ohlásíme $\<Slovo>(K)$.
348 \:::$K \leftarrow \<Zkratka>(K)$.
351 \>Jak u¾ jsme nahlédli, v¹echny kroky automatu dohromady trvají $\O(S)$.
352 Mimo to je¹tì hlásíme výskyty, co¾ trvá $\O(\<poèet výskytù>)$. Zbývá
353 ukázat, jak automat sestrojit.
355 \h{XXX --- Pod tímto místem nepøepsáno --- XXX}
357 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.
359 \s{Konstrukce automatu:}
361 \:Zalo¾íme prázdný strom, $r \leftarrow$ jeho koøen.
362 \:Vlo¾íme do~stromu slova $\iota_1 \dots \iota_n$, nastavíme $slovo(*)$.
363 \:$z(r) \leftarrow \emptyset$, $out(r) \leftarrow \emptyset$.
364 \:Zalo¾íme frontu $F$ a~vlo¾íme do~ní syny koøene.
365 \:$\forall v~\in F:~~z(v) \leftarrow r, \<out>(v) \leftarrow \emptyset$.
366 \:Dokud $F \neq \emptyset$:
367 \::Vybereme $u$ z~fronty $F$.
368 \::Pro v¹echny syny $v$ vrcholu $u$:
369 \:::$q \leftarrow \<Krok>(z(u), \<písmeno na~hranì uv>)$.
370 \:::$z(v) \leftarrow q$.
371 \:::Pokud $slovo(q) \neq \emptyset$, pak $out(v) \leftarrow q$.
372 \::::Jinak $out(v) \leftarrow out(q)$.
373 \:::Vlo¾íme $v$ do~fronty $F$.
376 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)$.
378 \s{Vìta:} Algoritmus Aho-Corasicková najde v¹echny výskyty v~èase
379 $$\O\left(\sum_i~\iota_i~+~S~+~\sharp\<výskytù>\right).$$
381 \h{Rabinùv-Karpùv algoritmus}
383 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í.
386 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.
388 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})$.
389 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í.
391 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ù}).
393 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:
394 $$h(x_1 \dots x_j) := \left(\sum_{I=1}^{J} x_I \cdot p^{J-I}\right) \bmod N.$$
395 Jinak zapsáno se tedy jedná o:
396 $$(x_1 \cdot p^{J-1} + x_2 \cdot p^{J-2} + \dots + x_J \cdot p^0 ) \bmod N.$$
397 Po posunutí okénka o~jedna chceme dostat:
398 $$(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.$$
399 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:
400 $$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.$$
401 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.
403 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).
405 %% Cvièení: velké abecedy
projects / ads2.git / blob