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 \proc{KmpKrok} \cmt{Jeden krok automatu}
132 \algin Jsme ve~stavu~$I$, pøeèetli jsme znak~$x$.
133 \:Dokud $\iota[I] \neq x~\&~I \neq 0: I \= Z[I]$.
134 \:Pokud $\iota[I] = x$, pak $I \= I + 1$.
135 \algout Nový stav~$I$.
138 \algo{Kmp} \cmt{Spu¹tìní automatu na øetìzec~$\sigma$.}
139 \algin Seno~$\sigma$, zkonstruovaný automat.
141 \:Pro znaky $x\in\sigma$ postupnì provádíme:
142 \::$I \= \alg{KmpKrok}(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ì:
217 \algin Jehla~$\iota$ délky~$J$.
218 \:$Z[0] \= ?$, $Z[1] \= 0$.
220 \:Pro $K = 2, \ldots, J-1$:
221 \::$I \= \alg{KmpKrok}(I, \iota[K])$.
223 \algout Pole zpìtných hran~$Z$.
226 \>Výsledky mù¾eme shrnout do následující vìty:
228 \s{Vìta:} Algoritmus KMP najde v¹echny výskyty v~èase $O(J+S)$.
231 Lineární èas s~délkou jehly potøebujeme na~postavení automatu, lineární èas
232 s~délkou sena pak potøebujeme na~samotné vyhledání.
235 \h{Hledání více øetìzcù najednou: algoritmus Aho-Corasicková}
237 Nyní si zahrajeme tuté¾ hru, ov¹em v~trochu slo¾itìj¹ích kulisách. Tentokrát
238 bude jehel vícero: $\iota_1, \ldots, \iota_N$, jejich délky oznaèíme $J_I = \vert \iota_I \vert $.
239 Opìt dostaneme nìjaké seno~$\sigma$ délky $S=\vert \sigma \vert$ a chceme nalézt
240 v¹echny výskyty jehel v~senì.
242 Pøedtím, ne¾ se pustíme do~vlastního vyhledávacího algoritmu, mìli bychom si
243 ujasnit, co bude jeho výstupem. Dokud byla jehla jedna jediná, bylo to jasné --
244 chtìli jsme nalézt mno¾inu v¹ech pozic v~senì, na~kterých zaèínaly výskyty
245 jehly. Jak tomu bude zde? Budeme chtít vìdìt, která jehla se vyskytuje na které
246 pozici. Jinými slovy budeme chtít vypsat v¹echny dvojice $(K,I)$ takové,
247 ¾e $\sigma[K:K+J_I]= \iota_I$.
249 Zde se v¹ak skrývá jedna drobná zrada. Budeme se asi muset vzdát nadìje
250 na algoritmus, jeho¾ slo¾itost je lineární v~celkové délce v¹ech jehel
251 a~sena. Výstup toti¾ mù¾e být del¹í ne¾ lineární. Pokud je toti¾ jedna
252 jehla suffixem druhé, na jedné pozici v~senì mohou konèit výskyty obou.
253 Proto budeme hledat algoritmus, který bude lineární v~délce vstupu plus
254 délce výstupu, co¾ je evidentnì to nejlep¹í, èeho mù¾eme dosáhnout.
256 Algoritmus, který si nyní uká¾eme, objevili v~roce 1975 pan Aho a~paní
257 Corasicková. Je elegantním zobecnìním Knuthova-Morrisova-Prattova algoritmu pro
260 \s{Vyhledávací automat:}
261 Opìt se budeme sna¾it sestrojit vyhledávací automat, jeho¾ stavy budou
262 odpovídat prefixùm jehel a dopøedné hrany roz¹iøování prefixù o~jeden znak.
263 Tentokrát navíc nebude jasnì definovaný koncový stav, oznaèíme si proto
264 v¹echny stavy, které odpovídají nìkteré z~jehel (na pøíkladu na obrázku
265 je vidìt, ¾e to nemusí být jen listy).
267 \figure{ara_strom_zkr.eps}{Vyhledávací automat pro slova |ara|, |bar|, |arab|, |baraba| a |barbara|.}{1.25in}
269 Dále potøebujeme zpìtné hrany (na obrázku èerné ¹ipky).
270 Jejich definice bude úplnì stejná jako u~automatu KMP.
271 Z~ka¾dého stavu pùjde zpìtná hrana do~jeho nejdel¹ího vlastního suffixu, který je také
272 stavem. Èili se budeme sna¾it jméno stavu zkracovat zleva tak dlouho, ne¾ dostaneme
273 opìt jméno stavu. Z~koøene -- prázdného stavu -- pak evidentnì ¾ádná zpìtná hrana nepovede.
275 Funkce pro hledání v~senì bude vypadat stejnì jako u~KMP: zaène v~poèáteèním
276 stavu (to je koøen stromu), postupnì bude roz¹iøovat seno o~dal¹í písmenka,
277 poka¾dé zkusí jít dopøednou hranou a pokud to nejde, bude se vracet po~zpìtných
278 hranách tak dlouho, a¾ buïto bude existovat vhodná dopøedná hrana, nebo se vrátí
279 do koøene stromu a tehdy nový znak zahodí.
281 Stejnì jako u~KMP nahlédneme, ¾e procházení sena trvá $\O(S)$ a ¾e platí analogický
282 invariant, toti¾ ¾e se v~ka¾dém okam¾iku nacházíme ve~stavu, který odpovídá nejdel¹ímu
283 suffixu zatím pøeèteného sena, který je prefixem nìkteré jehly.
286 Jediné, co se bude od KMP li¹it, je, kdy ohlásit výskyt. U~KMP to bylo snadné: kdykoliv
287 jsme dospìli do posledního stavu, znamenalo to nalezení jehly. Nabízí se hlásit
288 výskyt, kdykoliv dojdeme do stavu oznaèeného jako koncový. To ale nefunguje:
289 pokud ná¹ ukázkový automat pøeète seno |bara|, skonèí ve stavu~|bara|, a~pøitom
290 by mìl ohlásit výskyt jehly |ara|. Stejnì tak pøeèteme-li |barbara|, nev¹imneme
291 si, ¾e na tém¾e místì konèí i |ara|.
293 Platí ale, ¾e v¹echna slova, která bychom mìli v~daném stavu ohlásit, jsou suffixy
294 jména tohoto stavu. Mohli bychom je tedy najít tak, ¾e se vydáme po zpìtných hranách
295 a¾ do koøene a kdykoliv projdeme pøes koncový vrchol, ohlásíme výskyt. To ov¹em
296 trvá pøíli¹ dlouho -- jistì by se stávalo, ¾e bychom podnikli dlouhou cestu do koøene
297 a nena¹li na ní ani jeden výskyt.
299 Dal¹í, co se nabízí, je pøedpoèítat si pro ka¾dý stav~$\beta$ mno¾inu slov ${\cal S}(\beta)$,
300 jejich¾ výskyty máme v~tomto stavu hlásit. To by fungovalo, ale existují mno¾iny jehel,
301 pro které bude celková velikost mno¾in ${\cal S}(\beta)$ superlineární. Museli bychom se
302 tedy vzdát lákavé mo¾nosti stavby automatu v~lineárním èase. (Rozmyslete si, jak by
303 takové jehly vypadaly.)
305 Jak to tedy vyøe¹íme? Zavedeme zkratky (na obrázku zelenì):
308 {\I Zkratková hrana} ze~stavu~$\alpha$ vede do nejbli¾¹ího stavu $\zeta(\alpha)$ dosa¾itelného
309 z~$\alpha$ po zpìtných hranách, který je koncový.
311 Jinými slovy, $\zeta(\alpha)$ nám øekne, jaký je nejdel¹í vlastní suffix slova~$\alpha$, který
312 je jehlou. Pokud takový suffix neexistuje, ¾ádná zkratková hrana ze~stavu~$\alpha$ nepovede.
313 Pomocí zkratkových hran mù¾eme snadno vyjmenovat v¹echny výskyty. Budeme postupovat stejnì,
314 jako bychom procházeli po v¹ech zpìtných hranách, jen budeme dlouhé úseky zpìtných hran, na~nich¾
315 není nic k~hlá¹ení, pøeskakovat v~konstantním èase.
317 \s{Reprezentace automatu:}
318 Vyhledávací automat se tedy sestává ze stromu dopøedných hran, ze zpìtných
319 hran a ze~zkratkových hran. Ne¾ vyslovíme samotný algoritmus AC, rozmysleme si, jak automat
320 ulo¾it do pamìti. Pro ka¾dý stav si budeme pamatovat:
322 \:$I$ -- poøadové èíslo stavu (tøeba v~poøadí, jak vrcholy vznikaly),
323 \:$\<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
324 èíslo stavu, do nìj¾ vede),
325 \:$\<Zkratka>(I)$ -- kam z~nìj vede zkratková hrana (takté¾),
326 \:$\<Slovo>(I)$ -- zda tu konèí nìjaké slovo (a~pokud ano, tak které),
327 \:$\<Dopøedu>(I,x)$ -- kam vede dopøedná hrana oznaèená písmenem~$x$ (pro malé abecedy si to
328 mù¾eme pamatovat v~poli, pro velké tøeba v~he¹ovací tabulce nebo stromu).
331 \>Celý algoritmus pro zpracování sena automatem pak bude vypadat takto:
333 \proc{AcKrok} \cmt{Jeden krok automatu}
334 \algin Jsme ve~stavu~$I$, pøeèetli jsme znak~$x$.
335 \:Dokud $\<Dopøedu>(I, x) = \emptyset~\&~I \ne \<koøen>$: $I \= \<Zpìt>(I)$.
336 \:Pokud $\<Dopøedu>(I, x) \ne \emptyset$: $I \= \<Dopøedu>(I,x)$.
337 \algout Nový stav~$I$.
340 \algo{AcHledej} \cmt{Spu¹tìní automatu na daný øetìzec}
341 \algin Seno~$\sigma$, zkonstruovaný automat.
343 \:Pro znaky $x\in\sigma$ postupnì provádíme:
344 \::$I \= \alg{AcKrok}(I, x)$.
346 \::Dokud $K \neq \emptyset$:
347 \:::Je-li $\<Slovo>(K) \neq \emptyset$:
348 \::::Ohlásíme $\<Slovo>(K)$.
349 \:::$K \= \<Zkratka>(K)$.
352 \>Jak u¾ jsme nahlédli, v¹echny kroky automatu dohromady trvají $\O(S)$.
353 Mimo to je¹tì hlásíme výskyty, co¾ trvá $\O(\<poèet výskytù>)$. Zbývá
354 ukázat, jak automat sestrojit.
356 \s{Konstrukce automatu:}
357 Stejnì jako u~KMP, i zde nahlédneme, ¾e zpìtná hrana ze stavu $\beta$ vede tam,
358 kam by se dostal automat pøi hledání slova $\beta$ bez prvního znaku. Opìt bychom
359 tedy chtìli zaèít sestrojením dopøedných hran a pak spu¹tìním je¹tì nehotového
360 automatu doplòovat hrany zpìtné, doufajíce, ¾e si vystaèíme s~u¾ sestrojenou
363 Pøi konstrukci zpìtných hran tedy chceme automatem vyhledávat v¹echny jehly
364 bez prvních znakù. To v¹ak nemù¾eme dìlat jednu jehlu po druhé, proto¾e zpìtné
365 hrany mohou vést køí¾em mezi jednotlivými vìtvemi stromu. Mohlo by se nám tedy
366 stát, ¾e pøi hledání nìjakého slova potøebujeme zpìtnou hranu, která vede
367 do~jiného slova, které jsme je¹tì nezkonstruovali. Proto tento postup sel¾e.
369 Mù¾eme v¹ak vyu¾ít toho, ¾e ka¾dá zpìtná hrana vede ve~stromu alespoò o~jednu
370 hladinu vý¹, a strom konstruovat po~hladinách. To si lze pøedstavit tak, ¾e
371 paralelnì spustíme vyhledávání v¹ech slov bez prvních písmenek a~v¾dycky udìláme
372 jeden krok ka¾dého z~tìchto hledání, co¾ nám dá zpìtné hrany v~dal¹ím patøe stromu.
374 Kdykoliv vytvoøíme zpìtnou hranu, sestrojíme také zkratkovou hranu z~tého¾
375 vrcholu. Pokud vede zpìtná hrana z~$K$ do~$Q$ a $\<Slovo>(Q) \ne \emptyset$,
376 musí vést zkratka z~$K$ také do~$Q$. Pokud v~$Q$ ¾ádné slovo neskonèí, musí
377 zkratka z~$K$ vést do tého¾ vrcholu, jako zkratka z~$Q$.
380 \algin Slova $\iota_1,\ldots,\iota_N$.
381 \:Zalo¾íme prázdný strom, $R \=$ jeho koøen.
382 \:Vlo¾íme do~stromu slova $\iota_1 \dots \iota_N$, nastavíme $\<Slovo>$ ve~v¹ech stavech.
383 \:$\<Zpìt>(R) \= \emptyset$, $\<Zkratka>(R) \= \emptyset$.
384 \:Zalo¾íme frontu $F$ a~vlo¾íme do~ní syny koøene.
385 \:Pro v¹echny syny~$K$ koøene: $\<Zpìt>(K) \= R$, $\<Zkratka>(K) \= \emptyset$.
386 \:Dokud $F \neq \emptyset$:
387 \::Vybereme $I$ z~fronty $F$.
388 \::Pro v¹echny syny $K$ vrcholu $I$:
389 \:::$Q \= \alg{AcKrok}(\<Zpìt>(I), \hbox{písmeno na~hranì $IK$})$.
390 \:::$\<Zpìt>(K) \= Q$.
391 \:::Pokud $\<Slovo>(Q) \neq \emptyset$: $\<Zkratka>(K) \= Q$.
392 \:::Jinak $\<Zkratka>(K) \= \<Zkratka>(Q)$.
393 \:::Vlo¾íme $K$ do~fronty $F$.
394 \algout Strom, pole \<Slovo>, \<Zpìt> a \<Zkratka>.
397 Jeliko¾ tento algoritmus pouze napøeskáèku hledá v¹echny jehly, musí být jeho
398 èasová slo¾itost shora omezena souètem slo¾itostí hledání jehel, co¾, jak u¾
399 víme, je pro ka¾dou jehlu lineární s~její délkou. Dokonce mù¾e dobìhnout i
400 rychleji, jeliko¾ jsou-li dva ze simulovaných výpoètù v~tém¾e stavu, poèítáme
401 krok automatu pouze jednou (to je vidìt tøeba na spoleèném zaèátku slov |araba|
404 Chování celého algoritmu shrneme do následující vìty:
406 \s{Vìta:} Algoritmus Aho-Corasicková najde v¹echny výskyty v~èase
407 $\O\left(\sum_i J_i + S + V \right)$, kde $J_1,\ldots,J_n$ jsou délky
408 jednotlivých jehel, $S$ je délka sena a $V$ poèet ohlá¹ených výskytù.
410 \h{Rabinùv-Karpùv algoritmus}
412 Nyní si uká¾eme je¹tì jeden algoritmus na~hledání jedné jehly, tentokrát
413 zalo¾ený na he¹ování. Aèkoliv jeho èasová slo¾itost v~nejhor¹ím pøípadì
414 bude srovnatelná s~hledáním hrubou silou, v~prùmìru bude lineární a v~praxi
415 èasto pobì¾í rychleji ne¾ KMP.
417 Pøedstavme si, ¾e máme seno délky $S$ a~jehlu délky $J$. Poøídíme si nìjakou
418 he¹ovací funkci~$H$, které $J$-ticím znakù pøiøazuje èísla z~mno¾iny $\{0,\ldots,N-1\}$
419 pro nìjaké dost velké~$N$. Budeme posouvat okénko délky~$J$ po~senì, pro ka¾dou
420 jeho polohu si spoèteme he¹ znakù uvnitø okénka, porovnáme s~he¹em jehly a pokud
421 se rovnají, porovnáme je znak po~znaku.
423 Pokud je he¹ovací funkce \uv{kvalitní}, málokdy se stane, ¾e by se he¹e rovnaly,
424 tak¾e místo èasu $\Theta(J)$ na porovnáváním øetìzcù si vystaèíme s~porovnáním
425 he¹ù v~konstantním èase. Jen¾e ouha, èas $\Theta(J)$ potøebujeme i na vypoètení
426 he¹e pro ka¾dou polohu okénka, tak¾e jsme si nepomohli.
428 Poøídíme si proto he¹ovací funkci, kterou lze pøi posunutí okénka o~jednu
429 pozici doprava v~konstantním èase pøepoèítat. Tyto po¾adavky splòuje tøeba
432 H(x_1,\ldots,x_J) = (x_1P^{J-1} + x_2P^{J-2} + \ldots + x_{J-1}P^1 + x_JP^0) \bmod N,
434 pøièem¾ písmena pova¾ujeme za pøirozená èísla a $P$ je nìjaká vhodná konstanta -- potøebujeme,
435 aby byla nesoudìlná s~$N$ a aby $P^J$ bylo øádovì vìt¹í ne¾~$N$.
436 Posuneme-li nyní okénko z~$x_1,\ldots,x_J$ na $x_2,\ldots,x_{J+1}$, he¹ se zmìní takto:
438 H(x_2,\ldots,x_{J+1}) &= (x_2P^{J-1} + x_3P^{J-2} + \ldots + x_JP^1 + x_{J+1}P^0) \bmod N \cr
439 &= (P\cdot H(x_1,\ldots,x_J) - x_1P^J + x_{J+1}) \bmod N. \cr
441 Pokud si mocninu $P^J$ pøepoèítáme, probìhne aktualizace he¹e v~konstantním èase.
443 Celý algoritmus pak bude vypadat následovnì:
446 \algin Jehla $\iota$ délky~$J$, seno~$\sigma$ délky~$S$.
447 \:$X \= H(\iota)$. \cmt{he¹ jehly}
448 \:$Y \= H(\sigma[{}:J])$. \cmt{he¹ první pozice okénka}
449 \:Zvolíme~$P$ a~$N$ a pøedpoèítáme $P^J \bmod N$.
450 \:Pro $I$ od~$0$ do~$S-J$: \cmt{mo¾né pozice okénka}
452 \:::Pokud $\sigma[I:I+J] = \iota$, ohlásíme výskyt na pozici~$I$.
453 \::Pokud $I<S-J$: \cmt{pøepoèítáme he¹}
454 \:::$X \= (P\cdot X - \sigma[I]\cdot P^J + \sigma[I+J]) \bmod N$.
458 V~nejhor¹ím pøípadì pro ka¾dou pozici okénka porovnáváme øetìzce a celý
459 algoritmus spotøebuje èas $\Theta(JS)$. Abychom zjistili, jak tomu bude
460 v~prùmìrném pøípadì, odhadnìme pravdìpodobnost porovnání.
462 Pøedev¹ím pokud nastane výskyt, urèitì porovnáváme. Nenastane-li, he¹ jehly
463 se shoduje s~he¹em okénka s~pravdìpodobností $1/N$ (za~pøedpokladu dokonale
464 náhodného chování he¹ovací funkce, co¾ té na¹í budeme vìøit, aèkoliv jsme
465 to poøádnì nedokázali).
467 V~prùmìru tedy spotøebujeme èas $\O(S + VJ + S/N\cdot J)$, kde $V$ je poèet
468 nalezených výskytù. Pokud nám bude staèit najít první výskyt a zvolíme $N > SJ$,
469 algoritmus pobì¾í v~prùmìrném èase $\O(S)$.
473 \ex{Naivní algoritmus, který zkou¹í v¹echny mo¾né zaèátky jehly v~senì a v¾dy
474 porovnává øetìzce, má èasovou slo¾itost $\O(JS)$. Mù¾e být opravdu tak pomalý,
475 uvá¾íme-li, ¾e porovnávání øetìzcù skonèí, jakmile najde první neshodu? Sestrojte
476 vstup, na kterém algoritmus pobì¾í $\Theta(JS)$ krokù, pøesto¾e nic nenajde.}
478 \ex{Naleznìte pøíklad jehel a sena, v~nìm¾ se nachází superlineární poèet
479 výskytù vzhledem k~celkové velikosti vstupu (souèet velikostí jehel a délky
482 \ex{Uva¾ujme zjednodu¹ený algoritmus AC, který nepou¾ívá zkratkové hrany
483 a v¾dy projde po zpìtných hranách a¾ do koøene. Uka¾te pøíklad vstupu,
484 na~kterém je tento algoritmus asymptoticky pomalej¹í.}
486 \ex{Oznaème $M(S)$ mno¾inu øetìzcù, jejich¾ výskyty algoritmus AC ohlásí
487 ve~stavu~$S$. Uka¾te, ¾e kdybychom si mìli v¹echny mno¾iny $M(S)$ pamatovat
488 explicitnì, budeme pro nìkteré vstupy potøebovat superlineární mno¾ství
489 prostoru vzhledem k~velikosti vstupu, tak¾e automat nepùjde sestrojit
492 \ex{Rozmyslete si, ¾e mno¾iny $M(S)$ z~pøedchozího pøíkladu by bylo mo¾né
493 reprezentovat jako srùstající spojové seznamy -- tedy takové, kde si ka¾dý
494 prvek pamatuje ukazatel na svého následníka, který ov¹em mù¾e le¾et v~jiném
495 seznamu. Uka¾te, ¾e námi zavedené zkratkové hrany lze interpretovat jako
496 v~takových seznamech.}
498 \ex{Rozmyslete si, jak algoritmy z~této kapitoly upravit, aby si poradily
499 s~velkými abecedami.}
501 \ex{Upravte algoritmus AC, aby pro ka¾dou pozici v~senì vypsal nejdel¹í
502 tam konèící jehlu, a~to efektivnìji ne¾ vyjmenováním v¹ech jehel. Jak se
503 algoritmus zmìní, budeme-li chtít vypsat nejdel¹í jehlu, která na dané
506 \ex{Mìjme seno a jehly. Popi¹te algoritmus, který v~lineárním èase pro ka¾dou
507 jehlu spoèítá, kolikrát se v~senì vyskytuje. Èasová slo¾itost by nemìla záviset
508 na poètu výskytù -- ten, jak u¾ víme, mù¾e být superlineární.}
510 \ex{Cenzor dostane mno¾inu zakázaných podøetìzcù a text. V¾dy najde nejlevìj¹í
511 výskyt zakázaného podøetìzce v~textu (s~nejlevìj¹ím koncem; pokud jich je více,
512 tak nejdel¹í takový), vystøihne ho a postup opakuje. Uka¾te, jak text cenzurovat
515 \ex{Rotací øetìzce~$\alpha$ o~$K$ pozic nazýváme øetìzec $\alpha[K:{}]\alpha[{}:K]$.
516 Jak o~dvou øetìzcích zjistit, zda je jeden rotací druhého?}
518 \ex{Jak v~lineárním èase zrotovat øetìzec, dostaèuje-li pamì» poèítaèe jen
519 na ulo¾ení jedhoho øetìzce a $\O(1)$ pomocných promìnných?}
521 \ex{Navrhnìte algoritmus, který v~lineárním èase nalezne tu z~rotací zadaného
522 øetìzce, je¾ je lexikograficky minimální.}
524 \ex{Navrhnìte datovou strukturu pro básníky, která si bude pamatovat slovník
525 a bude umìt hledat rýmy. Tedy pro libovolné zadané slovo najde takové slovo
526 ve~slovníku, které má se zadaným nejdel¹í spoleèný suffix.}
528 \exx{Upravte datovou strukturu z~pøedchozího cvièení, aby je-li nejlep¹ích rýmù
529 více, vypsala lexikograficky nejmen¹í z~nich.}
531 \ex{Jak reprezentovat slovník, abyste umìli rychle vyhledávat v¹echny
532 pøesmyèky zadaného slova?}
534 \exx{Je dán text a èíslo~$K$. Jak zjistit, který podøetìzec délky~$K$
535 se v~textu vyskytuje nejèastìji?}
537 \exx{Sestrojte co nejefektivnìj¹í algoritmus, který v~daném øetìzci najde
538 nejdel¹í podøetìzec, který se vyskytuje vícekrát.}
540 \exx{Uka¾te, jak pro dané dva øetìzce najít jejich nejdel¹í spoleèný
543 \ex{Definujme Fibonacciho slova takto: $F_0=|a|$, $F_1=|b|$, $F_{n+2}=F_nF_{n+1}$.
544 Jak pro zadaný øetìzec nad abecedou $\{|a|,|b|\}$ najít nejdel¹í Fibonacciho podslovo?
547 \exx{Pokraèujme v~pøedchozím cvièení. Dostaneme-li øetìzec nad nìjakou obecnou abecedou,
548 jak nalézt jeho nejdel¹í podøetìzec, který je isomorfní s~nìjakým Fibonacciho slovem
549 (li¹í se pouze substitucí jiných znakù za |a| a~|b|)?}
551 \ex{Je dáno slovo. Chceme nalézt jeho nejdel¹í prefix, který je souèasnì suffixem.}
projects / ads2.git / blob