From 434fa5530ddb63b277667c36dd7944e600e480c7 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 9 Jan 2012 22:46:18 +0100 Subject: [PATCH] KMP: Prepsan uvod a sekce o znaceni --- 1-kmp/1-kmp.tex | 104 ++++++++++++++++++++++++++++-------------------- 1 file changed, 60 insertions(+), 44 deletions(-) diff --git a/1-kmp/1-kmp.tex b/1-kmp/1-kmp.tex index bcae029..3aea2ea 100644 --- a/1-kmp/1-kmp.tex +++ b/1-kmp/1-kmp.tex @@ -1,69 +1,84 @@ \input lecnotes.tex -\prednaska{1}{Vyhledávání v~textu}{(zapsal: Petr Jankovský)} +\prednaska{1}{Vyhledávání v~textu}{} -Nyní se budeme vìnovat následujícímu problému: v~textu délky $S$ (senì) 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è. +\h{Jehla v~kupce sena} -\h{Hloupý algoritmus} -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. +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. -\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. +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.) -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. +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é. -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¾ ne. +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. -{\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)$. +\h{Øetìzce a abecedy} -\h{Pomalý algoritmus} -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. +Aby se nám o~øetìzcových algoritmech lépe psalo, udìlejme si nejprve poøádek +v~terminologii okolo øetìzcù. -Tento algoritmus evidentnì funguje. Bì¾í v¹ak v~èase: $S$ mo¾ných zaèátkù, krát èas potøebný na~jedno porovná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 algoritmus è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. - -Nyní se pokusme najít takový algoritmus, který by byl tak rychlý, jako {\I Hloupý algoritmus}, ale chytrý, jako ten {\I Pomalý}. - -\h{Chytrý algoritmus} -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. - -\s{Pøíklad:} Vezmìme si napøíklad staré italské pøízvisko |barbarossa|, které znamená Rudovous. Pøedstavme si, ¾e takovéto slovo hledáme 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 øetì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. - -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. - -Aby se nám o~tìchto algoritmech lépe mluvilo a~pøedev¹ím psalo, pojïme si povìdìt nìkolik definic. - \s{Definice:} \itemize\ibull -\:{\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. +\:{\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 ale i rozlehlej¹í abecedy, napøíklad dnes bì¾ná znaková sada UniCode +má $2^{16}$ znakù, v~novìj¹ích verzích dokonce $2^{31}$ znakù. Je¹tì extrémnìj¹ím +zpùsobem pou¾ívají øetìzce lingvisté: na èeský text se nìkdy dívají jako na~slovo +nad abecedou, její¾ prvky jsou èeská slova. -\:{\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$. -\endlist -\s{Znaèení:} -Aby se nám nepletlo znaèení, budeme rozli¹ovat promìnné pro slova, promìnné pro písmenka a~promìnné pro èísla. +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$, ... . -\:$\iota$ bude oznaèovat \uv{jehlu} -\:$\sigma$ bude oznaèovat \uv{seno} -\:{\I Znaky} oznaèíme malými písmeny latinky $a$, $b$, \dots . -\:{\I Èísla} budeme znaèit velkými písmeny $A$, $B$, \dots . -\:{\I Délka slova} $\vert \alpha \vert$ pro $\alpha \in \Sigma^*$ je poèet jeho znakù. -\:{\I Prázdné slovo} znaèíme písmenem $\varepsilon$, $\vert \varepsilon \vert = 0$. +\:{\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$. -\:$\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]$. Jednu (èi obì) meze mù¾eme i~vynechat, tento zápis pak bude znamenat buï \uv{od zaèátku slova a¾ nìkam}, nebo \uv{odnìkud a¾ do~konce}: -%TODO - zaøadit pod pøedchozí bod -\:$\alpha[:k]$ je {\I prefix} obsahující prvních $k$ znakù slova $\alpha$ ($\alpha[0]$,\dots,$\alpha[k-1]$). -\:$\alpha[k:]$ je {\I suffix} obsahující znaky slova $\alpha$ poèínaje $k$-tým znakem a¾ do~konce. -\:$\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{XXX} -V¹imnìme si, ¾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í. 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. -\> $\alpha$ je {\I vlastní prefix} slova $\beta \equiv \alpha$ je prefix $\beta~\&~\alpha \neq \beta$. +\s{Pøíklad:} Vezmìme si napøíklad staré italské pøízvisko |barbarossa|, které znamená Rudovous. Pøedstavme si, ¾e takovéto slovo hledáme 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 øetì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. + +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. +Aby se nám o~tìchto algoritmech lépe mluvilo a~pøedev¹ím psalo, pojïme si povìdìt nìkolik definic. + \h{Vyhledávací automat (Knuth, Morris, Pratt)} {\I Vyhledávací automat} bude graf, jeho¾ vrcholùm budeme øíkat {\I 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 písmene. 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. @@ -274,5 +289,6 @@ $$\O\left(\sum_i~\iota_i~+~S~+~\sharp\