3 \prednaska{6}{Vyhledávání v textu}{(zapsal: Petr Jankovský)}
5 Nyní se budeme vìnovat následujícímu problému. V~textu délky $S$ (Senu) budeme chtít najít v¹echny výskyty hledaného slova délky $J$ (Jehly). Nejprve se podívejme na~jeden primitivní algoritmus, který nefunguje. Je ale zajímavé rozmyslet si, proè.
8 Zaèneme prvním písmenkem hledaného slova a~budeme postupnì procházet text, a¾ najdeme první výskyt poèáteèního písmenka. Poté budeme testovat, zda souhlasí i~písmenka dal¹í. Pokud nastane neshoda, v~hledaném slovì se vrátíme na~zaèátek a~v~textu pokraèujeme znakem, ve~kterém neshoda nastala. Podívejme se na~pøíklad.
10 \s{Pøíklad:} Budeme hledat slovo |jehla| v~textu |jevkupcejejehla|. Vezmeme si tedy první písmenko |j| v~hledaném slovì a~zjistíme, ¾e v~textu se nachází hned na~zaèátku. Vezmeme tedy dal¹í písmenko |e|, které se vyskytuje jako druhé i v~textu. Pøi tøetím písmenku ale narazíme na~neshodu. V~tuto chvíli tedy zresetujeme a~opìt hledáme výskyt písmenka |j|, tentokrát v¹ak a¾ od~tøetího písmene v~textu. Takto postupujeme postupnì dál, a¾ narazíme na~dal¹í |je|, které ov¹em není následováno písmenem |h|, tudí¾ opìt zresetujeme a~nakonec najdeme shodu s~celým hledaným øetìzcem. V~tomto pøípadì tedy algoritmus na¹el hledané slovo.
12 Tento algoritmus v¹ak zjevnì mù¾e hanebnì selhat. Mù¾e se stát, ¾e zaèneme porovnávat, a¾ v~jednu chvíli narazíme na~neshodu. Celý tento kus tedy pøeskoèíme. Pøi tom se ale v~tomto kusu textu mohl vyskytovat nìjaký pøekrývající se výskyt hledané \uv{jehly}. Hledejme napøíklad øetìzec |kokos| v~textu |clanekokokosu|. Algoritmus tedy zaène porovnávat. Ve~chvíli kdy najde prefix |koko| a~na~vstupu dostane |k|, dochází k~neshodì. Proto algoritmus zresetuje a~pokraèuje v~hledání od~tohoto znaku. Najde sice je¹tì výskyt |ko|, ov¹em s~dal¹ím písmenkem |s| ji¾ dochází k~neshodì a~algotimus sel¾e. Nesprávnì se toti¾ \uv{upnul} na~první nalezené |koko| a~s~dal¹ím |k| pak \uv{zahodil} i~správný zaèátek.
14 Máme tedy algoritmus, který i~kdy¾ je ¹patnì, tak funguje urèitì kdykoli se první písmenko hledaného slova v~tomto slovì u¾ nikde jinde nevyskytuje - co¾ |jehla| splòovala, ale |kokos| u¾ nikoliv.
16 {\I Hloupý algoritmus} se na~ka¾dé písmenko textu podívá jednou, tudí¾ èasová slo¾itost bude lineární s~délkou textu ve~kterém hledáme - tedy $\O(S)$.
19 Zkusíme algoritmus vylep¹it tak, aby fungoval správnì: pokud nastane nìjaká neshoda, vrátíme se zpátky tìsnì za~zaèátek toho, kdy se nám to zaèalo shodovat. To je ov¹em vlastnì skoro toté¾, jako brát postupnì v¹echny mo¾né zaèátky v~\uv{senì} a~pro ka¾dý z~nìj ovìøit, jestli se tam \uv{jehla} nachází èi nikoliv.
21 Tento algoritmus evidentnì funguje. Bì¾í v¹ak v~èase: $S$ mo¾ných zaèátkù, krát èas potøebný na~jedno potovnání (zda se na~dané pozici nenachází \uv{jehla}), co¾ nám mù¾e trvat a¾ $J$. Proto je èasová slo¾itost $\O(SJ)$. V praxi bude algoritus èasto rychlej¹í, proto¾e typicky velmi brzo zjistíme, ¾e se øetìzce neshodují, ale je mo¾né vymyslet vstup, kde bude potøeba porovnání opravdu tolik.
23 Nyní se pokusme najít takový algoritmus, který by byl tak rychlý, jako {\I Hloupý algoritmus}, ale chytrý, jako ten {\I Pomalý}.
26 Ne¾ vlastní algoritmus vybudujeme, zkusíme se cestou nauèit pøemý¹let o~øetìzcích obèas trochu pøekrouceným zpùsobem. Podívejme se na~je¹tì jeden pøíklad.
28 \s{Pøíklad:}Vezmìme si napøíklad staré italské pøízvisko |barbarossa|, které znamená Rudovous. Pøedstavme si, ¾e takovéto slovo hledám v~nìjakém textu, který zaèíná |barbar|. Víme, ¾e a¾ sem se nám hledaný øetìzec shodoval. Øeknìme, ¾e dal¹í písmenko textu se shodovat pøestane - místo |o| naèteme napøíklad opìt |b|. {\I Hloupý algoritmus} by velil vrátit se k~|a| a~od~nìj hledat dál. Uvìdomme si ale, ¾e kdy¾ se vracíme z~|barbar| do~|arbar| (tedy øetìzce, který ji¾ známe), mù¾eme si pøedpoèítat, jak dopadne hledání, kdy¾ ho pustíme na~nìj. V~pøedpoèítaném bychom tedy chtìli ukládat, ¾e kdy¾ máme øtìzec |arbar|, tak |ar| a~|r| nám do~hledaného nepasuje a~a¾~|bar| se bude shodovat. Tedy místo toho, abychom spustili nové hledání od~|a|, mù¾eme ho spustit a¾~od~|b|. Co víc, my dokonce víme, jak dopadne to - pokud toti¾ nastane neshoda po~pøeètení |barbar|, je to stejné, jako kdybychom pøeèetli pouze |bar|, na~které se (pùvodne neshodující se) |b| u¾ navázat dá. Kdyby se nedalo navázat ani tam, tak bychom opìt zkracovali... Nejen, ¾e tedy víme, kam se máme vrátit, ale víme dokonce i~to, co tam najdeme.
30 My¹lenka, ke které míøíme, je pøedpoèítat si nìjakou tabulku, která nám bude øíkat, jak se máme pøi hledání vracet a~jak to dopadne, a~pak u¾ jenom prohlédávat s~pou¾itím této tabulky.
32 Aby se nám o~pøepisových algoritmech lépe mluvila a~pøedev¹ím psalo, pojïme si povìdìt nìkolik definic.
36 \:{\I Abeceda $\Sigma$} je koneèná mno¾ina znakù \foot{Mù¾eme pøi tom jít a¾~do~extrémù. Pøíkladem extrémních abeced je binární abeceda slo¾ená pouze z~nul a~jednièek. Pøíklad z~druhého konce (který rádi dìlají lingvisti) je abeceda, která má jako abecedu v¹echna èeská slova. V¹echny èeské vìty, pak nejsou nic jiného, ne¾ slova nad touto abecedou. Pou¾itá abeceda tedy mù¾e být i~relativnì obrovská. Dal¹ím takovým pøíkladem mù¾e být unicode. Pro na¹e potøeby ale zatím budeme pøedpokládat, ¾e abeceda je nejen konstantnì velká, ale i~rozumnì malá. Budeme si moci tedy dovolit napøíklad indexovat pole znakem abecedy (kdybychom nemohli, tak bychom místo pole pou¾ili napøíklad hashovací tabulku, èi nìco podobného\dots) .}, ze~kterých tvoøíme text, øetìzce, slova.
39 \:{\I $\Sigma^*$} je mno¾ina v¹ech slov nad abecedou $\Sigma$. Èili mno¾ina v¹ech neprázdných koneèných posloupností znakù ze $\Sigma$.
42 Aby se nám nepletlo znaèení, budeme rozli¹ovat promìnné pro slova, promìnné pro písmenka a~promìnné pro èísla.
45 \:{\I Slova} budeme znaèit malými písmenky øecké abecedy $\alpha$,$\beta$... .
46 \:$\iota$ bude oznaèovat \uv{jehlu}
47 \:$\sigma$ bude oznaèovat \uv{seno}
48 \:{\I Znaky} oznaèíme malými písmeny latinky $a$,$b$\dots .
49 \:{\I Èísla} budeme znaèit velkými písmeny $A$, $B$\dots .
50 \:{\I Délka slova} $\vert \alpha \vert$ pro $\alpha \in \Sigma^*$ je poèet jeho znakù.
51 \:{\I Prázdné slovo} znaèíme písmenem $\varepsilon$, $\vert \varepsilon \vert = 0$.
52 \:{\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$.
53 \:$\alpha[k]$ je $k$-tý znak slova $\alpha$, indexujeme od $0$.
54 \:$\alpha[k:l]$ je podslovo zaèínající $k$-tým znakem a~$l$-tý znak je první, který v~nìm není. Jedná se tedy o podslovo skládající se z~$\alpha[k]$,$\alpha[k+1]$,\dots,$\alpha[l-1]$. Platí tedy: $\alpha[k:k]=\varepsilon$, $\alpha[k:k+1]=\alpha[k]$. Jedu (èi obì) meze mù¾eme i~vynechat, tento zápis pak bude znamenat buï \uv{od zaèátku slova a¾ nìkam}, nebo \uv{od nìkud a¾ do konce}.
55 \:$\alpha[:k]$ je {\I prefix} obsahující prvních $k$ znakù slova $\alpha$ ($\alpha[0]$,\dots,$\alpha[k-1]$) .
56 \:$\alpha[k:]$ je {\I suffix} obsahující znaky slova $\alpha$ poèínaje $k$-tým znakem a¾ do konce.
57 \:$\alpha[:] = \alpha$
60 V¹imnìme si, ¾e prázdné slovo je prefixem, suffixem i~podslovem jekéhokoliv slova vèetnì sebe sama.
61 Ka¾dé slovo je také prefixem, suffixem i~podslovem sebe sama.
62 To se nám nìkdy nebude hodit. Nìkdy budeme chtít øíct, ¾e nìjaké slovo je {\I vlastním} prefixem nebo suffixem. To bude znamenat, ¾e to nebude celé slovo.
64 \> $\alpha$ je {\I vlastní prefix} slova $\beta \equiv \alpha$ je prefix $\beta~\&~\alpha \neq \beta$.
66 \h{Vyhledávací automat (Knuth, Morris, Pratt)}
67 {\I Vyhledávací automat} bude graf, jeho¾ vrcholùm budeme øíkat stavy. Jejich jména budou prefixy hledaného slova a~hrany budou odpovídat tomu, jak jeden prefix mù¾eme získat z~pøedchozího prefixu pøidáním jednoho stavu. Poèáteèní stav je prázdné slovo $\varepsilon$ a~koncový je celá $\iota$. Dopøedné hrany grafu budou popisovat pøechod mezi stavy ve~smyslu zvìt¹ení délky jména stavu (dopøedná funkce $h(\alpha)$, urèující znak na~dopøedné hranì z $\alpha$). Zpìtné hrany grafu budou popisovat pøechod (zpìtná funkce $z(\alpha)$) mezi stavem $\alpha$ a~nejdel¹ím vlastním suffixem $\alpha$, který je prefixem $\iota$, kdy¾ nastane neshoda.
69 \figure{barb.eps}{Vyhledávací automat.}{4.2in}
73 \:$\alpha \leftarrow \varepsilon$.
74 \:Pro $x\in\sigma$ postupnì:
75 \:$\indent$Dokud $h(\alpha) \neq x~\&~\alpha \neq \varepsilon : \alpha \leftarrow z(\alpha)$.
76 \:$\indent$Pokud $h(\alpha) = x: \alpha \leftarrow \alpha x$.
77 \:$\indent$Pokud $\alpha = \iota$, ohlásíme výskyt.
80 \>Vstupem je $\iota$ hledané slovo (jehla) délky $J=\vert \iota \vert$ a $\sigma$ text (seno) délky $S=\vert \sigma \vert$.
81 \>Výstupem jsou v¹echny výskyty hledaného slova $\iota$ v textu $\sigma$: $\left\{ k\vert \sigma[k:k+J]=\iota \right\}$
83 Pojïme nyní dokázat, ¾e tento algoritmus správnì ohlásí v¹echny výskyty.
85 \s{Definice}: $\alpha(\tau) := $ stav automatu po pøeètení $\tau$
87 \s{Invariant:} Pokud algoritmus pøeète nìjaký vstup, nachází se ve stavu, který je nejdel¹ím suffixem pøeèteného vstupu, který je nìjakým stavem.
88 $\alpha(\tau) =$ nejdel¹í stav (nejdel¹í prefix jehly), který je suffixem $\tau$ (pøeèteného vstupu).
89 Pojïme si rozmyslet, ¾e z tohoto invariantu ihnet plyne, ¾e algoritmus najde to, co má. Kdykoli toti¾ ohlásí nìjaký výskyt, tak tam tento výskyt opravdu je. Kdykoli pak má nìjaký výskyt ohlásit, tak se v této situaci jako suffix toho právì pøeèteného textu vyskytuje hledané slovo, pøièem¾ hledané slovo je urèitì stav a zároveò nejdel¹í ze v¹ech existujících stavù. Tak¾e invariant opravdu øíká, ¾e jsme právì v koncovém stavu a algoritmus nám tedy ohlásí výskyt.
92 Indukcí podle kroku algoritmu. Na zaèátku pro prázdný naètený vstup invariant triviálnì platí, tedy prázdný suffix $\tau$ je prefixem $\iota$. V~kroku $n$ máme naètený vstup $\tau$ a k~nìmu naèteme znak $x$. Invariant nám øíká, ¾e nejdel¹í stav, který je suffixem, je nejdel¹í suffix, který je stavem. Nyní se ptáme, jaký je nejdel¹í stav, který se dá \uv{napasovat} na konec øetìzce $\tau x$. Kdykoli v¹ak takovýto suffix máme, tak z nìj mù¾eme $x$ na konci odebrat, èím¾ dostaneme suffix slova $\tau$.
94 \>Tedy: pokud $\beta$ je neprázdným suffixem slova $\tau x$, pak $\beta = \gamma x$, kde $\gamma$ je suffix $\tau$.
96 Suffix, který máme sestrojit, tedy vznikne z nìjakého suffixu slova $\tau$ pøipsáním~$x$. Chceme najít nejdel¹í suffix slova $\tau x$, který je stavem, tak¾e chceme najít i nejdel¹í suffix pùvodního slova $\tau$, za který se dá pøidat $x$ tak, aby vy¹lo jméno stavu. Staèí tedy u¾ jen \uv{probírat} suffixy $\tau$ od nejdel¹ího po nejkrat¹í, zkou¹et k nim pøidávat $x$ a a¾ to pùjde, tak jsme na¹li nejdel¹í suffix $\tau x$. Pøesnì toto ov¹em algoritmus dìlá, nebo» zpìtná funkce mu v¾dy øekne nejbli¾¹í krat¹í suffix, který je stavem. Pokud pak nemù¾eme $x$ pøidat ani do $\varepsilon$, pak je øe¹ením prázdný suffix. Algoritmus tedy funguje. \qed
98 Nyní pojïmì zkoumat to, jak je ve skuteènosti ná¹ algoritmus rychlý. K tomu bychom si ale nejdøív mìli øíct, jak pøesnì budeme automat reprezentovat. V algoritmu vystupují nìjaká porovnávání stavù, pøièem¾ není úplnì jasné, jak zaøídit, aby v¹e trvalo konstantnì dlouho. Vyjde nám to ale docela snadno. K reprezentaci automatu nám toti¾ budou staèit pouze dvì pole.
100 \s{Reprezentace automatu:}
101 Oèíslujeme si stavy délkami pøíslu¹ných prefixù tedy $0 \dots J$. Poté je¹tì potøebujeme nìjakým zpùsobem zakódovat dopøedné a zpìtné hrany. Vzhledem k tomu, ¾e z ka¾dého vrcholu vede v¾dy nejvý¹e jedna dopøedná a nejvý¹e jedna zpìtná, tak nám evidentnì staèí pamatovat si pro ka¾dý typ hran pouze jedno èíslo na vrchol. Budeme mít tedy nìjaké pole dopøedných hran, které nám pro ka¾dý stav øekne, jakým písmenkem je nadepsaná dopøedná hrana ze stavu $I$ do $I+1$. To jsou ale pøesnì písmenky jehly, tak¾e si staèí pamatovat jehlu samotnou. Èili z $I$ do $I+1$ vede hrana nadepsaná $\iota [I]$. Pro zpìtné hrany pak budeme potøebovat pole $Z$, které nám pro stav $I$ øekne èíslo stavu, do kterého vede zpìtná hrana. Tedy $Z[I]$ je cíl zpìtné hrany ze stavu $I$.
102 S touto reprezentací ji¾ doká¾eme na¹i hledací proceduru pøímoèaøe pøepsat tak, aby sahala pouze do tìchto dvou polí:
105 \:Pro znaky $x$ z textu:
106 \:$\indent$Dokud $\iota[I] \neq x~\&~I \neq 0: I \leftarrow Z[I]$.
107 \:$\indent$Pokud $\iota[I] = x, pak I \leftarrow I + 1$.
108 \:$\indent$Pokud $I = J$, ohlásíme výskyt.
111 Zatím se v algoritmu je¹tì skrývá drobná chyba -- toti¾ algoritmus se obèas zeptá na dopøednou hranu z posledního stavu. Pokud jsme právì ohlásili výskyt (jsme tedy v posledním stavu) a pøijde nìjaký dal¹í znak, algoritmus se ptá, zda je roven tomu, co je na dopøedné hranì z posledního stavu. Ta ale ov¹em neexistuje. Jednodu¹e to ale napravíme tak, ¾e si pøidáme fiktivní hranu, na které se vyskytuje nìjaké \uv{nepísmenko} -- nìco co se nerovná ¾ádnému jinému písmenku. Zajistíme tak, ¾e se po této hranì nikdy nevydáme. Dodefinujeme tedy $\iota[J]$ odli¹nì od v¹ech znakù. (V jazyce C se toto dodefinování provede vlastnì zadarmo, nebo» ka¾dý øetìzec je v nìm ukonèen znakem s kódem nula, který se ve vstupu nevyskytne\dots Algoritmus bude tedy fungovat i bez tohoto dodefinování. V jiných jazycích je ale na nìj tøeba nezapomenout!)
113 \s{Lemma:} Funkce Hledej bì¾í v~èase $\O(S)$.
116 Fonkce {\I Hledej} chodí po dopøedných a zpìtných hranách. Dopøedných hran projdeme urèitì maximálnì tolik, kolik je délka sena. Pro ka¾dý znak pøeètený ze sena toti¾ jdeme nejvý¹e jednou po dopøedné hranì. Se zpìtnými hranami se to má tak, ¾e na jeden pøeètený znak z textu se mù¾eme po zpìtné hranì vracet maximálnì $J$-krát. Z tohoto by nám v¹ak vy¹la slo¾itost $\O(JS)$, èím¾ bychom si nepomohli. Zachrání nás ale pøímoèarý potenciál. Uvìdomme si, ¾e chùze po dopøedné hranì zvý¹í $I$ o jedna a chùze po zpìtné hranì $I$ sní¾í alespoò o jedna. Vzhledem k tomu, ¾e $I$ není nikdy záporné a na zaèátku je nulové, zjistíme, ¾e krokù zpìt mù¾e být maximálnì tolik, kolik krokù dopøedu. Èasová slo¾itost hledání je tedy lineární vzhledem k délce sena. \qed
118 Nyní nám zbývá na první pohled malièkost -- toti¾ zkonstruovat automat. Zkonstruovat dopøedné hrany zvládneme zjevnì snadno, jsou toti¾ explicitnì popsané hledaným slovem. Tì¾¹í u¾ to bude pro hrany zpìtné. Vyu¾ijeme k tomu následující pozorování:
121 Pøedstavme si, ¾e automat u¾ máme hotový a tím, ¾e budeme sledovat jeho chování, chceme zjistit, jak v nìm vedou zpìtné hrany.
122 Vezmìme si nìjaký stav $\beta$. To, kam z nìj vede zpìtná hrana zjistíme tak, ¾e spustíme automat na øetìzec $\beta$ bez prvního písmenka a stav, ve kterém se automat zastaví je pøesnì ten, kam má vést i zpìtná hrana z $\beta$. Jinými slovy víme, ¾e $z(\beta) = \alpha (\beta[1:])$.
123 Proè takováto vìc funguje? V¹imìme si, ¾e definice $z$ a to, co nám o $\alpha$ øíká invariant je témìø toto¾ná -- $z(\beta)$ je nejdel¹í vlastní suffix $\beta$, který je stavem, $\alpha(\beta)$ je nejdel¹í suffix $\beta$, který je stavem. Jediná odli¹nost je v tom, ¾e definice $z$ narozdíl od definice $\alpha$ zakazuje nevlastní suffixy. Jak nyní vylouèit suffix $\beta$, který by byl roven $\beta$ samotné? Zkrátíme $\beta$ o první znak. Tím pádem v¹echny suffixy $\beta$ bez prvního znaku jsou stejné jako v¹echny vlastní suffixy $\beta$.
125 K èemu je toto pozorování dobré? Rozmysleme si, ¾e pomocí nìj u¾ doká¾eme zkonstruovat zpìtné hrany. Není to ale trochu divné, kdy¾ pøi simulování automatu na øetìzec bez prvního znaku u¾ zpìtné hrany potøebujeme? Není. Za chvíli zjistíme, ¾e takto mù¾eme zji¹»ovat zpìtné hrany postupnì s tím, ¾e pou¾íváme v¾dy jenom ty, které jsme u¾ sestrojili.
126 Takovémuhle pøístupu, kdy pøi konstruování chtìného u¾ pou¾íváme to, co chceme sestrojit, ale pouze ten kousek, který ji¾ máme hotový, se v angliètinì øíká {\I bootstrapping}\foot{Z tohoto slova vzniklo i {\I bootování} poèítaèù, kdy operaèní systém v podstatì zavádí sám seme. Bootstrap znamená èesky ¹truple -- tedy oèko na konci boty, které slou¾í k usnadnìní nazouvání. A jak souvisí ¹truple s algoritmem? To se zase musíme vrátit k pøíbìzích o baronu Prá¹ilovi, mezi nimi¾ je i ten, ve kterém baron Prá¹il vypráví o tom, jak sám sebe vytáhl z ba¾iny za ¹truple. Stejnì tak i my budeme algoritmus konstruovat tím, ¾e se budeme sami vytahovat za ¹truple, tedy bootstrappovat.}.
127 V¹imnìme si, ¾e pøi výpoètu se vstupem $\beta$ projde automat jenom prvních $\vert \beta \vert$ stavù. Automat se evidentnì nemù¾e dostat dál, proto¾e na ka¾dý krok dopøedu (doprava) spotøebuje písmenko $\beta$. Tak¾e krokù doprava je maximálnì tolik, kolik je $\vert \beta \vert$. Jinými slovy kdybychom ji¾ mìli zkonstruované zpìtné hrany pro prvních $\vert \beta \vert$ stavù (tedy $0 \dots \vert \beta \vert - 1$), tak pøi tomto výpoètu, kt
128 erý potøebujeme na zkonstuovíní zpìtné hrany z $\beta$, je¹tì tuto zpìtnou hranu nemù¾eme potøebovat. Vystaèíme si s tìmi, které ji¾ máme zkonstruované.
129 Nabízí se tedy zaèít zpìtnou hranou z prvního znaku (která vede evidentnì do $\varepsilon$), pak postupnì brát dal¹í stavy a pro ka¾dý z nich si spoèítáme kdy spustíme automat na jméno stavu bez prvního znaku a tím získáme dal¹í zpìtnou hranu. Toto funguje, ale je to kvadratické \dots. Máme toti¾ $J$ stavù a pro ka¾dý z nich nám automat bì¾í v èase a¾ lineárním s $J$. Jak z toho ven?
130 Z prvního stavu povede zpìtná funkce do $\varepsilon$. Prodl¹í stavy chceme spoèítat zpìtnou funkci. Z druhého stavu $\iota[0:2]$ tedy automat spustíme na $\iota[1:2]$, dále pak na $\iota[1:3]$, $\iota[1:4]$, atd. Ty øetìzce, pro které potøebujeme spo¹tìt automat, abychom dostali zpìtné hrany, jsou tedy ve skuteènosti takové, ¾e ka¾dý dal¹í dostaneme roz¹íøením pøedchozího o jeden znak. To jsou ale pøesnì ty stavy, kterými projde automat pøi spracovávání øetezce $\iota$ od prvního znaku dál. Jedním prùchodem automatu nad jehlou bez prvního písmenka, se tím pádem rovnou dozvíme v¹echny údaje, které potøebujeme.
131 Z pøedchozího pozorování plyne, ¾e nikdy nebudeme potøebovat zpìtnou hranu, kterou jsme je¹tì nezkonstruovali a jeliko¾ víme, jedno prohledání trvá lineárnì s délkou toto v èem hledáme, tak toto celé pobì¾í v lineárním èase. Dostaneme tedy následující algoritmus:
133 \s{Konstrukce zpìtné funkce:}
135 \:$Z[0] \leftarrow ?$, $Z[1] \leftarrow 0.$
138 \:$\indent$$I \leftarrow krok( I , \iota [k])$
139 \:$\indent$$Z[k] \leftarrow I$
142 Zaèínáme tím, ¾e nastavíme zpìtnou hranu z prvních dvou stavù, pøièem¾ $z[0]$ je nedefinované, proto¾e tuto zpìtnou hranu nikdy nepou¾íváme. Dále postupnì simulujeme výpoèet automatu nad slovem bez prvního znaku a po ka¾dém kroku se dozvíme novou zpìtnou hranu. {\I Krokem} automatu pak není nic jiného ne¾ vnitøek (3. a 4. bod) na¹í hledací procedury. To, kam jsme se dostali pak zaznamenáme jako zpìtnou funkci z $k$.
143 Èili pou¹tíme automat nanjehlu bez prvního písmenka, provedeme v¾dy jeden krok automatu (pøes dal¹í písmenko jehly) a zapamatujeme si, jakou zpìtnou funkci jsme zrovna dostali. Díky pozorováním navíc víme, ¾e zpìtné hrany konstruujeme správnì, nikdy nepou¾ijeme zpìtnou hranu, kterou jsme je¹tì nesestrojili a víme i to, ¾e celou konstrukci zvládneme v lineárním èase s délkou jehly.
145 \s{Vìta:} Algoritmus KMP najde v¹echny výskyty v èase $O(J+S)$.
146 Linéá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í.
152 \s{Vysvìtlení:} V¹imnìte si, ¾e $z(i)$ je pøesnì stav, do nej¾ se dostaneme pøi spu¹tìní na¹eho vyhledávacího algoritmu na øetìzec $\iota [2:i]$, èili na $i$-tý prefix bez prvního písmenka. Proè to tak je? Zpìtná funkce øíká, jaký je nejdel¹í vlastní suffix daného stavu, který je také stavem, zatímco $\alpha$ oznaèuje nejdel¹í suffix textu, který je stavem. Tyto dvì vìci se pøeci li¹í jen v~tom, ¾e ta druhá pøipou¹tí i nevlastní suffixy, a právì tomu zabráníme odstranìním prvního znaku. Tak¾e $z()$ získáme tak, ¾e spustíme vyhledávání na èást samotného slova $\iota$. Jen¾e k~vyhledávání zase potøebujeme zpìtnou funkci $z$. Proto budeme zpìtnou funkci vytváøet postupne od nejkrat¹ích prefixù. Zøejmì $z(1) = \varepsilon$. Pokud ji¾ máme $z(i)$, pak výpoèet $z(i+1)$ odpovídá spu¹tení automatu na slovo délky $i$ a pritom budeme zpìtnou funkci potøebovat jen pro stavy délky $i$ nebo men¹í, pro které ji ji¾ máme hotovou.
154 Navíc nemusíme pro jednotlivé prefixy spou¹tìt výpoèet v¾dy znovu od zaèátku, proto¾e $(i+1)$-ní prefix
155 je prodlou¾ením $i$-tého prefixu o~jeden znak. Staèí tedy spustit algoritmus na celý øetìzec $\iota$ a sledovat, jakými stavy bude procházet. To budou pøesnì hodnoty zpìtné funkce. Vytvoøení zpìtné funkce se tak nakonec zredukovalo na jediné vyhledávání v~textu o~délce $J-1$, a proto pobì¾í v èase $\O(J)$. Èasová slo¾itost celého algoritmu tedy bude $\O(S+J)$.
157 \h{Algoritmus Rabin \& Karp}
158 Tento algoritmus funguje tak, ¾e porovnává hash hledaného øetìzce s~hashem aktuálního podøetìzce (\uv{posuvné okénko} stejné délky jako hledaný øetìzec) v~textu a aktuální podøetìzec porovná se vzorkem pouze v~pøípadì, kdy¾ mají shodný hash. Kdy¾ si zvolíme tu správnou hashovací funkci, budeme moci vypoèítat hash následujíciho podøetìzce na základe hashe toho aktuálního. Jako hashovací funkci $h: \Sigma^J \rightarrow \bb Z$ pou¾ijeme následující: $h(x_{0},...,x_{J-1}) = ( \sum_{i=0}^{J-1} x_{i}.p^{J-1-i}) \bmod N$, kde $N$ je velikost prostoru, do kterého hashujeme. Jak zjistíme hash následujícího podøetìzce?
160 \:$h = x_{0}.p^{J} + x_{1}.p^{J-1} + ... + x_{J-1}.p^{1}$
161 \:$h^{'} = x_{1}.p^{J} + x_{2}.p^{J-1} + ... + x_{J}.p^{1}$
162 \:$h^{'} = (h - x_{0}.p^{J}).p + x_{J}.p^{1}$
164 Tady mù¾eme vidìt, ¾e hash následujícího øetìzce lze pøepoèítat na základì toho pøedchozího v konstantním èase.
165 Èasová slo¾itost je v nejlep¹ím pøípadì lineární vzhledem k~délce textu, zatímco nejhor¹í pøípad mú¾e trvat a¾ $\Theta(JS)$.
projects / ads2.git / blob