\input lecnotes.tex

\prednaska{1}{Vyhledávání v~textu}{}

\h{Jehla v~kupce sena}

Uva¾ujme následující problém: máme nìjaký text~$\sigma$ délky~$S$ (seno), chceme v~nìm najít
v¹echny výskyty nìjakého podøetìzce~$\iota$ délky~$J$ (jehly). Seno pøitom bude øádovì del¹í
ne¾ jehla.

Triviální øe¹ení pøesnì podle definice by vypadalo následovnì: Zkusíme v¹echny mo¾né pozice,
kde by se v~senì mohla jehla nacházet, a pro ka¾dou z~nich otestujeme, zda tam opravdu je.
Pozic je øádovì~$S$, ka¾dé porovnání stojí a¾~$J$, celkovì tedy algoritmus bì¾í v~èase
$\O(SJ)$. (Rozmyslete si, jak by vypadaly vstupy, pro které skuteènì spotøebujeme tolik èasu.)

Zkusme jiný pøístup: nalezneme v~senì první znak jehly a od tohoto místa budeme porovnávat
dal¹í znaky. Pokud se pøestanou shodovat, pøepneme opìt na hledání prvního znaku. Jen¾e odkud?
Pokud od místa, kde nastala neshoda, sel¾e to tøeba pøi hledání jehly |kokos| v~senì |clanekokokosu|
-- neshoda nastane za~|koko| a zbylý |kos| nás neuspokojí. Nebo se mù¾eme vrátit a¾ k~výskytu
prvního znaku a pokraèovat tìsnì za ním, jen¾e to je toté¾, co dìlal triviální algoritmus,
tak¾e je to také stejnì pomalé.

V~této kapitole si uká¾eme algoritmus, který je o~trochu slo¾itìj¹í, ale nalezne v¹echny
výskyty v~èase $\O(S+J)$. Pak ho zobecníme, aby umìl hledat více rùzných jehel najednou.

\h{Øetìzce a abecedy}

Aby se nám o~øetìzcových algoritmech lépe psalo, udìlejme si nejprve poøádek
v~terminologii okolo øetìzcù.

\s{Definice:}
\itemize\ibull
\:{\I Abeceda $\Sigma$} je nìjaká koneèná mno¾ina {\I znakù,} z~nich¾ se
  skládají na¹e øetìzce.
\:{\I $\Sigma^*$} je mno¾ina v¹ech {\I slov} neboli {\I øetìzcù} nad abecedou~$\Sigma$,
  co¾ jsou koneèné posloupnosti znakù ze~$\Sigma$.
\endlist

\s{Pøíklady:}
Abeceda mù¾e být tvoøena tøeba písmeny |a| a¾~|z| nebo bity |0| a~|1|.
Potkáme ov¹em i rozlehlej¹í abecedy: napøíklad dnes bì¾ná znaková sada UniCode
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
zpùsobem pou¾ívají øetìzce lingvisté: na èeský text se nìkdy dívají jako na~øetìzec
nad abecedou, její¾ prvky jsou èeská slova.

Pro na¹e úèely budeme pøedpokládat, ¾e abeceda je \uv{rozumnì malá}, èím¾ myslíme, ¾e
její velikost je konstantní a navíc dostateènì malá na to, abychom si mohli dovolit
ukládat do pamìti pole indexovaná znakem.

\s{Znaèení:}
\itemize\ibull
\:{\I Slova} budeme znaèit malými písmenky øecké abecedy $\alpha$, $\beta$, \dots
\:{\I Znaky} oznaèíme malými písmeny latinky $a$, $b$, \dots{} \hfil\break
  Znak budeme pou¾ívat i ve~smyslu jednoznakového øetìzce.
\:{\I Èísla} budeme znaèit velkými písmeny $A$, $B$, \dots
\:{\I Délka slova} $\vert \alpha  \vert$ udává, kolika znaky je slovo tvoøeno.
\:{\I Prázdné slovo} znaèíme písmenem $\varepsilon$, je to jediné slovo délky~0.
\:{\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$.
\:$\alpha[k]$ je $k$-tý znak slova $\alpha$, indexujeme od~$0$ do~$\vert\alpha\vert-1$.
\:$\alpha[k:\ell]$ je {\I podslovo} zaèínající $k$-tým znakem a konèící tìsnì pøed~$\ell$-tým.
Tedy $\alpha[k:\ell] = \alpha[k]\alpha[k+1]\ldots\alpha[\ell-1]$. Pokud $k\ge\ell$, je podslovo
prázdné. Pokud nìkterou z~mezí vynecháme, míní se $k=0$ nebo $\ell=\vert\alpha\vert$.
\:$\alpha[{}:\ell]$ je {\I prefix} (pøedpona) tvoøený prvními $\ell$ znaky øetìzce.
\:$\alpha[k:{}]$ je {\I suffix} (pøípona) od $k$-tého znaku do~konce øetìzce.
\:$\alpha[:] = \alpha$.
\endlist

\>Dodejme je¹tì, ¾e prázdné slovo je prefixem, suffixem i~podslovem jakéhokoliv slova vèetnì sebe sama.
Ka¾dé slovo je také prefixem, suffixem i~podslovem sebe sama. To se ne v¾dy hodí, pak budeme hovoøit
o~{\I vlastním} prefixu, suffixu èi podslovì, èím¾ myslíme, ¾e alespoò jeden znak nebude obsahovat.

\h{Inkrementální algoritmus}

Vra»me se tedy zpìt k~pùvodnímu problému hledání podøetìzcù. Nejprve si
ujasnìme, co má být výstupem algoritmu. Budeme chtít nalézt mno¾inu v¹ech
indexù~$K$ takových, ¾e $\sigma[K:K+\vert\iota\vert] = \iota$. To je dostateènì
kompaktní výstup (nejvý¹e lineární s~délkou sena), a~pøitom obsahuje informace
o~v¹ech výskytech.

Na hledání podøetìzce pou¾ijeme {\I inkrementální pøístup.} Tím se obecnì myslí,
¾e chceme umìt roz¹íøit vstup o~dal¹í znak a pøepoèítat výstup. V~na¹em pøípadì
budeme pøidávat znak na konec sena a zapoèítáme pøípadný nový výskyt jehly, který
konèí tímto znakem.

Abychom toho dosáhli, budeme si prùbì¾nì udr¾ovat informaci o~tom, jaký nejdel¹í
prefix jehly konèí právì pøidaným znakem. Tomu budeme øíkat {\I stav algoritmu.}
A~jakmile bude tento prefix roven celé jehle, ohlásíme výskyt.

Pøedstavme si tedy, ¾e jsme pøeèetli øetìzec~$\sigma$, který konèil stavem~$\alpha$.
Teï vstup roz¹íøíme o~znak~$x$ na~$\sigma x$. V~jakém stavu se nyní máme
nacházet? Pokud to nebude prázdný øetìzec, musí konèit na~$x$, tedy ho mù¾eme
napsat ve~tvaru $\alpha'x$.

V¹imneme si, ¾e $\alpha'$ musí být suffixem slova~$\alpha$: Jeliko¾ $\alpha' x$
je prefix jehly, je $\alpha'$ také prefix jehly. A~proto¾e $\alpha'x$ je suffixem~$\sigma x$,
musí $\alpha'$ být suffixem~$\sigma$. Tedy jak $\alpha$, tak $\alpha'$ jsou suffixy slova~$\alpha$,
které jsou souèasnì prefixy jehly. Ov¹em stav~$\alpha$ jsme vybrali jako nejdel¹í slovo
s~touto vlastností, tak¾e $\alpha'$~musí být nejvý¹e tak dlouhé, a~tudí¾ je prefixem~$\alpha$.

Staèilo by tedy probrat v¹echny suffixy slova~$\alpha$, které jsou prefixem jehly,
a~vybrat z~nich nejdel¹í, který po roz¹íøení o~znak~$x$ je stále prefixem jehly.

Abychom ale nemuseli suffixy procházet v¹echny, pøedpoèítáme {\I zpìtnou funkci~$z$.}
Ta nám pro ka¾dý prefix jehly øekne, jaký je jeho nejdel¹í vlastní suffix,
který je opìt prefixem jehly. To nám umo¾ní procházet rovnou kandidáty na nový stav:
staèí probrat øetìzce $\alpha$, $z(\alpha)$, $z(z(\alpha))$, \dots{} a pou¾ít první,
který lze roz¹íøit o~znak~$x$. Pokud nepùjde roz¹íøit ani jeden z~tìchto kandidátù,
novým stavem bude prázdný øetìzec.

Na~této my¹lence je zalo¾en následující algoritmus.

\h{Knuthùv-Morrisùv-Prattùv algoritmus (KMP)}

Algoritmus se opírá o~{\I vyhledávací automat.} To je orientovaný graf, jeho¾
vrcholy ({\I stavy} automatu) odpovídají prefixùm jehly. Vrcholy jsou spojeny
hranami dvou druhù: {\I dopøedné} popisují roz¹íøení prefixu pøidáním jednoho písmene,
{\I zpìtné} vedou podle zpìtné funkce, tedy z~ka¾dého stavu do jeho nejdel¹ího
vlastního suffixu, který je opìt stavem.

\figure{barb.eps}{Vyhledávací automat pro slovo |barbarossa|}{4.1in}

Reprezentace automatu bude pøímoèará: stavy oèíslujeme od~0 do~$J$, dopøedná hrana
povede v¾dy ze stavu~$S$ do~$S+1$ a bude odpovídat roz¹íøení prefixu o~pøíslu¹ný
znak jehly, tedy $\iota[S]$. Zpìtné hrany si budeme pamatovat v~poli~$Z$, tedy
$Z[S]$ bude øíkat èíslo stavu, do~nìj¾ vede zpìtná hrana ze~stavu~$S$, pøípadnì
bude nedefinované, pokud taková hrana neexistuje.

Kdybychom takový automat mìli, mohli bychom pomocí nìj inkrementální algoritmus
z~pøedchozí sekce popsat následovnì:

\proc{KmpKrok} \cmt{Jeden krok automatu}
\algin Jsme ve~stavu~$I$, pøeèetli jsme znak~$x$.
\:Dokud $\iota[I] \neq x~\&~I \neq 0: I \= Z[I]$.
\:Pokud $\iota[I] = x$, pak $I \= I + 1$.
\algout Nový stav~$I$.
\endalgo

\algo{Kmp} \cmt{Spu¹tìní automatu na øetìzec~$\sigma$.}
\algin Seno~$\sigma$, zkonstruovaný automat.
\:$I \= 0$.
\:Pro znaky $x\in\sigma$ postupnì provádíme:
\::$I \= \alg{KmpKrok}(I,x)$.
\::Pokud $I = J$, ohlásíme výskyt.
\endalgo

\s{Invariant:} Stav algoritmu~$I$ v~ka¾dém okam¾iku øíká, jaký nejdel¹í
prefix jehly je suffixem zatím pøeètené èásti sena. (To u¾ víme z~úvah
o~inkrementálním algoritmu.)

\s{Dùsledek:} Algoritmus ohlásí v¹echny výskyty. Pokud jsme toti¾ právì
pøeèetli poslední znak nìjakého výskytu, je celá jehla suffixem zatím
pøeètené èásti sena, tak¾e se musíme nacházet v~posledním stavu.

Jen musíme opravit drobnou chybu -- tìsnì poté, co ohlásíme výskyt, se
algoritmus zeptá na~dopøednou hranu z~posledního stavu. Ta ale
neexistuje. Napravíme to jednodu¹e: pøidáme fiktivní dopøednou hranu,
na~ní¾ je napsán znak odli¹ný od~v¹ech skuteèných znakù. Tím zajistíme,
¾e se po této hranì nikdy nevydáme. Staèí tedy vhodnì dodefinovat $\iota[i]$.%
\foot{V jazyce C mù¾eme zneu¾ít toho, ¾e ka¾dý øetìzec je ukonèen znakem
s~nulovým kódem.}

\s{Lemma:} Funkce \<Hledej> bì¾í v~èase $\O(S)$.

\proof
Výpoèet funkce mù¾eme rozdìlit na prùchody dopøednými a zpìtnými hranami.
S~dopøednými je to snadné -- za~ka¾dý z~$S$ znakù sena projdeme po nejvý¹e
jedné dopøedné hranì. To o~zpìtných hranách neplatí, ale pomù¾e nám, ¾e ka¾dá
dopøedná hrana vede o~právì~1 stav doprava a ka¾dá zpìtná o~aspoò~1 stav
doleva. Proto je v¹ech prùchodù po~zpìtných hranách nejvý¹e tolik, kolik
jsme pro¹li dopøedných hran, tak¾e také nejvý¹e~$S$.
\qed

\s{Konstrukce automatu:}
Algoritmus je tedy lineární, ale potøebuje, aby mu nìkdo zkonstruoval 
automat. Dopøedné hrany vytvoøíme snadno, ale jak si poøídit ty zpìtné?

Podnikneme my¹lenkový pokus: Pøedstavme si, ¾e automat u¾ máme hotový, ale nevidíme,
jak vypadá uvnitø. Chtìli bychom zjistit, jak v~nìm vedou zpìtné hrany, ov¹em jediné,
co umíme, je spustit automat na nìjaký øetìzec a zjistit, v~jakém stavu skonèil.

Tvrdíme, ¾e pro zji¹tìní zpìtné hrany ze~stavu~$\alpha$ staèí automatu pøedlo¾it
øetìzec $\alpha[1:{}]$. Definice zpìtné funkce je toti¾ nápadnì podobná invariantu,
který jsme o~funkci \<Hledej> dokázali. Obojí hovoøí o~nejdel¹ím suffixu daného
slova, který je prefixem jehly. Jediný rozdíl je v~tom, ¾e v~pøípadì zpìtné funkce
uva¾ujeme pouze vlastní suffixy, zatímco invariant pøipou¹tí i nevlastní. To ov¹em
snadno vyøe¹íme \uv{ukousnutím} prvního znaku jména stavu.

Pokud chceme objevit v¹echny zpìtné hrany, staèí automat spou¹tìt postupnì
na øetìzce $\iota[1:1]$, $\iota[1:2]$, $\iota[1:3]$, atd. Jeliko¾ funkce \<Hledej>
je lineární, stálo by nás to dohromady $\O(J^2)$. Pokud si ale v¹imneme, ¾e ka¾dý
ze~zmínìných øetìzcù je prefixem toho následujícího, je jasné, ¾e staèí spustit
automat jen jednou na øetìzec $\iota[1:{}]$ a jen zaznamenávat, kterými stavy
jsme pro¹li.

To je zajímavé pozorování, øeknete si, ale jak nám pomù¾e ke~konstrukci automatu,
kdy¾ samo u¾ hotový automat potøebuje? Pomù¾e pìkný trik: pokud hledáme zpìtnou
hranu z~$I$-tého stavu, spou¹tíme automat na slovo délky~$I-1$, tak¾e se mù¾eme
dostat pouze do prvních~$I-1$ stavù a vùbec nám nevadí, ¾e v~tom $I$-tém je¹tì
není zpìtná hrana hotova.%
\foot{Konstruovat nìjaký objekt pomocí tého¾ objektu je osvìdèený postup, který
si u¾ vyslou¾il i svùj vlastní název. V~angliètinì se mu øíká {\I bootstrapping}
a z~tohoto názvu vzniklo i bootování poèítaèù, proto¾e pøi nìm operaèní systém
vlastnì do pamìti zavádí sám sebe. Kde se toto slovo vzalo? Bootstrap znamená èesky
{\I ¹truple} -- to je takové to oèko na patì boty, které usnadòuje nazouvání.
A~v~jednom z~pøíbìhù o~baronu Prá¹ilovi sly¹íme barona vyprávìt, jak se uvíznuv
v~ba¾inì zachránil tím, ¾e se vytáhl za ¹truple. Krásný popis bootování, není-li¾
pravda?}

Konstrukce automatu tedy bude vypadat tak, ¾e nejdøíve sestrojíme pouze dopøedné
hrany, pak rozpracovaný automat spustíme na øetìzec $\iota[1:{}]$ a podle toho,
jakými stavy prochází, doplòujeme zpìtné hrany. A~jeliko¾ vyhledávání je lineární,
celá konstrukce trvá $\O(J)$.

Hotový algoritmus mù¾eme zapsat následovnì:

\algo{KmpKonstrukce}
\algin Jehla~$\iota$ délky~$J$.
\:$Z[0] \= ?$, $Z[1] \= 0$.
\:$I \= 0$.
\:Pro $K = 2, \ldots, J-1$:
\::$I \= \alg{KmpKrok}(I, \iota[K])$.
\::$Z[K] \= I$.
\algout Pole zpìtných hran~$Z$.
\endalgo

\>Výsledky mù¾eme shrnout do následující vìty:

\s{Vìta:} Algoritmus KMP najde v¹echny výskyty v~èase $O(J+S)$.

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

\s{Definice:}
{\I Zkratková hrana} ze~stavu~$\alpha$ vede do nejbli¾¹ího stavu $\zeta(\alpha)$ dosa¾itelného
z~$\alpha$ po zpìtných hranách, který je koncový.

Jinými slovy, $\zeta(\alpha)$ nám øekne, jaký je nejdel¹í vlastní suffix slova~$\alpha$, který
je jehlou. Pokud takový suffix neexistuje, ¾ádná zkratková hrana ze~stavu~$\alpha$ nepovede.
Pomocí zkratkových hran mù¾eme snadno vyjmenovat v¹echny výskyty. Budeme postupovat stejnì,
jako bychom procházeli po v¹ech zpìtných hranách, jen budeme dlouhé úseky zpìtných hran, na~nich¾
není nic k~hlá¹ení, pøeskakovat v~konstantním èase.

\s{Reprezentace automatu:}
Vyhledávací automat se tedy sestává ze stromu dopøedných hran, ze zpìtných
hran a ze~zkratkových hran. Ne¾ vyslovíme samotný algoritmus AC, rozmysleme si, jak automat
ulo¾it do pamìti. Pro ka¾dý stav si budeme pamatovat:
\itemize\ibull
\:$I$ -- poøadové èíslo stavu (tøeba v~poøadí, jak vrcholy vznikaly),
\:$\<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
  èíslo stavu, do nìj¾ vede),
\:$\<Zkratka>(I)$ -- kam z~nìj vede zkratková hrana (takté¾),
\:$\<Slovo>(I)$ -- zda tu konèí nìjaké slovo (a~pokud ano, tak které),
\:$\<Dopøedu>(I,x)$ -- kam vede dopøedná hrana oznaèená písmenem~$x$ (pro malé abecedy si to
  mù¾eme pamatovat v~poli, pro velké tøeba v~he¹ovací tabulce nebo stromu).
\endlist

\>Celý algoritmus pro zpracování sena automatem pak bude vypadat takto:

\proc{AcKrok} \cmt{Jeden krok automatu}
\algin Jsme ve~stavu~$I$, pøeèetli jsme znak~$x$.
\:Dokud $\<Dopøedu>(I, x) = \emptyset~\&~I \ne \<koøen>$: $I \= \<Zpìt>(I)$.
\:Pokud $\<Dopøedu>(I, x) \ne \emptyset$: $I \= \<Dopøedu>(I,x)$.
\algout Nový stav~$I$.
\endalgo

\algo{AcHledej} \cmt{Spu¹tìní automatu na daný øetìzec}
\algin Seno~$\sigma$, zkonstruovaný automat.
\:$I \= \<koøen>$.
\:Pro znaky $x\in\sigma$ postupnì provádíme:
\::$I \= \alg{AcKrok}(I, x)$.
\::$K \= I$.
\::Dokud $K \neq \emptyset$:
\:::Je-li $\<Slovo>(K) \neq \emptyset$:
\::::Ohlásíme $\<Slovo>(K)$.
\:::$K \= \<Zkratka>(K)$.
\endalgo

\>Jak u¾ jsme nahlédli, v¹echny kroky automatu dohromady trvají $\O(S)$.
Mimo to je¹tì hlásíme výskyty, co¾ trvá $\O(\<poèet výskytù>)$. Zbývá
ukázat, jak automat sestrojit.

\s{Konstrukce automatu:}
Stejnì jako u~KMP, i zde nahlédneme, ¾e zpìtná hrana ze stavu $\beta$ vede tam,
kam by se dostal automat pøi hledání slova $\beta$ bez prvního znaku. Opìt bychom
tedy chtìli zaèít sestrojením dopøedných hran a pak spu¹tìním je¹tì nehotového
automatu doplòovat hrany zpìtné, doufajíce, ¾e si vystaèíme s~u¾ sestrojenou
èástí automatu.

Pøi konstrukci zpìtných hran tedy chceme automatem vyhledávat v¹echny jehly
bez prvních znakù. To v¹ak nemù¾eme dìlat jednu jehlu po druhé, proto¾e zpìtné
hrany mohou vést køí¾em mezi jednotlivými vìtvemi stromu. 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. Proto 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ý¹, a strom konstruovat po~hladinách. To si lze 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 krok ka¾dého z~tìchto hledání, co¾ nám dá zpìtné hrany v~dal¹ím patøe stromu.

Kdykoliv vytvoøíme zpìtnou hranu, sestrojíme také zkratkovou hranu z~tého¾
vrcholu. Pokud vede zpìtná hrana z~$K$ do~$Q$ a $\<Slovo>(Q) \ne \emptyset$,
musí vést zkratka z~$K$ také do~$Q$. Pokud v~$Q$ ¾ádné slovo neskonèí, musí
zkratka z~$K$ vést do tého¾ vrcholu, jako zkratka z~$Q$.

\algo{AcKonstrukce}
\algin Slova $\iota_1,\ldots,\iota_N$.
\:Zalo¾íme prázdný strom, $R \=$ jeho koøen.
\:Vlo¾íme do~stromu slova $\iota_1 \dots \iota_N$, nastavíme $\<Slovo>$ ve~v¹ech stavech.
\:$\<Zpìt>(R) \= \emptyset$, $\<Zkratka>(R) \= \emptyset$.
\:Zalo¾íme frontu $F$ a~vlo¾íme do~ní syny koøene.
\:Pro v¹echny syny~$K$ koøene: $\<Zpìt>(K) \= R$, $\<Zkratka>(K) \= \emptyset$.
\:Dokud $F \neq \emptyset$:
\::Vybereme $I$ z~fronty $F$.
\::Pro v¹echny syny $K$ vrcholu $I$:
\:::$Q \= \alg{AcKrok}(\<Zpìt>(I), \hbox{písmeno na~hranì $IK$})$.
\:::$\<Zpìt>(K) \= Q$.
\:::Pokud $\<Slovo>(Q) \neq \emptyset$: $\<Zkratka>(K) \= Q$.
\:::Jinak $\<Zkratka>(K) \= \<Zkratka>(Q)$.
\:::Vlo¾íme $K$ do~fronty $F$.
\algout Strom, pole \<Slovo>, \<Zpìt> a \<Zkratka>.
\endalgo

Jeliko¾ tento algoritmus pouze napøeskáèku hledá v¹echny jehly, musí být jeho
èasová slo¾itost shora omezena souètem slo¾itostí hledání jehel, co¾, jak u¾
víme, je pro ka¾dou jehlu lineární s~její délkou. Dokonce mù¾e dobìhnout i
rychleji, jeliko¾ jsou-li dva ze simulovaných výpoètù v~tém¾e stavu, poèítáme
krok automatu pouze jednou (to je vidìt tøeba na spoleèném zaèátku slov |araba|
a |arbara|).

Chování celého algoritmu shrneme do následující vìty:

\s{Vìta:} Algoritmus Aho-Corasicková najde v¹echny výskyty v~èase
$\O\left(\sum_i J_i + S + V \right)$, kde $J_1,\ldots,J_n$ jsou délky
jednotlivých jehel, $S$ je délka sena a $V$ poèet ohlá¹ených výskytù.

\h{Rabinùv-Karpùv algoritmus}

Nyní si uká¾eme je¹tì jeden algoritmus na~hledání jedné jehly, tentokrát
zalo¾ený na he¹ování. Aèkoliv jeho èasová slo¾itost v~nejhor¹ím pøípadì
bude srovnatelná s~hledáním hrubou silou, v~prùmìru bude lineární a v~praxi
èasto pobì¾í rychleji ne¾ KMP.

Pøedstavme si, ¾e máme seno délky $S$ a~jehlu délky $J$. Poøídíme si nìjakou
he¹ovací funkci~$H$, které $J$-ticím znakù pøiøazuje èísla z~mno¾iny $\{0,\ldots,N-1\}$
pro nìjaké dost velké~$N$. Budeme posouvat okénko délky~$J$ po~senì, pro ka¾dou
jeho polohu si spoèteme he¹ znakù uvnitø okénka, porovnáme s~he¹em jehly a pokud
se rovnají, porovnáme je znak po~znaku.

Pokud je he¹ovací funkce \uv{kvalitní}, málokdy se stane, ¾e by se he¹e rovnaly,
tak¾e místo èasu $\Theta(J)$ na porovnáváním øetìzcù si vystaèíme s~porovnáním
he¹ù v~konstantním èase. Jen¾e ouha, èas $\Theta(J)$ potøebujeme i na vypoètení
he¹e pro ka¾dou polohu okénka, tak¾e jsme si nepomohli.

Poøídíme si proto he¹ovací funkci, kterou lze pøi posunutí okénka o~jednu
pozici doprava v~konstantním èase pøepoèítat. Tyto po¾adavky splòuje tøeba
polynom
$$
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,
$$
pøièem¾ písmena pova¾ujeme za pøirozená èísla a $P$ je nìjaká vhodná konstanta -- potøebujeme,
aby byla nesoudìlná s~$N$ a aby $P^J$ bylo øádovì vìt¹í ne¾~$N$.
Posuneme-li nyní okénko z~$x_1,\ldots,x_J$ na $x_2,\ldots,x_{J+1}$, he¹ se zmìní takto:
$$\eqalign{
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
&= (P\cdot H(x_1,\ldots,x_J) - x_1P^J + x_{J+1}) \bmod N. \cr
}$$
Pokud si mocninu $P^J$ pøepoèítáme, probìhne aktualizace he¹e v~konstantním èase.

Celý algoritmus pak bude vypadat následovnì:

\algo{RabinKarp}
\algin Jehla $\iota$ délky~$J$, seno~$\sigma$ délky~$S$.
\:$X \= H(\iota)$. \cmt{he¹ jehly}
\:$Y \= H(\sigma[{}:J])$. \cmt{he¹ první pozice okénka}
\:Zvolíme~$P$ a~$N$ a pøedpoèítáme $P^J \bmod N$.
\:Pro $I$ od~$0$ do~$S-J$: \cmt{mo¾né pozice okénka}
\::Je-li $X=Y$:
\:::Pokud $\sigma[I:I+J] = \iota$, ohlásíme výskyt na pozici~$I$.
\::Pokud $I<S-J$: \cmt{pøepoèítáme he¹}
\:::$Y \= (P\cdot Y - \sigma[I]\cdot P^J + \sigma[I+J]) \bmod N$.
\endalgo

\s{Analýza:}
V~nejhor¹ím pøípadì pro ka¾dou pozici okénka porovnáváme øetìzce a celý
algoritmus spotøebuje èas $\Theta(JS)$. Abychom zjistili, jak tomu bude
v~prùmìrném pøípadì, odhadnìme pravdìpodobnost porovnání.

Pøedev¹ím pokud nastane výskyt, urèitì porovnáváme. Nenastane-li, he¹ jehly
se shoduje s~he¹em okénka s~pravdìpodobností $1/N$ (za~pøedpokladu dokonale
náhodného chování he¹ovací funkce, co¾ té na¹í budeme vìøit, aèkoliv jsme
to poøádnì nedokázali).

V~prùmìru tedy spotøebujeme èas $\O(S + VJ + S/N\cdot J)$, kde $V$ je poèet
nalezených výskytù. Pokud nám bude staèit najít první výskyt a zvolíme $N > SJ$,
algoritmus pobì¾í v~prùmìrném èase $\O(S)$.

\exercises

\ex{Naivní algoritmus, který zkou¹í v¹echny mo¾né zaèátky jehly v~senì a v¾dy
porovnává øetìzce, má èasovou slo¾itost $\O(JS)$. Mù¾e být opravdu tak pomalý,
uvá¾íme-li, ¾e porovnávání øetìzcù skonèí, jakmile najde první neshodu? Sestrojte
vstup, na kterém algoritmus pobì¾í $\Theta(JS)$ krokù, pøesto¾e nic nenajde.}

\ex{Naleznìte pøíklad jehel a sena, v~nìm¾ se nachází superlineární poèet
výskytù vzhledem k~celkové velikosti vstupu (souèet velikostí jehel a délky
sena).}

\ex{Uva¾ujme zjednodu¹ený algoritmus AC, který nepou¾ívá zkratkové hrany
a v¾dy projde po zpìtných hranách a¾ do koøene. Uka¾te pøíklad vstupu,
na~kterém je tento algoritmus asymptoticky pomalej¹í.}

\ex{Oznaème $M(S)$ mno¾inu øetìzcù, jejich¾ výskyty algoritmus AC ohlásí
ve~stavu~$S$. Uka¾te, ¾e kdybychom si mìli v¹echny mno¾iny $M(S)$ pamatovat
explicitnì, budeme pro nìkteré vstupy potøebovat superlineární mno¾ství
prostoru vzhledem k~velikosti vstupu, tak¾e automat nepùjde sestrojit
v~lineárním èase.}

\ex{Rozmyslete si, ¾e mno¾iny $M(S)$ z~pøedchozího pøíkladu by bylo mo¾né
reprezentovat jako srùstající spojové seznamy -- tedy takové, kde si ka¾dý
prvek pamatuje ukazatel na svého následníka, který ov¹em mù¾e le¾et v~jiném
seznamu. Uka¾te, ¾e námi zavedené zkratkové hrany lze interpretovat jako
v~takových seznamech.}

\ex{Rozmyslete si, jak algoritmy z~této kapitoly upravit, aby si poradily
s~velkými abecedami.}

\ex{Upravte algoritmus AC, aby pro ka¾dou pozici v~senì vypsal nejdel¹í
tam konèící jehlu, a~to efektivnìji ne¾ vyjmenováním v¹ech jehel. Jak se
algoritmus zmìní, budeme-li chtít vypsat nejdel¹í jehlu, která na dané
pozici zaèíná?}

\ex{Mìjme seno a jehly. Popi¹te algoritmus, který v~lineárním èase pro ka¾dou
jehlu spoèítá, kolikrát se v~senì vyskytuje. Èasová slo¾itost by nemìla záviset
na poètu výskytù -- ten, jak u¾ víme, mù¾e být superlineární.}

\ex{Cenzor dostane mno¾inu zakázaných podøetìzcù a text. V¾dy najde nejlevìj¹í
výskyt zakázaného podøetìzce v~textu (s~nejlevìj¹ím koncem; pokud jich je více,
tak nejdel¹í takový), vystøihne ho a postup opakuje. Uka¾te, jak text cenzurovat
v~lineárním èase.}

\ex{Rotací øetìzce~$\alpha$ o~$K$ pozic nazýváme øetìzec $\alpha[K:{}]\alpha[{}:K]$.
Jak o~dvou øetìzcích zjistit, zda je jeden rotací druhého?}

\ex{Jak v~lineárním èase zrotovat øetìzec, dostaèuje-li pamì» poèítaèe jen
na ulo¾ení jedhoho øetìzce a $\O(1)$ pomocných promìnných?}

\ex{Navrhnìte algoritmus, který v~lineárním èase nalezne tu z~rotací zadaného
øetìzce, je¾ je lexikograficky minimální.}

\ex{Navrhnìte datovou strukturu pro básníky, která si bude pamatovat slovník
a bude umìt hledat rýmy. Tedy pro libovolné zadané slovo najde takové slovo
ve~slovníku, které má se zadaným nejdel¹í spoleèný suffix.}

\exx{Upravte datovou strukturu z~pøedchozího cvièení, aby je-li nejlep¹ích rýmù
více, vypsala lexikograficky nejmen¹í z~nich.}

\ex{Jak reprezentovat slovník, abyste umìli rychle vyhledávat v¹echny
pøesmyèky zadaného slova?}

\exx{Je dán text a èíslo~$K$. Jak zjistit, který podøetìzec délky~$K$
se v~textu vyskytuje nejèastìji?}

\exx{Sestrojte co nejefektivnìj¹í algoritmus, který v~daném øetìzci najde
nejdel¹í podøetìzec, který se vyskytuje vícekrát.}

\exx{Uka¾te, jak pro dané dva øetìzce najít jejich nejdel¹í spoleèný
podøetìzec.}

\ex{Definujme Fibonacciho slova takto: $F_0=|a|$, $F_1=|b|$, $F_{n+2}=F_nF_{n+1}$.
Jak pro zadaný øetìzec nad abecedou $\{|a|,|b|\}$ najít nejdel¹í Fibonacciho podslovo?
}

\exx{Pokraèujme v~pøedchozím cvièení. Dostaneme-li øetìzec nad nìjakou obecnou abecedou,
jak nalézt jeho nejdel¹í podøetìzec, který je isomorfní s~nìjakým Fibonacciho slovem
(li¹í se pouze substitucí jiných znakù za |a| a~|b|)?}

\ex{Je dáno slovo. Chceme nalézt jeho nejdel¹í prefix, který je souèasnì suffixem.}

\ex{Jak zjistit, zda je zadané slovo~$\alpha$ periodické? Tím myslíme zda existuje
slovo~$\beta$ a èíslo $k>1$ takové, ¾e $\alpha = \beta^k$ (zøetìzení $k$~kopií øetìzce~$\beta$).}

\endexercises

\bye
