3 \prednaska{1}{Vyhledávání v~textu}{}
7 Uva¾ujme následující úlohu: máme nìjaký text~$\sigma$ délky~$S$ (budeme mu øíkat {\I seno}) a
8 chceme v~nìm najít v¹echny výskyty nìjakého podøetìzce~$\iota$ délky~$J$ ({\I jehly}). Seno pøitom bude øádovì del¹í
11 Kupøíkladu v~senì |bananas| se jehla |ana| vyskytuje hned dvakrát, pøièem¾
12 výskyty se pøekrývají.
14 Triviální øe¹ení pøesnì podle definice by vypadalo následovnì: Zkusíme v¹echny mo¾né pozice,
15 kde by se v~senì mohla jehla nacházet, a pro ka¾dou z~nich otestujeme, zda tam opravdu je.
16 Pozic je øádovì~$S$, ka¾dé porovnání stojí a¾~$J$, celkovì tedy algoritmus bì¾í v~èase
17 $\O(SJ)$. (Rozmyslete si, jak by vypadaly vstupy, pro které skuteènì spotøebujeme tolik èasu
18 -- viz cvièení \exref{naivejs}.)
20 Zkusme jiný pøístup: nalezneme v~senì první znak jehly a od tohoto místa budeme porovnávat
21 dal¹í znaky. Pokud se pøestanou shodovat, pøepneme opìt na hledání prvního znaku. Jen¾e odkud?
22 Pokud od místa, kde nastala neshoda, sel¾e to tøeba pøi hledání jehly |kokos| v~senì |clanekokokosu|
23 -- neshoda nastane za~|koko| a zbylý |kos| nás neuspokojí. Nebo se mù¾eme vrátit a¾ k~výskytu
24 prvního znaku a pokraèovat tìsnì za ním, jen¾e to je toté¾, co dìlal triviální algoritmus,
25 tak¾e je to také stejnì pomalé.
27 V~této kapitole si uká¾eme algoritmus, který je o~trochu slo¾itìj¹í, ale nalezne v¹echny
28 výskyty v~èase $\O(S+J)$. Pak ho zobecníme, aby umìl hledat více rùzných jehel najednou.
32 Aby se nám o~øetìzcových algoritmech lépe psalo, udìlejme si nejprve poøádek
33 v~terminologii okolo øetìzcù.
37 \:{\I Abeceda $\Sigma$} je nìjaká koneèná mno¾ina, jejím prvkùm budeme øíkat {\I znaky}
38 (nìkdy té¾ {\I písmena}).
39 \:{\I $\Sigma^*$} je mno¾ina v¹ech {\I slov} neboli {\I øetìzcù} nad abecedou~$\Sigma$,
40 co¾ jsou koneèné posloupnosti znakù ze~$\Sigma$.
44 Abeceda mù¾e být tvoøena tøeba písmeny |a| a¾~|z| nebo bity |0| a~|1|.
45 Potkáme ov¹em i rozlehlej¹í abecedy: napøíklad dnes bì¾ná znaková sada UniCode
46 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
47 zpùsobem pou¾ívají øetìzce lingvisté: na èeský text se nìkdy dívají jako na~øetìzec
48 nad abecedou, její¾ znaky jsou èeská slova.
50 Pro na¹e úèely budeme pøedpokládat, ¾e abeceda je \uv{rozumnì malá}, èím¾ myslíme, ¾e
51 její velikost je konstantní a navíc dostateènì malá na to, abychom si mohli dovolit
52 ukládat do pamìti pole indexovaná znakem.
56 \:{\I Slova} budeme znaèit malými písmenky øecké abecedy $\alpha$, $\beta$, \dots
57 \:{\I Znaky} abecedy oznaèíme malými písmeny latinky |a|, |b|, \dots{} \hfil\break
58 Znak budeme pou¾ívat i ve~smyslu jednoznakového øetìzce.
59 \:{\I Délka slova} $\vert \alpha \vert$ udává, kolika znaky je slovo tvoøeno.
60 \:{\I Prázdné slovo} znaèíme písmenem $\varepsilon$, je to jediné slovo délky~0.
61 \:{\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$.
62 \:$\alpha[k]$ je $k$-tý znak slova $\alpha$, indexujeme od~$0$ do~$\vert\alpha\vert-1$.
63 \:$\alpha[k:\ell]$ je {\I podslovo} zaèínající $k$-tým znakem a konèící tìsnì pøed~$\ell$-tým.
64 Tedy $\alpha[k:\ell] = \alpha[k]\alpha[k+1]\ldots\alpha[\ell-1]$. Pokud $k\ge\ell$, je podslovo
65 prázdné. Pokud nìkterou z~mezí vynecháme, míní se $k=0$ nebo $\ell=\vert\alpha\vert$.
66 \:$\alpha[{}:\ell]$ je {\I prefix} (pøedpona) tvoøený prvními $\ell$ znaky øetìzce.
67 \:$\alpha[k:{}]$ je {\I suffix} (pøípona) od $k$-tého znaku do~konce øetìzce.
68 \:$\alpha[:] = \alpha$.
71 \>Dodejme je¹tì, ¾e ka¾dé slovo je prefixem sebe sama a prázdné slovo je
72 prefixem ka¾dého slova. Pokud budeme hovoøit o~{\I vlastním} suffixu, budeme
73 tím myslet suffix rùzný od~celého slova. Analogicky pro prefixy a podslova.
75 \h{Inkrementální algoritmus}
77 Vra»me se nyní zpìt k~pùvodnímu problému hledání podøetìzcù. Nejprve si
78 ujasnìme, co má být výstupem algoritmu. Budeme chtít nalézt mno¾inu v¹ech
79 indexù~$k$ takových, ¾e $\sigma[k:k+\vert\iota\vert] = \iota$. To je dostateènì
80 kompaktní výstup (nejvý¹e lineární s~délkou sena), a~pøitom obsahuje informace
83 Na hledání podøetìzce pou¾ijeme {\I inkrementální pøístup.} Tím se obecnì myslí,
84 ¾e chceme umìt roz¹íøit vstup o~dal¹í znak a pøepoèítat výstup. V~na¹em pøípadì
85 budeme pøidávat znak na konec sena a zapoèítáme pøípadný nový výskyt jehly, který
88 Abychom toho dosáhli, budeme si prùbì¾nì udr¾ovat informaci o~tom, jakým nejdel¹ím
89 prefixem jehly konèí zatím pøeètená èást sena. Tomu budeme øíkat {\I stav
90 algoritmu.} A~jakmile bude tento prefix roven celé jehle, ohlásíme výskyt.
92 V~na¹em \uv{kokosovém} pøíkladì se tedy po~pøeètení sena |clanekoko| nacházíme
93 ve~stavu |koko|, následují stavy |kok|, |koko| a |kokos|.
95 Pøedstavme si nyní obecnì, ¾e jsme pøeèetli øetìzec~$\sigma$, který konèil stavem~$\alpha$.
96 Teï vstup roz¹íøíme o~znak~$x$ na~$\sigma x$. V~jakém stavu se nyní máme
97 nacházet? Pokud to nebude prázdný øetìzec, musí konèit na~$x$, tedy ho mù¾eme
98 napsat ve~tvaru $\alpha'x$.
100 V¹imneme si, ¾e $\alpha'$ musí být suffixem slova~$\alpha$: Jeliko¾ $\alpha' x$
101 je prefix jehly, je $\alpha'$ také prefix jehly. A~proto¾e $\alpha'x$ je suffixem~$\sigma x$,
102 musí $\alpha'$ být suffixem~$\sigma$. Tedy jak~$\alpha$, tak $\alpha'$ jsou suffixy slova~$\alpha$,
103 které jsou souèasnì prefixy jehly. Ov¹em stav~$\alpha$ jsme vybrali jako nejdel¹í slovo
104 s~touto vlastností, tak¾e $\alpha'$~musí být nejvý¹e tak dlouhé, a~tudí¾ je prefixem~$\alpha$.
106 Staèilo by tedy probrat v¹echny suffixy slova~$\alpha$, které jsou prefixem jehly,
107 a~vybrat z~nich nejdel¹í, který po roz¹íøení o~znak~$x$ stále je prefixem jehly.
109 Abychom ale nemuseli suffixy procházet v¹echny, pøedpoèítáme si {\I zpìtnou funkci~$z$.}
110 Ta nám pro ka¾dý prefix jehly øekne, jaký je jeho nejdel¹í vlastní suffix,
111 který je opìt prefixem jehly. To nám umo¾ní procházet rovnou kandidáty na nový stav:
112 staèí probrat øetìzce $\alpha$, $z(\alpha)$, $z(z(\alpha))$, \dots{} a pou¾ít první,
113 který lze roz¹íøit o~znak~$x$. Pokud nepùjde roz¹íøit ani jeden z~tìchto kandidátù,
114 novým stavem bude prázdný øetìzec.
116 Na~této my¹lence je zalo¾en následující algoritmus.
118 \h{Knuthùv-Morrisùv-Prattùv algoritmus (KMP)}
120 Algoritmus se opírá o~{\I vyhledávací automat.} To je orientovaný graf, jeho¾
121 vrcholy ({\I stavy} automatu) odpovídají prefixùm jehly. Vrcholy jsou spojeny
122 hranami dvou druhù: {\I dopøedné} popisují roz¹íøení prefixu pøidáním jednoho písmene,
123 {\I zpìtné} vedou podle zpìtné funkce, tedy z~ka¾dého stavu do jeho nejdel¹ího
124 vlastního suffixu, který je opìt stavem.
126 \figure{barb.eps}{Vyhledávací automat pro slovo |barbarossa|}{4.1in}
128 Reprezentace automatu bude pøímoèará: stavy oèíslujeme od~0 do~$J$, dopøedná hrana
129 povede v¾dy ze stavu~$s$ do~$s+1$ a bude odpovídat roz¹íøení prefixu o~pøíslu¹ný
130 znak jehly, tedy o~$\iota[s]$. Zpìtné hrany si budeme pamatovat v~poli~$Z$, tedy
131 $Z[s]$ bude øíkat èíslo stavu, do~nìj¾ vede zpìtná hrana ze~stavu~$s$, pøípadnì
132 bude nedefinované, pokud taková hrana neexistuje.
134 Kdybychom takový automat mìli, mohli bychom pomocí nìj inkrementální algoritmus
135 z~pøedchozí sekce popsat následovnì:
137 \proc{KmpKrok} \cmt{Jeden krok automatu}
138 \algin Jsme ve~stavu~$s$, pøeèetli jsme znak~$x$.
139 \:Dokud $\iota[s] \neq x~\&~s \neq 0: s \= Z[s]$.
140 \:Pokud $\iota[s] = x$, pak $s \= s + 1$.
141 \algout Nový stav~$s$.
144 \algo{KmpHledej} \cmt{Spu¹tìní automatu na øetìzec~$\sigma$.}
145 \algin Seno~$\sigma$, zkonstruovaný automat.
147 \:Pro znaky $x\in\sigma$ postupnì provádíme:
148 \::$s \= \alg{KmpKrok}(s,x)$.
149 \::Pokud $s = J$, ohlásíme výskyt.
152 \s{Invariant:} Stav algoritmu~$s$ v~ka¾dém okam¾iku øíká, jaký nejdel¹í
153 prefix jehly je suffixem zatím pøeètené èásti sena. (To u¾ víme z~úvah
154 o~inkrementálním algoritmu.)
156 \s{Dùsledek:} Algoritmus ohlásí v¹echny výskyty. Pokud jsme toti¾ právì
157 pøeèetli poslední znak nìjakého výskytu, je celá jehla suffixem zatím
158 pøeètené èásti sena, tak¾e se musíme nacházet v~posledním stavu.
160 Jen musíme opravit drobnou chybu -- tìsnì poté, co ohlásíme výskyt, se
161 algoritmus zeptá na~dopøednou hranu z~posledního stavu. Ta ale
162 neexistuje. Napravíme to jednodu¹e: pøidáme fiktivní dopøednou hranu,
163 na~ní¾ je napsán znak odli¹ný od~v¹ech skuteèných znakù. Tím zajistíme,
164 ¾e se po této hranì nikdy nevydáme. Staèí tedy vhodnì dodefinovat $\iota[J]$.%
165 \foot{V jazyce C mù¾eme zneu¾ít toho, ¾e ka¾dý øetìzec je ukonèen znakem
168 \s{Lemma:} Funkce \<Hledej> bì¾í v~èase $\O(S)$.
171 Výpoèet funkce mù¾eme rozdìlit na prùchody dopøednými a zpìtnými hranami.
172 S~dopøednými je to snadné -- za~ka¾dý z~$S$ znakù sena projdeme po nejvý¹e
173 jedné dopøedné hranì. To o~zpìtných hranách neplatí, ale pomù¾e nám, ¾e ka¾dá
174 dopøedná hrana vede o~právì~1 stav doprava a ka¾dá zpìtná o~aspoò~1 stav
175 doleva. Proto je v¹ech prùchodù po~zpìtných hranách nejvý¹e tolik, kolik
176 jsme pro¹li dopøedných hran, tak¾e také nejvý¹e~$S$.
179 \ss{Konstrukce automatu}
181 Hledání tedy pracuje v~lineárním èase, zbývá domyslet, jak v~lineárním èase
182 sestrojit automat. Stavy a dopøedné hrany získáme triviálnì, se zpìtnými budeme
185 Podnikneme my¹lenkový pokus: Pøedstavme si, ¾e automat u¾ máme hotový, ale nevidíme,
186 jak vypadá uvnitø. Chtìli bychom zjistit, jak v~nìm vedou zpìtné hrany, ov¹em jediné,
187 co umíme, je spustit automat na nìjaký øetìzec a zjistit, v~jakém stavu skonèil.
189 Tvrdíme, ¾e pro zji¹tìní zpìtné hrany ze~stavu~$\alpha$ staèí automatu pøedlo¾it
190 øetìzec $\alpha[1:{}]$. Definice zpìtné funkce je toti¾ nápadnì podobná invariantu,
191 který jsme o~funkci \<Hledej> dokázali. Obojí hovoøí o~nejdel¹ím suffixu daného
192 slova, který je prefixem jehly. Jediný rozdíl je v~tom, ¾e v~pøípadì zpìtné funkce
193 uva¾ujeme pouze vlastní suffixy, zatímco invariant pøipou¹tí i nevlastní. To ov¹em
194 snadno vyøe¹íme \uv{ukousnutím} prvního znaku jména stavu.
196 Pokud chceme objevit v¹echny zpìtné hrany, staèí automat spou¹tìt postupnì
197 na øetìzce $\iota[1:1]$, $\iota[1:2]$, $\iota[1:3]$, atd. Jeliko¾ funkce \<Hledej>
198 je lineární, stálo by nás to dohromady $\O(J^2)$. Pokud si ale v¹imneme, ¾e ka¾dý
199 ze~zmínìných øetìzcù je prefixem toho následujícího, je jasné, ¾e staèí spustit
200 automat jen jednou na øetìzec $\iota[1:{}]$ a jen zaznamenávat, kterými stavy
203 To je zajímavé pozorování, øeknete si, ale jak nám pomù¾e ke~konstrukci automatu,
204 kdy¾ samo u¾ hotový automat potøebuje? Pomù¾e pìkný trik: pokud hledáme zpìtnou
205 hranu z~$i$-tého stavu, spou¹tíme automat na slovo délky~$i-1$, tak¾e se mù¾eme
206 dostat pouze do prvních~$i-1$ stavù a vùbec nám nevadí, ¾e v~tom $i$-tém je¹tì
207 není zpìtná hrana hotova.%
208 \foot{Konstruovat nìjaký objekt pomocí tého¾ objektu je osvìdèený postup, který
209 si u¾ vyslou¾il i svùj vlastní název. V~angliètinì se mu øíká {\I bootstrapping}
210 a z~tohoto názvu vzniklo bootování poèítaèù, proto¾e pøi nìm operaèní systém
211 zavádí do pamìti sám sebe. Kde se toto slovo vzalo? Bootstrap znamená èesky
212 {\I ¹truple} -- to je takové to oèko na patì boty, které usnadòuje nazouvání.
213 A~v~jednom z~pøíbìhù o~baronu Prá¹ilovi sly¹íme barona vyprávìt, jak se uvíznuv
214 v~ba¾inì zachránil tím, ¾e se vytáhl za ¹truple. Krásný popis bootování, není-li¾
217 Pøi konstrukci automatu tedy nejdøíve sestrojíme dopøedné hrany, naèe¾
218 rozpracovaný automat spustíme na øetìzec $\iota[1:{}]$ a podle toho,
219 jakými stavy bude procházet, doplníme zpìtné hrany. Jak u¾ víme, vyhledávání má
220 lineární slo¾itost, tak¾e celá konstrukce potrvá $\O(J)$.
222 Hotový algoritmus pro konstrukci automatu mù¾eme zapsat následovnì:
225 \algin Jehla~$\iota$ délky~$J$.
226 \:$Z[0] \= ?$, $Z[1] \= 0$.
228 \:Pro $i = 2, \ldots, J-1$:
229 \::$s \= \alg{KmpKrok}(s, \iota[i])$.
231 \algout Pole zpìtných hran~$Z$.
234 \>Výsledky mù¾eme shrnout do následující vìty:
236 \s{Vìta:} Algoritmus KMP najde v¹echny výskyty v~èase $O(J+S)$.
239 Lineární èas s~délkou jehly potøebujeme na~postavení automatu, lineární èas
240 s~délkou sena pak potøebujeme na~samotné vyhledání.
243 \h{Hledání více øetìzcù najednou: algoritmus Aho-Corasicková (AC)}
245 Nyní si zahrajeme tuté¾ hru v~trochu slo¾itìj¹ích kulisách. Tentokrát
246 bude jehel vícero: $\iota_1, \ldots, \iota_N$, jejich délky oznaèíme $J_i = \vert \iota_i \vert $.
247 Opìt dostaneme nìjaké seno~$\sigma$ délky~$S$ a chceme nalézt
248 v¹echny výskyty jehel v~senì.
250 Pøedtím, ne¾ se pustíme do~vlastního vyhledávacího algoritmu, mìli bychom si
251 opìt ujasnit, co bude jeho výstupem. Dokud byla jehla jedna jediná, bylo to zøejmé --
252 chtìli jsme nalézt mno¾inu v¹ech pozic v~senì, na~kterých zaèínaly výskyty
253 jehly. Jak tomu bude zde? Chceme se dozvìdìt, která jehla se vyskytuje na které
254 pozici. Jinými slovy vypsat v¹echny dvojice $(k,i)$ takové, ¾e $\sigma[k:k+J_i]= \iota_i$.
256 Tìchto dvojic mù¾e být pomìrnì hodnì. Pokud je toti¾ jedna jehla suffixem druhé,
257 na jedné pozici v~senì mohou konèit výskyty obou. Celková velikost výstupu
258 tak mù¾e být vìt¹í ne¾ lineární v~délce vstupu (viz cvièení~\exref{acslout}).
259 Budeme proto hledat algoritmus, který bude lineární v~délce vstupu plus
260 délce výstupu, co¾ je evidentnì to nejlep¹í, èeho mù¾eme dosáhnout.
262 Algoritmus, který si nyní uká¾eme, objevili v~roce 1975 pan Aho a~paní
263 Corasicková. Je elegantním zobecnìním Knuthova-Morrisova-Prattova algoritmu pro
266 \s{Vyhledávací automat:}
267 Opìt se budeme sna¾it sestrojit vyhledávací automat, jeho¾ stavy budou
268 odpovídat prefixùm jehel a dopøedné hrany budou popisovat roz¹iøování
269 prefixù o~jeden znak. Hrany tedy budou tvoøit strom orientovaný smìrem
270 od~koøene (písmenkový strom neboli trii pro daný slovník).
272 Ka¾dý list stromu bude odpovídat nìkteré z~jehel, ale jak je vidìt
273 na obrázku, nìkteré jehly se mohou vyskytovat i ve~vnitøních vrcholech
274 (pokud je jedna jehla prefixem jiné). Výskyty jehel ve~stromu si tedy
275 nìjak oznaèíme, pøíslu¹ným stavùm budeme øíkat {\I koncové.}
277 \figure{ara_strom_zkr.eps}{Vyhledávací automat pro slova |ara|, |bar|, |arab|, |baraba| a |barbara|.}{1.25in}
279 Dále potøebujeme zpìtné hrany (na obrázku èerné ¹ipky).
280 Jejich definice bude úplnì stejná jako u~automatu KMP.
281 Z~ka¾dého stavu pùjde zpìtná hrana do~jeho nejdel¹ího vlastního suffixu, který je také
282 stavem. Èili se budeme sna¾it jméno stavu zkracovat zleva tak dlouho, ne¾ dostaneme
283 jméno dal¹ího stavu. Z~koøene -- prázdného stavu -- pak evidentnì ¾ádná zpìtná hrana nepovede.
285 Funkce pro hledání v~senì bude vypadat stejnì jako u~KMP: zaène v~poèáteèním
286 stavu (to je koøen stromu) a postupnì bude roz¹iøovat seno o~dal¹í písmenka.
287 Poka¾dé zkusí jít dopøednou hranou a pokud to nepùjde, bude se vracet po~zpìtných
288 hranách. Pøitom se buïto dostane do vrcholu, kde vhodná dopøedná hrana existuje,
289 nebo se vrátí a¾ do koøene stromu a tehdy nový znak zahodí.
291 Stejnì jako u~KMP nahlédneme, ¾e procházení sena trvá $\O(S)$ a ¾e platí analogický
292 invariant, toti¾ ¾e se v~ka¾dém okam¾iku nacházíme ve~stavu, který odpovídá nejdel¹ímu
293 suffixu zatím pøeèteného sena, který je prefixem nìkteré jehly.
296 Jediné, co se bude od KMP li¹it, je, kdy ohlásit výskyt. U~KMP to bylo snadné: kdykoliv
297 jsme dospìli do posledního stavu, znamenalo to nalezení jehly. Nabízí se hlásit
298 výskyt, kdykoliv dojdeme do stavu oznaèeného jako koncový. To ale nefunguje:
299 pokud ná¹ ukázkový automat pøeète seno |bara|, skonèí ve stavu~|bara|, který není
300 koncový, a~pøitom by zde mìl ohlásit výskyt jehly |ara|. Stejnì tak pøeèteme-li |barbara|,
301 nev¹imneme si, ¾e na tém¾e místì konèí i |ara|.
303 Platí ale, ¾e v¹echna slova, která bychom mìli v~daném stavu ohlásit, jsou suffixy
304 jména tohoto stavu. Mohli bychom se tedy vydat po zpìtných hranách
305 a¾ do koøene a kdykoliv projdeme pøes koncový vrchol, ohlásit výskyt. To ov¹em
306 trvá pøíli¹ dlouho -- jistì by se stávalo, ¾e bychom podnikli dlouhou cestu do koøene
309 Dal¹í, co se nabízí, je pøedpoèítat si pro ka¾dý stav~$\beta$ mno¾inu slov $M(\beta)$,
310 jejich¾ výskyty máme v~tomto stavu hlásit. To by fungovalo, ale existují mno¾iny jehel,
311 pro které bude celková velikost mno¾in $M(\beta)$ superlineární (viz cvièení~\exref{acslm}).
312 Museli bychom se tedy vzdát lákavé mo¾nosti stavby automatu v~lineárním èase.
314 Jak to tedy vyøe¹íme? Zavedeme zkratky (na obrázku vyznaèeny zelenì):
317 {\I Zkratková hrana} ze~stavu~$\alpha$ vede do nejbli¾¹ího koncového stavu $\zeta(\alpha)$
318 dosa¾itelného z~$\alpha$ po zpìtných hranách.
320 Jinými slovy, zkratka $\zeta(\alpha)$ nám øekne, jaký je nejdel¹í vlastní suffix slova~$\alpha$, který
321 je jehlou. Pokud takový suffix neexistuje, ¾ádná zkratková hrana ze~stavu~$\alpha$ nepovede.
322 Pomocí zkratkových hran mù¾eme snadno vyjmenovat v¹echny výskyty. Budeme postupovat stejnì,
323 jako bychom procházeli po v¹ech zpìtných hranách, jen budeme dlouhé úseky zpìtných hran, na~nich¾
324 není nic k~hlá¹ení, pøeskakovat v~konstantním èase.
326 \s{Reprezentace automatu:}
327 Vyhledávací automat se tedy sestává ze stromu dopøedných hran, ze zpìtných
328 hran a ze~zkratkových hran. Rozmysleme si, jak v¹e ulo¾it do pamìti.
329 Pro ka¾dý stav si budeme pamatovat:
331 \:$s$ -- poøadové èíslo stavu (tøeba podle toho, jak vrcholy vznikaly),
332 \:$\<Zpìt>(s)$ -- kam z~nìj vede zpìtná hrana (vyu¾íváme toho, ze mù¾e být nejvý¹e jedna, tak¾e si zapamatujeme
333 èíslo stavu, do nìj¾ vede),
334 \:$\<Zkratka>(s)$ -- kam z~nìj vede zkratková hrana (takté¾),
335 \:$\<Slovo>(s)$ -- zda tu konèí nìjaké slovo (a~pokud ano, tak které),
336 \:$\<Dopøedu>(s,x)$ -- kam vede dopøedná hrana oznaèená písmenem~$x$ (pro malé abecedy si to
337 mù¾eme pamatovat v~poli, pro velké viz cvièení~\exref{bigsigma}).
340 \>Celý algoritmus pro zpracování sena automatem pak bude vypadat takto:
342 \proc{AcKrok} \cmt{Jeden krok automatu}
343 \algin Jsme ve~stavu~$s$, pøeèetli jsme znak~$x$.
344 \:Dokud $\<Dopøedu>(s, x) = \emptyset~\&~s \ne \<koøen>$: $s \= \<Zpìt>(s)$.
345 \:Pokud $\<Dopøedu>(s, x) \ne \emptyset$: $s \= \<Dopøedu>(s,x)$.
346 \algout Nový stav~$s$.
349 \algo{AcHledej} \cmt{Spu¹tìní automatu na daný øetìzec}
350 \algin Seno~$\sigma$, zkonstruovaný automat.
352 \:Pro znaky $x\in\sigma$ postupnì provádíme:
353 \::$s \= \alg{AcKrok}(s, x)$.
355 \::Dokud $j \neq \emptyset$:
356 \:::Je-li $\<Slovo>(j) \neq \emptyset$:
357 \::::Ohlásíme $\<Slovo>(j)$.
358 \:::$j \= \<Zkratka>(j)$.
361 \>Stejným argumentem jako u~KMP zdùvodníme, ¾e v¹echny kroky automatu dohromady trvají $\O(S)$.
362 Mimo to je¹tì hlásíme výskyty, co¾ trvá $\O(\<poèet výskytù>)$. Zbývá
363 ukázat, jak automat sestrojit.
365 \s{Konstrukce automatu:}
366 Opìt se inspirujeme algoritmem KMP a nahlédneme, ¾e zpìtná hrana ze~stavu~$\beta$ vede tam,
367 kam by se automat dostal pøi hledání slova~$\beta$ bez prvního znaku. Chtìli bychom
368 tedy zaèít sestrojením dopøedných hran a pak spou¹tìním je¹tì nehotového automatu
369 na jednotlivé jehly doplòovat zpìtné hrany, doufajíce, ¾e si vystaèíme s~u¾ sestrojenou
372 Kdybychom v¹ak automat spou¹tìli na jednu jehlu po~druhé (poka¾dé bez prvního
373 znaku), dostali bychom se do úzkých, proto¾e zpìtné hrany mohou vést køí¾em mezi
374 jednotlivými vìtvemi stromu. Mohlo by se nám tedy stát, ¾e pøi hledání nìjakého
375 slova potøebujeme zpìtnou hranu, která vede do~jiného slova, které jsme je¹tì
376 nezkonstruovali. Proto tento postup sel¾e.
378 Mù¾eme v¹ak vyu¾ít toho, ¾e ka¾dá zpìtná hrana vede ve~stromu alespoò o~jednu
379 hladinu vý¹, a strom konstruovat po~hladinách. To si lze pøedstavit tak, ¾e
380 paralelnì spustíme vyhledávání v¹ech slov bez prvních písmenek a~v¾dycky udìláme
381 jeden krok ka¾dého z~tìchto hledání, co¾ nám dá zpìtné hrany v~dal¹ím patøe stromu.
383 Kdykoliv vytvoøíme zpìtnou hranu, sestrojíme také zkratkovou hranu z~tého¾
384 vrcholu. Pokud vede zpìtná hrana ze stavu~$s$ do stavu~$z$ a $\<Slovo>(z)$ je definováno,
385 musí vést zkratka z~$s$ také do~$z$. Pokud v~$z$ ¾ádné slovo nekonèí, musí
386 zkratka z~$s$ vést do tého¾ vrcholu, kam vede zkratka ze~$z$.
389 \algin Slova $\iota_1,\ldots,\iota_n$.
390 \:Zalo¾íme strom, který obsahuje pouze koøen~$r$.
391 \:Vlo¾íme do~stromu slova $\iota_1 \dots \iota_n$, nastavíme $\<Slovo>$ ve~v¹ech stavech.
392 \:$\<Zpìt>(r) \= \emptyset$, $\<Zkratka>(r) \= \emptyset$.
393 \:Zalo¾íme frontu $F$ a~vlo¾íme do~ní syny koøene.
394 \:Pro v¹echny syny~$s$ koøene: $\<Zpìt>(s) \= r$, $\<Zkratka>(s) \= \emptyset$.
395 \:Dokud $F \neq \emptyset$:
396 \::Vybereme $i$ z~fronty $F$.
397 \::Pro v¹echny syny $s$ vrcholu $i$:
398 \:::$z \= \alg{AcKrok}(\<Zpìt>(s), \hbox{písmeno na~hranì $is$})$.
399 \:::$\<Zpìt>(s) \= z$.
400 \:::Pokud $\<Slovo>(z) \neq \emptyset$: $\<Zkratka>(s) \= z$.
401 \:::Jinak $\<Zkratka>(s) \= \<Zkratka>(z)$.
402 \:::Vlo¾íme $s$ do~fronty $F$.
403 \algout Strom, pole \<Slovo>, \<Zpìt> a \<Zkratka>.
406 Pro rozbor èasové slo¾itosti si uvìdomíme, ¾e konstrukce zpìtných hran
407 hledá v¹echny jehly, jen kroky jednotlivých hledání vhodným zpùsobem støídá
408 (jakoby je provádìla paralelnì).
409 Její èasovou slo¾itost tedy mù¾eme shora omezit souètem slo¾itostí hledání
410 jehel, co¾, jak u¾ víme, je lineární v~délce jehel.
411 Konstrukce dokonce mù¾e dobìhnout i rychleji, jsou-li toti¾ dva z~provádìných
412 výpoètù v~tém¾e stavu, poèítáme krok automatu pouze jednou. To je vidìt tøeba
413 na spoleèném zaèátku slov |araba| a |arbara|.
415 Chování celého algoritmu shrneme do následující vìty:
417 \s{Vìta:} Algoritmus Aho-Corasicková najde v¹echny výskyty v~èase
418 $\O\left(\sum_i J_i + S + V \right)$, kde $J_1,\ldots,J_n$ jsou délky
419 jednotlivých jehel, $S$ je délka sena a $V$ poèet ohlá¹ených výskytù.
421 \h{Rabinùv-Karpùv algoritmus}
423 Nyní si uká¾eme je¹tì jeden algoritmus na~hledání jedné jehly, tentokrát
424 zalo¾ený na he¹ování. Aèkoliv jeho èasová slo¾itost v~nejhor¹ím pøípadì
425 bude srovnatelná s~hledáním hrubou silou, v~prùmìru bude lineární a v~praxi
426 èasto pobì¾í rychleji ne¾ KMP.
428 Pøedstavme si, ¾e máme seno délky $S$ a~jehlu délky $J$. Poøídíme si nìjakou
429 he¹ovací funkci~$H$, které $J$-ticím znakù pøiøazuje èísla z~mno¾iny $\{0,\ldots,N-1\}$
430 pro nìjaké dost velké~$N$. Budeme posouvat okénko délky~$J$ po~senì, pro ka¾dou
431 jeho polohu si spoèteme he¹ znakù uvnitø okénka, porovnáme s~he¹em jehly a pokud
432 se rovnají, porovnáme okénko s~jehlou znak po~znaku.
434 Pokud je he¹ovací funkce \uv{kvalitní}, málokdy se stane, ¾e by se he¹e rovnaly,
435 tak¾e místo èasu $\Theta(J)$ na porovnáváním øetìzcù si vystaèíme s~porovnáním
436 he¹ù v~konstantním èase. Jen¾e ouha, èas $\Theta(J)$ potøebujeme i na vypoètení
437 he¹e pro ka¾dou polohu okénka. Jak z~toho ven?
439 Poøídíme si he¹ovací funkci, kterou lze pøi posunutí okénka o~jednu
440 pozici doprava v~konstantním èase pøepoèítat. Tyto po¾adavky splòuje tøeba
443 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,
445 pøièem¾ písmena pova¾ujeme za pøirozená èísla a $P$ je nìjaká vhodná konstanta -- potøebujeme,
446 aby byla nesoudìlná s~$N$ a aby $P^J$ bylo øádovì vìt¹í ne¾~$N$.
447 Posuneme-li nyní okénko z~$x_1,\ldots,x_J$ na $x_2,\ldots,x_{J+1}$, he¹ se zmìní takto:
449 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
450 &= (P\cdot H(x_1,\ldots,x_J) - x_1P^J + x_{J+1}) \bmod N. \cr
452 Pokud si mocninu $P^J$ pøepoèítáme, probìhne aktualizace he¹e v~konstantním èase.
454 Celý algoritmus pak bude vypadat následovnì:
457 \algin Jehla $\iota$ délky~$J$, seno~$\sigma$ délky~$S$.
458 \:$j \= H(\iota)$. \cmt{he¹ jehly}
459 \:$h \= H(\sigma[{}:J])$. \cmt{he¹ první pozice okénka}
460 \:Zvolíme~$P$ a~$N$ a pøedpoèítáme $P^J \bmod N$.
461 \:Pro $i$ od~$0$ do~$S-J$: \cmt{mo¾né pozice okénka}
463 \:::Pokud $\sigma[i:i+J] = \iota$, ohlásíme výskyt na pozici~$i$.
464 \::Pokud $i<S-J$: \cmt{pøepoèítáme he¹}
465 \:::$h \= (P\cdot h - \sigma[i]\cdot P^J + \sigma[i+J]) \bmod N$.
469 V~nejhor¹ím pøípadì pro ka¾dou pozici okénka porovnáváme øetìzce a celý
470 algoritmus spotøebuje èas $\Theta(JS)$. Abychom zjistili, jak tomu bude
471 v~prùmìrném pøípadì, odhadnìme pravdìpodobnost porovnání.
473 Pøedev¹ím pokud nastane výskyt, urèitì porovnáváme. Nenastane-li, he¹ jehly
474 se shoduje s~he¹em okénka s~pravdìpodobností $1/N$ (za~pøedpokladu dokonale
475 náhodného chování he¹ovací funkce, co¾ té na¹í budeme vìøit, aèkoliv jsme
476 to poøádnì nedokázali).
478 V~prùmìru tedy spotøebujeme èas $\O(S + VJ + S/N\cdot J)$, kde $V$ je poèet
479 nalezených výskytù. Pokud nám bude staèit najít první výskyt a zvolíme $N > SJ$,
480 algoritmus pobì¾í v~prùmìrném èase $\O(S)$.
484 \ex{Naivní algoritmus, který zkou¹í v¹echny mo¾né zaèátky jehly v~senì a v¾dy
485 porovnává øetìzce, má èasovou slo¾itost $\O(JS)$. Mù¾e být opravdu tak pomalý,
486 uvá¾íme-li, ¾e porovnávání øetìzcù skonèí, jakmile najde první neshodu? Sestrojte
487 vstup, na kterém algoritmus pobì¾í $\Theta(JS)$ krokù, pøesto¾e nic nenajde.}
490 \ex{Naleznìte pøíklad jehel a sena, v~nìm¾ se nachází superlineární poèet
491 výskytù vzhledem k~celkové velikosti vstupu (souèet velikostí jehel a délky
495 \ex{Uva¾ujme zjednodu¹ený algoritmus AC, který nepou¾ívá zkratkové hrany
496 a v¾dy projde po zpìtných hranách a¾ do koøene. Uka¾te pøíklad vstupu,
497 na~kterém je tento algoritmus asymptoticky pomalej¹í.}
499 \ex{Oznaème $M(s)$ mno¾inu øetìzcù, jejich¾ výskyty algoritmus AC ohlásí
500 ve~stavu~$s$. Uka¾te, ¾e kdybychom si mìli v¹echny mno¾iny $M(s)$ pamatovat
501 explicitnì, budeme pro nìkteré sady jehel potøebovat superlineární mno¾ství
502 prostoru vzhledem k~velikosti vstupu, tak¾e automat nepùjde sestrojit
506 \ex{Rozmyslete si, ¾e mno¾iny $M(S)$ z~pøedchozího pøíkladu by bylo mo¾né
507 reprezentovat jako srùstající spojové seznamy -- tedy takové, kde si ka¾dý
508 prvek pamatuje ukazatel na svého následníka, který ov¹em mù¾e le¾et v~jiném
509 seznamu. Uka¾te, ¾e námi zavedené zkratkové hrany lze interpretovat jako
510 ukazatele v~takových seznamech.}
512 \ex{Rozmyslete si, jak algoritmy z~této kapitoly upravit, aby si poradily
513 s~velkými abecedami.}
516 \ex{Upravte algoritmus AC, aby pro ka¾dou pozici v~senì vypsal nejdel¹í
517 tam konèící jehlu, a~to efektivnìji ne¾ vyjmenováním v¹ech jehel. Jak se
518 algoritmus zmìní, budeme-li chtít vypsat nejdel¹í jehlu, která na dané
521 \ex{Mìjme seno a jehly. Popi¹te algoritmus, který v~lineárním èase pro ka¾dou
522 jehlu spoèítá, kolikrát se v~senì vyskytuje. Èasová slo¾itost by nemìla záviset
523 na poètu výskytù -- ten, jak u¾ víme, mù¾e být superlineární.}
525 \ex{Cenzor dostane mno¾inu zakázaných podøetìzcù a text. V¾dy najde nejlevìj¹í
526 výskyt zakázaného podøetìzce v~textu (s~nejlevìj¹ím koncem; pokud jich je více,
527 tak nejdel¹í takový), vystøihne ho a postup opakuje. Uka¾te, jak text cenzurovat
530 \ex{Rotací øetìzce~$\alpha$ o~$K$ pozic nazýváme øetìzec $\alpha[K:{}]\alpha[{}:K]$.
531 Jak o~dvou øetìzcích zjistit, zda je jeden rotací druhého?}
533 \ex{Jak v~lineárním èase zrotovat øetìzec, dostaèuje-li pamì» poèítaèe jen
534 na ulo¾ení jednoho øetìzce a $\O(1)$ pomocných promìnných?}
536 \exx{Navrhnìte algoritmus, který v~lineárním èase nalezne tu z~rotací zadaného
537 øetìzce, je¾ je lexikograficky minimální.}
539 \ex{Navrhnìte datovou strukturu pro básníky, která si bude pamatovat slovník
540 a bude umìt hledat rýmy. Tedy pro libovolné zadané slovo najde takové slovo
541 ve~slovníku, které má se zadaným nejdel¹í spoleèný suffix.}
543 \exx{Upravte datovou strukturu z~pøedchozího cvièení, aby v~pøípadì, ¾e nejlep¹ích rýmù
544 je více, vypsala lexikograficky nejmen¹í z~nich.}
546 \ex{Jak reprezentovat slovník, abyste umìli rychle vyhledávat v¹echny
547 pøesmyèky zadaného slova?}
549 \exx{Je dán text a èíslo~$K$. Jak zjistit, který podøetìzec délky~$K$
550 se v~textu vyskytuje nejèastìji?}
552 \exx{Sestrojte co nejefektivnìj¹í algoritmus, který v~daném øetìzci najde
553 nejdel¹í podøetìzec, který se vyskytuje vícekrát.}
555 \exx{Uka¾te, jak pro dané dva øetìzce najít jejich nejdel¹í spoleèný
558 \ex{Definujme Fibonacciho slova takto: $F_0=|a|$, $F_1=|b|$, $F_{n+2}=F_nF_{n+1}$.
559 Jak v~zadaném øetìzci nad abecedou $\{|a|,|b|\}$ najít nejdel¹í Fibonacciho podslovo?
562 \exx{Pokraèujme v~pøedchozím cvièení. Dostaneme øetìzec nad nìjakou obecnou abecedou,
563 chceme nalézt jeho nejdel¹í podøetìzec, který je isomorfní s~nìjakým Fibonacciho slovem
564 (li¹í se pouze substitucí jiných znakù za |a| a~|b|).}
566 \ex{Je dáno slovo. Chceme nalézt jeho nejdel¹í prefix, který je souèasnì suffixem.}
568 \ex{Jak zjistit, zda je zadané slovo~$\alpha$ periodické? Tím myslíme zda existuje
569 slovo~$\beta$ a èíslo $k>1$ takové, ¾e $\alpha = \beta^k$ (zøetìzení $k$~kopií øetìzce~$\beta$).}
projects / ads2.git / blob