Miroslav Beneˇs, 2001 Informatika I/2/31
Vyhled´ av´ an´ı v textu Obsah ´ 1. Uvod 2. Z´akladn´ı pojmy 3. Algoritmy (a) Naivn´ı algoritmus (b) Knuth-Morris-Pratt˚ uv algoritmus (KMP) (c) Boyer-Moore˚ uv algoritmus (BM) (d) Baeza-Yates-Gonnet˚ uv algoritmus (BYG) (e) Quicksearch 4. Srovn´an´ı algoritm˚ u 5. Z´avˇer 6. Literatura
´ I. Uvod V dneˇsn´ı dobˇe, kdy se vˇetˇsina dokument˚ u (aˇt uˇz na u ´ˇradech nebo v bˇeˇzn´ ych podm´ınk´ach) vede na poˇc´ıtaˇc´ıch, a tedy v elektronick´e podobˇe, je potˇreba m´ıti dostateˇcnˇe siln´en´astroje k tomu, aby se v dan´ ych dokumentech vyhledal nˇejak´ y text (slovo, vˇeta apod.)v co nejkratˇs´ım moˇzn´em ˇcase. Proto se ˇradu let vyv´ıj´ı r˚ uzn´e algoritmy, kter´e tento u ´kols odliˇsn´ ymi u ´spˇechy pln´ı. Tyto algoritmy jsou bˇeˇzn´emu uˇzivateli poˇc´ıtaˇce schov´any v jin´ ych vˇetˇs´ıch celc´ıch jako jsour˚ uzn´e textov´e editory, kde je obˇcas nutn´e nˇejak´e to slovo v textu vyhledat (potaˇzmo zamˇenitza jin´e). Dalˇs´ım pˇr´ıkladem mohou b´ yt vyhled´avac´ı syst´emy v knihovn´ach, vyhled´av´an´ı v datab´az´ıch, vˇselijak´e vyhled´avac´ı servery apod. Principy vyhled´av´an´ı vzork˚ u v textu se tak´e pouˇz´ıvaj´ı i v jin´ ych oborech neˇz v informatice, pˇr´ıkladem m˚ uˇze b´ yt napˇr´ıkladhled´an´ı ”vzork˚ u” v DNA ˇsroubovici. Z toho vypl´ yv´a, ˇze vyhled´av´an´ı v textu je pomˇernˇe rozs´ahl´ y probl´em o jehoˇz uˇziteˇcnostijistˇe nen´ı sporu. Proto je urˇcitˇe uˇziteˇcn´e uv´est si nˇejak´e pˇr´ıklady algoritm˚ u, kter´e tentoprobl´em ˇreˇs´ı, popsat je a porovnat. Algoritmy se mohou dˇelit do nˇekolika moˇzn´ ych kategori´ı podle toho za jak´ ym u ´ˇcelem se pouˇz´ıvaj´ı nebo podle sv´eho p˚ uvodu. M˚ uˇzeme se tedy setkat s algoritmy, kter´e vyhled´avaj´ıpouze jeden vzorek v dan´em textu, v jin´ ych pˇr´ıpadech je moˇzno vyhled´avat mnoˇzinu v´ıcevzork˚ u. Rozd´ıl je tak´e v tom, ˇze nˇekter´e algoritmy naleznou pouze prvn´ı v´ yskyt vzorkuv textu, jin´e naleznou vˇsechny v´ yskyty.Existuj´ı algoritmy, kter´e se inspirovaly i jin´ ymi obory informatiky jako je napˇr. teorieautomat˚ u.
1
V tomto ˇcl´anku bych se r´ad vˇenoval zejm´ena dvˇema algoritm˚ um. Prvn´ım je KnuthMorris-Pratt˚ uv algoritmus (KMP), druh´ ym je Boyer-Moore˚ uv algoritmus (BM). Spoleˇcn´ ym rysem obou jeskuteˇcnost, ˇze vyhled´avaj´ı vˇsechny v´ yskyty jednoho vzorku v dan´em textu. Na KMP se d´anahl´ıˇzet jako na upraven´ y koneˇcn´ y (v tomto pˇr´ıpadˇe vyhled´avac´ı) automat. BM se na druhoustranu jev´ı jako naivn´ı vyhled´avac´ı algoritmus (viz d´ale) se dvˇemid˚ uleˇzit´ ymi heuristikami. Pˇredstavitelem skupiny algoritm˚ u, kter´e vyhled´avaj´ı celou mnoˇzinu vzork˚ u je napˇr.algoritmus Aho-Corasickov´e, kter´ y je zaloˇzen na poznatc´ıch pr´avˇe z teorie automat˚ u. V dalˇs´ım odstavci bych r´ad zm´ınil dalˇs´ı dva zaj´ımav´e a relativnˇe nov´e algoritmy: Baeza-YatesGonnet, kter´ y je zaloˇzen na vyhled´av´an´ı pomoc´ı bitov´ ych masek, a algoritmusQuicksearch, jehoˇz autorem je D.M. Sunday. ˇ Nejprve si vˇsak zavedme nˇekolik d˚ uleˇzit´ ych pojm˚ u a definic, kter´e se budou hodit k pozdˇejˇs´ımu popisu a zkoum´an´ı algoritm˚ u. >>>Obsah
II. Z´ akladn´ı pojmy I pˇresto, ˇze vˇetˇsina lid´ı v principu ch´ape, co vyhled´av´an´ı v textu je, definujme sitento pojem alespoˇ n trochu pˇresnˇeji a form´alnˇeji. Nejprve si vysvˇetl´ıme nˇekter´e z´akladn´ı pojmy potˇrebn´e pro popis dan´eho probl´emu. Abecedou Σ rozum´ıme koneˇcnou mnoˇzinu znak˚ u. Napˇr´ıklad Σ ={0,1} nebo Σ ={a,b,...,z}. Prvky t´eto mnoˇziny se ˇcastonaz´ yvaj´ı znaky, p´ısmena nebo symboly. Slovem v abecedˇe Σ je m´ınˇenakoneˇcn´a posloupnost znak˚ u z t´eto abecedy. Pr´azdn´ ym slovem se rozum´ı posloupnost d´elky0 a obvykle se znaˇc´ı ( nepatˇr´ı do Σ). Mnoˇzina vˇsech slov v abecedˇe Σ se znaˇc´ı Σ∗ . Na t´eto mnoˇzinˇe je definov´anaoperace skl´ ad´ an´ı (konkatenace), kter´a dvˇema slov˚ um x a y d´elek m a n pˇriˇrad´ı slovo xy d´elky m+n. Tato operace je asociativn´ı (to znamen´a, ˇze (xy)z je to sam´eslovo jako x(yz)) a pro v´ıce neˇz jednoprvkovou abecedu nekomutativn´ı(v pˇr´ıpadˇe jednoprvkov´e abecedy: aa”=” aa, pokud Σ ={a}; v pˇr´ıpadˇe v´ıceprvkov´e napˇr. xy nen´ı rovno yx pro x, y navz´ajem r˚ uzn´a). Roli jednotkov´eho prvku t´eto operace hraje pr´azdn´e slovo, tedy x = x=x pro kaˇzd´e x z . Nechˇt x je prvkem Σ∗ . Potom d´elkou slova x rozum´ımepoˇcet znak˚ u v x. Zapisujeme |x|. Tedy jak bylo poznamen´ano | |=0. ˇ Rekneme, ˇze slovo x z Σ∗ je pˇ redponou (prefixem)slova y z Σ∗ , existuje-li takov´e slovo u ∗ zΣ , ˇze xu=y. Takov´e u zˇrejmˇe existuje nejv´ yˇse jednoa je-li nepr´azdn´e, ˇr´ık´ame, ˇze xvlastn´ı pˇ redpona. Obdobnˇe, ˇrekneme, ˇze slovo x z Σ∗ je pˇ r´ıponou (suffixem)slova y z Σ∗ , existujeli takov´e slovo v zΣ∗ , ˇze vx=y. Opˇet takov´e v existuje nejv´ yˇse jednoa je-li nepr´azdn´e, mluv´ıme o vlastn´ı pˇ r´ıponˇ e.Zˇrejmˇe plat´ı, ˇze je vlastn´ı pˇr´ıponou a pˇredponou kaˇzd´eho slova z Σ∗ . Podobnˇe kaˇzd´e slovo je svou jedinou nevlastn´ı pˇr´ıponou i pˇredponou. ˇ Pro pˇr´ıklad si uvedme, ˇze slovo ab je pˇredponou slova abbdad a to pˇredponou vlastn´ı. Z´aroveˇ n je vlastn´ı pˇr´ıponou slova abbab. ˇ Pro dalˇs´ı u ´ˇcely si zavedme jeˇstˇe jeden jednoduch´ y pojem, prefix o k znac´ıch. Prefix vzorku P[1..m] o k znac´ıch, tedy P[1..k],budeme znaˇcit Pk . Podobnˇe budeme m´ıt tento pojem i pro prohled´avan´ y text( Tk ). ˇ Nyn´ı se vratme k formulaci probl´emu vyhled´av´an´ı v textu. Nechˇt m´ame danou abecedu Σ a t´ım i mnoˇzinu Σ∗ . Pˇredpokl´adejme, ˇze m´ame d´any dva textov´e ˇretˇezce (nejlepˇs´ı je 2
ˇ ezec P = p1 ...pm (nebo jako pole znak˚ pˇredstavit si je jako pole jednotliv´ ych znak˚ u). Retˇ u ˇ P[1..m]) budeme naz´ yvat vzorek. Jeho d´elka je m. Retˇezec T = t1 ...tn ( T[1..n]) bude prohled´avan´ y textd´elky n. Oba ˇretˇezce jsou slova z Σ∗ . ˇ ık´ame, ˇze vzorek P se v textu T nach´ R´ az´ı s posunut´ım s (jin´ ymi slovy ˇreˇceno, nach´az´ı se v textu T na pozici s+1), jestliˇze 0<=s<=n-m a z´aroveˇ n T[s+1..s+m]=P[1..m] (pro vˇsechna j 1<=j<=m ts + j=pj ). Pokud se vzorek P v prohled´avan´em textu T nach´az´ı naz´ yv´ame splatn´ ym posunem . Jinak je tento posun neplatn´ y. Probl´em vyhled´av´an´ı jednoho vzorku v textu lze tedy formulovat jako probl´em nalezen´ı vˇsech platn´ ych posun˚ u, se kter´ ymi se vzorek P nach´az´ı v textu T.
Tento obr´azek zn´azorˇ nuje pˇredchoz´ı definici o vyhled´av´an´ı v textu. Vzorek P=bbcabse nach´az´ı v textu T s platn´ ym posunem 4, neboli na 5. pozici. >>>Obsah
III. Algoritmy Po vysvˇetlen´ı vˇsech potˇrebn´ ych pojm˚ u a formulaci dan´eho probl´emu se m˚ uˇzeme zaˇc´ıt zab´ yvat jednotliv´ ymi algoritmy. Nejprve se zlehka pod´ıv´ame na naivn´ı vyhled´avac´ı algoritmus a jehoˇcasovou sloˇzitost, aby se urˇcit´ ym zp˚ usobem zd˚ uvodnila potˇreba lepˇs´ıch a efektivnˇejˇs´ıchvyhled´ avac´ıch algoritm˚ u. Pot´e probereme jiˇz zm´ınˇen´e dva algoritmy (Knuth-Morris-Pratt aBoyer-Moore). 1. Naivn´ı algoritmus Tento algoritmus je v podstatˇe v´ ysledkem prvn´ı myˇslenky, kter´a kaˇzd´eho napadne, kdyˇz dostaneza u ´kol navrhnout algoritmus na vyhled´av´an´ı v textu. Jednoduˇse ˇreˇceno spoˇc´ıv´a v prozkoum´an´ıvˇsech moˇznost´ı (ne tedy doslova, ale v principu ano). Jak tomu u takov´ ych algoritm˚ u b´ yv´a,jeho ˇcasov´a sloˇzitost nen´ı pˇr´ıliˇs dobr´a. Myˇslenka je jednoduch´a. Budeme proch´azet zadan´ y text a na kaˇzd´e pozici zkontrolujeme, zdatu nezaˇc´ın´a dan´ y vzorek. Princip zn´azorˇ nuje n´asleduj´ıc´ı obr´azek.
Jak je z obr´azku vidno, vzorek se jakoby postupnˇe posouv´a pod dan´ ym textem a na 3
kaˇzd´em m´ıstˇese kontroluje, zda se zde nenach´az´ı pˇr´ısluˇsn´ y vzorek. V tomto pˇr´ıkladu byl vzorek nalezen nadruh´e pozici (s posunem 1, pˇr´ıpad (b)). V ostatn´ıch pˇr´ıpadech vˇzdy nastala na urˇcit´em m´ıstˇe vzorku kolize. Neefektivnost tohoto algoritmu spoˇc´ıv´a pr´avˇe ve skuteˇcnosti, ˇze pokud naraz´ım na neshodu, posunuvzorek pouze o jedno m´ısto doprava a zaˇcnu porovn´avat znovu, a to aˇz do konce prohled´avan´ehotextu. T´ımto postupem se tedy nevyuˇz´ıvaj´ı informace, kter´e byly z´ısk´any v pˇredchoz´ım kroku.Napˇr´ıklad u naˇseho obr´azku po tom, co jsem naˇsel vzorek v pˇr´ıpadˇe (b), nemus´ım kontrolovatpozici o jednu vpravo, ale mohu pˇristoupit aˇz k n´akresu pod p´ısmenem (d). Tyto informace, kter´e z´avis´ı pr´avˇe na zadan´em vzorku se snaˇz´ı vyuˇz´ıvat efektivnˇejˇs´ı algoritmy, kter´e si zde uk´aˇzeme. Naivn´ı algoritmus by v pseudok´odu mohl vypadat asi n´asledovnˇe: (1) (2) (3) (4) (5)
n = length(T) m = length(P) for s = 1 to n-m+1 if T[s..s+m-1] == P[1..m] then print("Vzorek se nach´ az´ ı na pozici", s)
Nyn´ı se k´od rozeberme a pod´ıvejme se na ˇcasovou sloˇzitost algoritmu. Prvn´ı dvˇe ˇr´adky obstar´avaj´ıpouze uloˇzen´ı d´elky obou textov´ ych ˇretˇezc˚ u do promˇenn´ ych n a m.Posouv´an´ı vzorku pod textem zajiˇsˇtuje cyklus, kter´ y zaˇc´ın´a na ˇr´adce (3). Provede se pˇresnˇe(n-m+1)-kr´at, coˇz je ˇ adka (5) jen informujeo nalezen´ı vzorku poˇcet pozic, na kter´ ych se m˚ uˇze vzorek vyskytovat. R´ v textu. Pro urˇcen´ı ˇcasov´e sloˇzitosti je kl´ıˇcov´a ˇr´adka ˇc´ıslo 4. Zde seprov´ad´ı porovn´av´an´ı vzorku s dan´ ym textem. Tento pseudoz´apis m˚ uˇze ve skuteˇcnosti b´ yt while cyklus, kter´ y porovn´av´ a jednotliv´e znaky dokud nenaraz´ı na neshodu nebo na konec vzorku, v tomtopˇr´ıpadˇe se vykon´ a ˇr´adka (5). Je snadn´e nahl´ednout, ˇze v nejhorˇs´ım pˇr´ıpadˇe (to je ˇze vˇzdy projduvˇsechny znaky ˇ ve vzorku) se while cyklus provede m-kr´at. Casov´ a sloˇzitost v nejhorˇs´ım pˇr´ıpadˇeje tedy O((n-m+1)*m). >>>Obsah 2. Knuth-Morris-Pratt˚ uv algoritmus (KMP) Mezi prvn´ımi, kteˇr´ı si uvˇedomili, ˇze informace, kter´e z´ısk´av´a naivn´ı algoritmus sv´ ym porovn´av´ an´ımznak po znaku, mohou b´ yt velmi cenn´e pro n´avrh efektivn´ıho algoritmu, byl pr´avˇe Knuth se sv´ ymispoleˇcn´ıky Morrisem a Prattem. Jejich n´apad spoˇc´ıval v tom, ˇze pokud se tyto informace vyuˇzij´ıspr´avn´ ym zp˚ usobem, m˚ uˇze se vzorek nad prohled´avan´ ym textem posouvat i o v´ıce neˇz pouze o jedenznak doprava. T´ım se v´ yznamnˇe zkr´at´ı doba potˇrebn´a k prohled´an´ı textu. Tak´e je zbyteˇcn´e sev prohled´avan´em textu vracet ke znak˚ um, kter´e jiˇz byly analyzov´any tak jak to ˇcin´ı naivn´ı algoritmus. Toto vracen´ı spoˇc´ıv´a ve skuteˇcnosti, ˇze pokud pˇri porovn´av´an´ı vzorku s dan´ ym textemnaraz´ım na neshodu, vr´at´ım se zpˇet na zaˇc´atek vzorku a ten posunu o jedno m´ısto doprava. Tato ˇcinnost je zˇrejmˇe zbyteˇcn´a, neboˇt j´a jiˇz m´am informaci o pˇredchoz´ıch znac´ıch, staˇc´ı jipouze dostateˇcnˇe vyuˇz´ıt. Vracen´ı se v textu m˚ uˇze pˇrin´est i dalˇs´ı probl´em, kter´ y nen´ı na prvn´ı pohled zˇrejm´ y. Pˇri zpracov´av´an´ı delˇs´ıho textu, urˇcitˇe nen´ı tento text v pamˇeti poˇc´ıtaˇce cel´ y.Ze souboru se naˇc´ıt´a po kusech do nˇejak´eho bufferu v pamˇeti, se kter´ ym se pot´e pracuje.Pod´ıvejme se na n´asleduj´ıc´ı pˇr´ıklad.
4
Dejme tomu, ˇze v takov´emto textu hled´ame v´ yskyt slova kapka. Dva ˇr´adky v obr´azkupˇredstavuj´ı dva kusy textu tak, jak jsou naˇcteny do pamˇeti (bufferu). Naivn´ı algoritmusproch´az´ı prvn´ım bufferem a na konci s podezˇren´ım, ˇze se nach´az´ı uprostˇred vzorku naˇcte nov´ ykus textu a tento zahod´ı. Ovˇsem hned u prvn´ıho znaku zjist´ı neshodu a vzhledem ke sv´e funkci munezbude nic jin´eho neˇz se v textu vr´atit. To ale pˇredstavuje dalˇs´ı pˇr´ıstup na disk, neboˇt se mus´ınaˇc´ıst pˇredchoz´ı kus textu. Princip algoritmu KMP zajist´ı, ˇze se nic takov´eho nestane.
Tento obr´azek je pˇr´ıkladem v´ ypoˇctu KMP algoritmu. Porovn´av´an´ı vzorku s textem zaˇc´ın´ a jako obvykleu prvn´ıho znaku zleva (vzorek je zarovn´an s textem). Algoritmus postupuje dokud nenaraz´ı naneshodu na ˇctvrt´e pozici mezi znaky b a g (obr´azek (a)).Z pˇredchoz´ıch znak˚ u okamˇzitˇe v´ıme, ˇze posun vzorku o jeden nebo dva znaky nem´a v´ yznam. Posun o tˇri znaky ale m˚ uˇze splnit u ´ˇcel. T´ım se vzorek zarovn´a s textem nad znakem, kde nastala neshoda.Odtud d´ale m˚ uˇze pokraˇcovat porovn´av´an´ı. Jak vidno na t´eto pozici se hned prvn´ı p´ısmeno vzorkuneshoduje se znakem v textu (obr´azek (b)), vzorek se pot´e posune o jedno m´ısto doprava.Velikost takov´eho posunu (o tˇri v prvn´ım nebo o jeden znak v dalˇs´ıch pˇr´ıpadech) z´avis´ı pouzena charakteru a formˇe kaˇzd´eho vzorku. Posun je nez´avisl´ y na prohled´avan´em textu. Jeho velikosturˇcuje tzv. prefixov´ a funkce. D´ıky prefixov´e funkci si pˇred spuˇstˇen´ım vlastn´ıho vyhled´avac´ıho algoritmu pˇredpoˇctu hodnotyposun˚ u pro jednotliv´e pozice ve vzorku do nˇejak´e tabulky. Mnoho efektivn´ıch vyhled´avac´ıch algoritm˚ u pouˇz´ıv´a podobn´e pˇredpoˇc´ıtan´e tabulky, kter´e se pozdˇeji v pr˚ ubˇehu vyhled´av´an´ı pouˇz´ıvaj´ı.Tedy jak je patrn´e algoritmus KMP bude m´ıt dvˇe f´aze. V prvn´ı f´azi si z dan´eho vzorku vypoˇc´ıt´amepotˇrebn´e hodnoty posun˚ u. Druh´a f´aze bude uskuteˇcn ˇovat vlastn´ı vyhled´av´an´ı.
5
Nejdˇr´ıve se tedy vˇenujme prvn´ı f´azi a prefixov´e funkci. Tato funkce vyjadˇruje chov´an´ı vzorkuˇ vzhledem k posun˚ um k sobˇe sam´emu. Uvedme si jeˇstˇe jeden pˇr´ıklad.
Na obr´azku (a) vid´ıme, ˇze pˇri takov´emto zarovn´an´ı (s posunem s), se prvn´ıch pˇetp´ısmen vzorku shoduje s pˇeti p´ısmeny v textu ( q=5), pˇriˇcemˇz na znaku ˇsest´em doˇslok neshodˇe. Z informace, ˇze pˇet p´ısmen se shodovalo, m˚ uˇzeme okamˇzitˇe vyvodit, kter´e to byly, neboˇt je to prvn´ıch pˇet p´ısmen ve vzorku, a tak´e m˚ uˇzeme zjistit pˇr´ısluˇsn´ y posun. Je moˇzn´e urˇcitposuny, ˇ o kter´ ych jiˇz ted mohu prohl´asit, ˇze jsou neplatn´e, a t´ım je v budoucnu pˇreskoˇcit. Zdeje na prvn´ı pohled jasn´e, ˇze posun o jedno pol´ıˇcko doprava (tedy posun s+1) jeneplatn´ y, neboˇt prvn´ı p´ısmeno ve vzorku (a) by bylo zarovn´ano k p´ısmenu v textu,o kter´em jiˇz m´ame informaci, ˇze se shodovalo s druh´ ym p´ısmenem ve vzorku (b).Posun s+2 na obr´azku (b) naopak d´av´a jistou nadˇeji, ˇze by vzorek mohl b´ yt nalezenna tomto m´ıstˇe, neboˇt tˇri znaky se shoduj´ı. K navrˇzen´ı k´odu, kter´ y vypoˇc´ıt´a dan´e hodnoty je tedy tˇreba vyˇreˇsit n´asleduj´ıc´ı probl´em. Nechˇtm´ame d´any znaky P[1..q], o kter´ ych v´ıme, ˇze se shoduj´ı s tˇemito znaky v textu T[s+1..s+q] (v naˇsem pˇr´ıkladu je to slovo ababa, na obr´azku vybarven´a pol´ıˇcka). Jak´ y je nejmenˇs´ı posun s’>s takov´ y, aby platilo P[1..k]=T[s’+1..s’+k], pˇriˇcemˇz s’+k=s+q. Slovy ˇreˇceno to znamen´a pˇresnˇeto, o co se snaˇz´ıme. Jak moc m˚ uˇzeme vzorek posunout doprava tak, aby se pˇredpona vzorku kratˇs´ı neˇz poˇcet znak˚ u (ababa), kter´e se pˇredt´ım shodovaly (ababa, tedy 5), shodovalas pˇr´ıponou slova v textu (ababa), kter´e bylo stˇredem shody (ababa). Pokud takov´apˇredpona nen´ı ( k=0) posuneme vzorek o poˇcet znak˚ u, kter´e se shodovaly ( q=5). Tedy posun s’ je nejmenˇs´ı takov´ y, ˇze je vˇetˇs´ı neˇz s a nen´ı nezbytnˇeneplatn´ y. Jak bylo ˇreˇceno v nejlepˇs´ım pˇr´ıpadˇe je nov´ y posun s’ roven s+q. V kaˇzd´em pˇr´ıpadˇe jiˇz nemus´ıme porovn´avat prvn´ıch k znak˚ u vzorku,neboˇt jejich shodu v textem m´ame zaruˇcenou. Tyto informace se daj´ı spoˇc´ıtat porovn´av´an´ım vzorku se sebou sam´ ym, jak je hrubˇe naznaˇcenona obr´azku (c). V´ıme, ˇze T[s’+1..s’+k] (ababa) je ˇc´ast zn´am´ehotextu, a tedy to mus´ı b´ yt
6
pˇr´ıpona jist´e ˇc´asti P, kter´a tak´e byla prozkoum´ana.Je to pˇresnˇe pˇr´ıpona Pq . Nyn´ı m˚ uˇzeme pˇresnˇe formulovat poˇzadavek na posun s’ a to pro kaˇzdou pozici ve vzorku. Nechˇt m´am vzorek P[1..m], potom prefixov´a funkce (ud´av´a posuny s’)vypad´a n´asledovnˇe: $\pi$ : \{1,...,m\} -$>$ \{0,...,m-1\}, takov´ a ˇ ze $\pi$[q]= max\{k: k$<$q and P$_k$ je pˇ r´ ıponou P$_q$\}. Pro prefixovou funkci d´ale plat´ı, ˇze pro kaˇzd´e q z {1,...,m} je π[ q]< q. Pozn. π[q] tedy pˇredstavuje d´elku nejdelˇs´ı pˇredpony P, kter´ a je pˇr´ıponou Pq . Nyn´ı se pod´ıvejme, jak bude algoritmus KMP fungovat jako celek. Tedy prvn´ı f´az´ı je v´ ypoˇcet prefixov´e funkce, kter´ y jsme si v principu popsali. N´asleduje f´aze druh´a, vyhled´av´an´ı.Princip je velice jednoduch´ y. Na zaˇc´atku zarovn´am vzorek v˚ uˇci textu a zaˇcnu porovn´avat. Pokudnaraz´ım na neshodu, pod´ıv´am se do tabulky prefixov´e funkce s indexem, kter´ y odpov´ıd´a pozici vevzorku, kde doˇslo k neshodˇe. S tabulky zjist´ım ˇc´ıslo, kter´e ud´av´ a znak vzorku (ˇc´ıslo urˇcujejeho pozici ve vzorku) kter´ y se, kdyˇz pˇr´ısluˇsnˇe zarovn´am vzorek k textu, bude nach´azet pˇresnˇenad znakem v textu, kter´ y byl pˇr´ıˇcinou neshody (vzorek se tedy posune doprava). Vzorek budu t´ımtozp˚ usobem posouvat doprava dokud nenaraz´ım na jeho zaˇc´atek nebo nebudu moci pokraˇcovat od dan´epozice dalˇs´ım porovn´av´an´ım. Takto pokraˇcuji dokud nenaraz´ım na konec textu. Pokud vzorek v textu najdu, ozn´am´ım to a pokraˇcuji d´ale (d´a se totiˇz uvaˇzovat, ˇze u posledn´ıho znaku ve vzorku doˇslo k neshodˇe). Nyn´ı si jiˇz m˚ uˇzeme uv´est z´apis algoritmu v pseudok´odu (na vstupu je text T a vzorek P). (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
n = length(T) m = length(P) $\pi$ = Prefix\_func(P) q = 0 for i = 1 to n while (q $>$ 0 \&\& P[q+1] != T[i]) q = $\pi$[q] if P[q+1] == T[i] then q = q+1 if q = m then print("Vzorek se nach´ az´ ı na pozici", i-m+1) q = $\pi$[q]
Prefix\_func(P) (1) m = length(P) (2) $\pi$[1] = 0 (3) k = 0 (4) for q = 2 to m (5) while (k $>$ 0 \&\& P[k+1] != P[q]) k = $\pi$[k] (6) if P[k+1] == P[q] then k = k+1 (7) $\pi$[q] = k (8) return $\pi$ Nyn´ı si urˇc´ıme ˇcasovou sloˇzitost algoritmu. Nejprve v´ ypoˇcet prefixov´e funkce. Z´akladem je,ˇze vnitˇrn´ı while cyklus se provede nejv´ yˇse tolikr´at jako cyklus vnˇejˇs´ı. Plat´ı totiˇz, ˇze kaˇzd´ ympr˚ uchodem vnitˇrn´ım cyklem se promˇenn´a k sn´ıˇz´ı, neboˇtπ[ k]< k. Souˇcasnˇe se promˇenn´ a 7
k m˚ uˇze zv´ yˇsit nejv´ yˇsejednou v kaˇzd´em kroku vnˇejˇs´ıho cyklu (d´ıky ˇr´adce (6)). Z toho evidentnˇe plyne, ˇze poˇcet pr˚ ubˇeh˚ uvnitˇrn´ım cyklem je menˇs´ı roven poˇctu krok˚ u vnˇejˇs´ıho cyklu. Odtud jiˇz plyne, ˇze ˇcasov´a sloˇzitostv´ ypoˇctu prefixov´e funkce je O(m). ˇ Obdobnou u ´vahou dojdeme k tomu, ˇze ˇcasov´a sloˇzitost vyhled´avac´ı f´aze je O(n). Casov´ a sloˇzitost cel´eho algoritmu je tedy O(m+n), coˇz je v´ yraznˇe lepˇs´ı neˇz u naivn´ıho algoritmu. Vu ´vodu cel´eho refer´atu bylo ˇreˇceno, ˇze KMP algoritmus do jist´e m´ıry souvis´ı s koneˇcn´ ymi automaty. Jak? Je to velice jednoduch´e. Pˇredpokl´adejme, ˇze m´ame vzorek P d´elky m. Definujeme si tedy koneˇcn´ y automat, kter´ y bude m´ıt m+1 stav˚ u. Pˇrechody mezi jednotliv´ ymi stavy budou postupnˇe urˇcen´e jednotliv´ ymi p´ısmeny vzorku. Tedy napˇr.pˇrechod mezi nult´ ym a prvn´ım stavem bude podle p´ısmena p1 , pˇrechod meziprvn´ım a druh´ ym stavem podle p2 atd. Zbyl´e pˇrechody (tedy jak´esi chybov´e)bude urˇcovat pr´avˇe prefixov´a funkce. Vstupn´ım stavem bude stav 0 a v´ ystupn´ım stav m.Samotn´e vyhled´av´an´ı bude realizov´ano jako pr´ace takov´eho automatu se vstupem, kter´ y odpov´ıd´azadan´amu textu. Je zde pouze rozd´ıl v tom, ˇze pokud se pomoc´ı prefixov´e funkce vr´at´ım do nˇekter´eho pˇredeˇsl´eho stavu, okamˇzitˇe zkus´ım pˇres to sam´e p´ısmeno (kter´e vlastnˇe zp˚ usobilo neshodu) pˇrej´ıt do n´asleduj´ıc´ıho stavu, jinak se vrac´ım d´ale. ˇ Uvedme si pˇr´ıklad.
Na obr´azku je koneˇcn´ y automat pro vzorek perpetrate. Nyn´ı si uk´aˇzeme, jak budevypadat v´ ypoˇcet automatu pro dvˇe r˚ uzn´a slova. V´ ypoˇcet je zn´azornˇen jako posloupnost stav˚ u, mezikter´ ymi jsou p´ısmena, pˇres kter´a se mezi stavy pˇrech´az´ı. (a) budeme prohled´avat text perperpetrate: 0p 1e 2r 3p 4e 5r 2r 3p 4e 5t 6r 7a 8t 9e 10 (b) nyn´ı to bude text perpespetrate: 0p 1e 2r 3p 4e 5s 2s 0p 1e 2r 3p 4e 5t 6r 7a 8t 9e 10 >>>Obsah
3. Boyer-Moore˚ uv algoritmus (BM) V t´eto kapitole si pˇredvedeme dalˇs´ı chytr´ y a efektivn´ı algoritmus jehoˇz autory jsou S. Boyer aJ. Strother Moore. Jak bylo ˇreˇceno v u ´vodu, tento algoritmus se pˇr´ıliˇs z´asadnˇe neliˇs´ı od naivn´ıho algoritmu, kter´ y jsme si uk´azali. Je zde pouze nˇekolik odliˇsnost´ı. Abychom si jeuk´azali, pˇredvedeme si ihned, jak Boyer-Moore˚ uv algoritmus vypad´a. Na vstupu je text T, vzorek P a abeceda Σ. (1) (2) (3) (4) (5)
n = length(T) m = length(P) $\lambda$ = Last\_Occur\_func(P,m,$\Sigma$) $\gamma$ = Good\_suff\_func(P,m) s = 0 8
(6) (7) (8) (9) (10) (11) (12)
while (s $<$= n-m) j = m while (j $>$ 0 \&\& P[j] == T[s+j]) j = j-1 if j == 0 then print("Vzorek se nach´ az´ ı na pozici", s+1) s = s+$\gamma$[0] else s = s+max($\gamma$[j], j-$\lambda$[T[s+j]])
V ˇcem se tedy tento algoritmus podob´a a v ˇcem se liˇs´ı od naivn´ıho algoritmu? Podobnost je jakve struktuˇre (coˇz zas tak podstatn´e nen´ı) tak ve skuteˇcnosti, ˇze se vzorek opˇet porovn´av´as dan´ ym textem a v pˇr´ıpadˇe neshody se vzorek posune doprava. Odliˇsnosti jsou v tom, ˇzevzorek se s textem porovn´av´a zprava doleva, tedy odzadu (u naivn´ıho algoritmu se porovn´av´an´ıprov´ad´ı zleva doprava). Pokud naraz´ım na zaˇc´atek vzorku, je jasn´e ˇze jsem v textu naˇsel jeho v´ yskyt. Zde je dalˇs´ı rozd´ıl, neboˇt pˇri takov´em n´alezu neposunu vzorek o jedno m´ısto doprava,ale o nˇejakou hodnotu γ[0]. Pokud naraz´ım na neshodu opˇet posunu vzorek, ale posun nemus´ım´ıt nutnˇe velikost jedna jako u naivn´ıho algoritmu. Ve skuteˇcnosti je tento posun mnohdy mnohemvˇetˇs´ı. Dalˇs´ı odliˇsnost´ı je, ˇze v pˇr´ıpadˇe naivn´ıho algoritmu (a vlastnˇe i v pˇr´ıpadˇe Knuth-Morris-Prattova algoritmu) se zpracoval kaˇzd´ y znak prohled´avan´eho textu aspoˇ n jednou (u naivn´ıho algoritmu i mnohokr´at). U Boyer-Mooreova algoritmu se d´ıky tomu, ˇze vzorek proch´az´ımod konce, a d´ıky tomu, ˇze vzorek v pˇr´ıpadˇe neshody posunu mnohdy o v´ıce neˇz jedno p´ısmeno doprava, na nˇekter´e znaky v prohled´avan´em textu v˚ ubec nedostane (pˇreskoˇc´ı se). Aby se tohoto u ´spˇechu dos´ahlo, pouˇz´ıv´a algoritmus dvˇe heuristiky (v k´odu jsou reprezentov´anyzat´ım z´ahadn´ ymi symboly γ a λ). Jelikoˇz jde o heuristiky d´a se oˇcek´avat, ˇzese ˇcasov´ a sloˇzitost v nejhorˇs´ım pˇr´ıpadˇe oproti naivn´ımu algoritmu pˇr´ıliˇs nezlepˇs´ı. Naˇstˇest´ıjsou tyto heuristiky tak efektivn´ı a u ´spˇeˇsn´e, ˇze v bˇeˇzn´e praxi dosahuj´ı velmi dobr´ ych v´ ysledk˚ u.Jak bylo ˇreˇceno v´ yˇse, spousta znak˚ u v textu se d´ıky tˇemto heuristik´am m˚ uˇze jednoduˇse pˇreskoˇcitaniˇz by byly nˇejak´ ym zp˚ usobem zpracov´any. Na n´asleduj´ıc´ım obr´azku si uk´aˇzeme, jak´a ja z´akladn´ımyˇslenka obou heuristik. Jen pro zaj´ımavost v angliˇctinˇe se naz´ yvaj´ı ”bad-character heuristic”(tedy nˇeco jako heuristika ˇspatn´eho znaku. Z toho se d´a odvodit, ˇze heuristika bude nˇejak´ ymzp˚ usobem souviset se znakem, kter´ y v textu zp˚ usobil neshodu.) a ”good-suffix heuristic” (tomu v ˇceˇstinˇe odpov´ıd´a asi heuristika dobr´e pˇr´ıpony. Opˇet je zjevn´e, ˇze bude souviset s pˇr´ıponami vzorku).
9
Na obr´azku (a) vid´ıme, ˇze hled´ame vzorek reminiscence v textu T, z kter´eho vid´ıme pouze ˇc´ast. Dan´ y posun s je neplatn´ y, neboˇt na tˇret´ım znakuod konce doˇslo k neshodˇe ˇ e je vyznaˇcena tzv.dobr´a pˇr´ıpona ce. Je (pˇr´ıpom´ın´am, ˇze se vzorek proch´az´ı odzadu). Sedˇ to ˇc´ast vzorku odzadu, kter´a se shoduje s jistou ˇc´ast´ıtextu, vzhledem ke kter´emu je vzorek zarovn´an (jak uvid´ıme pozdˇeji tato ˇc´ast se d´a velmi jednoduˇse urˇcit a z n´ı se d´a spoˇc´ıtat pˇr´ısluˇsn´ y posun). Znak i, kter´ y zp˚ usobilneshodu (ve vzorku se na stejn´em m´ıstˇe vyskytuje p´ısmeno n) je jiˇz dˇr´ıveproklamovan´ y tzv. ˇspatn´ y znak. Na obr´azku (b) je naˇcrtnuto, jak si s neshodou porad´ı ”bad-character heuristic”. Ta provedeposun vzorku o tolik pozic doprava, aby ˇspatn´ y znak v textu byl zarovn´an k nejpravˇejˇs´ımu v´ yskytustejn´eho znaku ve vzorku. Zde je ˇspatn´ y znak i, a jelikoˇz se ivyskytuje ve vzorku na sedm´e pozici od konce, mus´ım vzorek posunout o ˇctyˇri pozice doprava, aby se dos´ahlo poˇzadovan´eho v´ ysledku. U t´eto heuristiky vˇsak existuj´ı dvˇe v´ yjimky. Pokud seˇspatn´ y znak ve vzorku v˚ ubec nevyskytuje, vzorek se posune o takov´ y poˇcet m´ıst, aby prvn´ı p´ısmenovzorku bylo zarovn´ano k p´ısmenu, kter´e n´asleduje pˇr´ımo po znaku, kter´ y zp˚ usobil neshodu.V podstatˇe jde o nejlepˇs´ı moˇzn´ y pˇr´ıpad a je logick´e, ˇze pokud je v textu znak, kter´ y se v dan´emvzorku nenach´az´ı nemus´ım se tou ˇc´ast´ı textu zab´ yvat. Druhou v´ yjimkou je, pokud je nejpravˇejˇs´ıv´ yskyt ˇspatn´eho znaku napravo od aktu´aln´ı pozice, kde byla odhalena neshoda (vzorek by se tedy posouval doleva). V tomto pˇr´ıpadˇe neposkytuje heuristika ˇz´adnou moˇznost. Na obr´azku (c) je zobrazeno chov´an´ı ”good-suffix” heuristiky v pˇr´ıpadˇe, ˇze se naraz´ı na neshodu.Tato heuristika provede posun vzorku doprava o nejmenˇs´ı poˇcet znak˚ u, kter´ y zaruˇc´ı,
10
ˇze znakyve vzorku, kter´e se po posunu budou nach´azet pod dobrou pˇr´ıponou bude stejn´e jako znaky v t´etopˇr´ıponˇe, tedy ce. V naˇsem pˇr´ıkladu je to posun o tˇri pozice doprava. Kdyˇz Boyer-Moore˚ uv algoritmus naraz´ı na neshodu, dostane v lepˇs´ım pˇr´ıpadˇe dvˇe doporuˇcen´ı oddvou heuristik, o kolik je znak˚ u je moˇzno vzorek bezpeˇcnˇe posunout (v lepˇs´ım pˇr´ıpadˇe, neboˇtheuristika ”bad-character” nˇekdy doporuˇcen´ı neposkytne). Algoritmus si tedy logicky vyberevˇetˇs´ı posun (v naˇsem pˇr´ıkladˇe posun vzorku o ˇctyˇri pozice doprava). Tuto skuteˇcnost (m´ınˇeno vyb´ır´an´ı a v˚ ubec uˇzit´ı heuristik) je v pseudok´odu reflektov´ano na ˇr´adce(12) v pˇr´ıpadˇe, ˇze byl nalezen v´ yskyt vzorku, nebo na ˇr´adce (13) v pˇr´ıpadˇe, ˇze doˇslo k neshodˇe. Zde se vybere vˇetˇs´ı ˇc´ıslo z j-λ[T[s+j]] (poskytnuto heuristikou ”bad-character”) a γ[j] (poskytnuto ”good-suffix” heuristikou), o kter´e sezv´ yˇs´ı posun s. Nyn´ı se pod´ıv´ame, jak jednotliv´e heuristiky pˇresnˇe funguj´ı a jak se daj´ı spoˇc´ıtat posuny, kter´eposkytuj´ı. Uˇz nyn´ı je zˇrejm´e, ˇze posuny z´avis´ı pouze na vzorku, pˇr´ıpadnˇe na abecedˇe Σ.Na prohled´avan´em textu opˇet pˇr´ıliˇs nez´aleˇz´ı. Heuristika ˇ spatn´ eho znaku Uˇz bylo poznamen´ano, ˇze u t´eto heuristiky se vyuˇz´ıv´a znalost nejpravˇejˇs´ıho v´ yskytu znaku ve vzorku, kter´ y zp˚ usobil neshodu v textu ( T[s+j]). Z toho se pot´e odvod´ı poˇcetznak˚ u, o kter´ y se vzorek m˚ uˇze posunout doprava. Je zˇrejm´e, ˇze v nejlepˇs´ım pˇr´ıpadˇe, kdy dojdek neshodˇe hned na prvn´ım porovn´avan´em znaku (tedy posledn´ım znaku vzorku) a tento ˇspatn´ y znakse ve vzorku nevyskytuje, je moˇzn´e posunout vzorek doprava o celou jeho d´elku. Pokud k tomudoch´az´ı pˇri prohled´av´an´ı opakovanˇe, porovn´a se ve skuteˇcnosti pouh´ y zlomek celkov´eho poˇctup´ısmen, kter´e prohled´avan´ y text obsahuje. Heuristika ”bad-character” tedy zajiˇsˇtuje velmiv´ yrazn´e urychlen´ı vyhled´avac´ıho procesu a to i d´ıky faktu, ˇze porovn´av´an´ı vzorku s textemse prov´ad´ı zprava doleva. Jak tedy heuristika ve skuteˇcnosti pracuje? Nebude ˇskodit, kdyˇz k odpovˇedi pouˇzijeme trochuform´alnˇejˇs´ıho z´apisu. Nechˇt pˇri porovn´av´an´ı doˇslo k neshodˇe. To znamen´a, ˇze P[j]!=T[s+j] pro nˇejak´e j, pro kter´e ˇ nejvˇetˇs´ıˇc´ıslo takov´e, ˇze 1<=k<=m a z´aroveˇ plat´ı 1<=j<=m. Potom k bud n P[k]==T[s+j], ˇ k=0. Jedn´a se tedy o nejpravˇejˇs´ıv´ pokud takov´e k existuje. Pokud neexistuje, bud yskyt ˇspatn´eho znaku ve vzorku. Vzorek tedy m˚ uˇzeme bezpeˇcnˇe posunout o j-k znak˚ u.V d˚ ukazu tohoto tvrzen´ı se rozliˇsuj´ı tˇri moˇzn´e pˇr´ıpady podle velikosti k, kter´e jsou zn´azornˇeny na n´asleduj´ıc´ım obr´azku.
11
Na obr´azku (a) je ilustrov´an prvn´ı pˇr´ıpad, kdy se ˇspatn´ y znak T[s+j] (v naˇsempˇr´ıkladˇe je to p´ısmeno h) ve vzorku na jin´em m´ıstˇe v˚ ubec nevyskytuje. Vzorekm˚ uˇzeme tedy bezpeˇcnˇe
12
posunout o j m´ıst aniˇz bychom vynechali moˇznost v´ yskytuvzorku v textu (na obr´azku o 11 pozic). Vzorek se zarovn´a pod p´ısmeno v textu, kter´e n´asledujepˇresnˇe za znakem, kter´ y zp˚ usobil neshodu. Tvrzen´ı v tomto pˇr´ıpadˇe plat´ı, neboˇt k=0a vzorek posuneme o j pozic, coˇz je pˇresnˇe j-k m´ıst. Na dalˇs´ım obr´azku (b) je zobrazen dalˇs´ı pˇr´ıpad, kdy k<j. Nejpravˇejˇs´ı v´ yskytˇspatn´eho znaku ve vzorku je vlevo od m´ısta j, kde doˇslo k neshodˇe. Tud´ıˇz j-k>0 a vzorek mohu o tento poˇcet m´ıst bezpeˇcnˇe pˇrem´ıstit doprava. V´ yskytˇspatn´eho znaku ve vzorku se potom zarovn´ a ke ˇspatn´emu znaku v textu. Posun je bezpeˇcn´ y, protoˇze k je index nejbliˇzˇs´ıho znaku, kter´ y se shoduje se ˇspatn´ ym, vzhledem k posunu. To znamen´a, ˇze vˇsechny posuny o velikost menˇs´ı neˇz j-k jsou neplatn´e a posunpr´avˇe o j-k je v tuto chv´ıli platn´ y (je moˇzn´e, ˇze se vylouˇc´ı hned v dalˇs´ım kroku).Na obr´azku m´ame situaci, kdy k=6 a j=10, ˇspatn´ y znak je i. Vzorek tedy posunu o ˇctyˇri pozice a i budou zarovnan´a podsebou. Posledn´ı obr´azek (c) zn´azorˇ nuje i posledn´ı moˇznost postaven´ı ˇspatn´eho znaku ve vzorku, kdy k>j. Potom by platilo, ˇze j-k<0, coˇz by znamenalo posunut´ıvzorku smˇerem doleva (n´avrat zp´atky). Tato moˇznost se v pr˚ ubˇehu algoritmu automaticky podchyt´ı,neboˇt druh´a heuristika vˇzdy zaruˇc´ı posun alespoˇ n o jedno m´ısto a jelikoˇz algoritmus vyb´ır´amaximum z obou ˇc´ısel, vˇzdy se v takov´emto pˇr´ıpadˇe vybere ˇc´ıslo poskytnut´e heuristikou ”good-suffix”. V naˇsem pˇr´ıkladu je ˇspatn´ y znak e, j=10 a k=12. Nyn´ı si uvedeme jednoduch´ y pseudok´od funkce, kter´a heuristiku ”bad-character” realizuje. Funkcedostane na vstup vzorek P, jeho d´elku m a abecedu Σ, protoˇzeposun se mus´ı spoˇc´ıtat pro kaˇzd´ y znak, kter´ y se m˚ uˇze vyskytnout jako ˇspatn´ y. Last\_Occur\_func(P,m,$\Sigma$) (1) for kaˇ zd´ y znak a z abecedy $\Sigma$ (2) $\lambda$[a]=0 (3) for j=1 to m (4) $\lambda$[P[j]]=j (5) return $\lambda$ Funkce vrac´ı pole λ, kde λ[a] pˇredstavuje pozici nejpravˇejˇs´ıho v´ yskytu znaku a ve vzorku a to pro vˇsechny znaky z abecedy Σ. V pˇr´ıpadˇe,ˇze se znak ve vzorku nevyskytuje je hodnota rovna nule. λ se naz´ yv´a last-occurence function ˇcili nˇeco jako funkce posledn´ıho v´ yskytu. ˇ adka (2) se provede tolikr´at, kolik m´a abeceda Urˇcen´ı ˇcasov´e sloˇzitosti je jednoduch´e. R´ ˇ adka (4) se provede pˇresnˇe m-kr´at. Casov´ ˇ Σznak˚ u, tedy —Σ—-kr´at. R´ a sloˇzitostje tud´ıˇz O(—Σ—+m). Heuristika dobr´ e pˇ r´ıpony V tomto odstavci si uk´aˇzeme, jak vypoˇc´ıtat posuny doporuˇcovan´e druhou heuristikou, heuristikou”good-suffix”. Pro tento u ´ˇcel si definujme relaci Q~R pro dva textov´e ˇretˇezce Q ˇ a R, pro kter´e plat´ı, ˇze bud Q je pˇr´ıponou R nebo R je pˇr´ıponou Q. Tato relace neznamen´ a nic jin´ehoneˇz, ˇze pokud oba ˇretˇezce zarovn´ame pod sebe podle prav´eho okraje, budou se ve znac´ıch podsebou shodovat. Z´aroveˇ n plat´ı, ˇze Q~R pr´avˇe tehdy, kdyˇz R~Q. Dalˇs´ı vztah: Jestliˇze Q je pˇr´ıponou R a z´aroveˇ n S je pˇr´ıponou R, potom Q~S. Slovy ˇreˇceno to znamen´a, ˇze pokud je Qpˇr´ıponou R a nˇejak´e S je tak´e pˇr´ıponou R, tak je jasn´e,ˇze ˇretˇezce Q a S maj´ı urˇcit´ y ˇ Q je pˇr´ıponou S nebo S je pˇr´ıponou Q.To je ale Q~S podle poˇcet znak˚ u stejn´ ych. Tedy bud definice ˜. Nechˇt pˇri porovn´av´an´ı doˇslo k neshodˇe na j-t´em m´ıstˇe vzorku (tedy P[j]!=T[s+j]), pro nˇejak´e j<m. Potom heuristika ”good-suffix” ˇr´ık´a,ˇze vzorek mohu bezpeˇcnˇe posunout o 13
vzd´alenost $\lambda$[j]=m-max\{k: 0$<$=k$<$m \& P[j+1..m]\textasciitilde{}P$_k$\} Tedy λ[j] je nejmenˇs´ı vzd´alenost, o kterou m˚ uˇzeme vzorek posunout, aniˇzbychom zp˚ usobili nˇejakou neshodu dobr´e pˇr´ıpony T[s+j+1..s+m] v˚ uˇci odpov´ıdaj´ıc´ımznak˚ um novˇe posunut´eho vzorku. Tuto situaci si m˚ uˇzeme uk´azat na obr´azku (b) s pˇredchoz´ı kapitoly. K neshodˇe doˇslo na tˇret´ım znaku vzorku od konce, tedy j=3. Dobr´a pˇr´ıponaje tedy slovo ce, posledn´ı dvˇe p´ısmena vzorku reminiscence.Z definice λ hled´ame nejvˇetˇs´ı k, kter´e splˇ nuje, ˇze P[j+1..m]~Pk . V naˇsem pˇr´ıpadˇe je k=9, neboˇt P[j+1..m] je slovo ce (dobr´a pˇr´ıpona) a nejdelˇs´ı pˇredpona vzorku P konˇc´ıc´ı ce je slovo reminisce, jehoˇz d´elka jedevˇet. Vzorek tedy m˚ uˇzeme posunout o m-k=12-9=3 pozice doprava. Jeˇstˇe poznamenejme, ˇze funkce λ je dobˇre definov´ana pro vˇsechna j, neboˇt P[j+1..m]~P0 pro vˇsechna j (pr´azdn´ y ˇretˇezec je v relacise vˇs´ım). λ se naz´ yv´a good-suffix function, v pˇrekladu funkce dobr´e pˇr´ıpony. Jelikoˇz je naˇse definice t´eto funkce pro u ´ˇcely v´ ypoˇctu na poˇc´ıtaˇci ponˇekud nevhodn´a, provedemenˇekolik relativnˇe jednoduch´ ych u ´prav, abychom dostali ekvivalentn´ı definici, ale ve tvaru,v kter´em p˚ ujde pˇrepsat do naˇseho pseudok´odu. Nejprve si uk´aˇzeme, ˇze plat´ı vztah λ[j]<=m-π[m] pro vˇsechna j, kde π je prefixov´a funkce, kterou jsme pouˇzili u KMP algoritmu. Poloˇzme w=π[m]. Z definice prefixov´e funkce m´ame, ˇze mus´ı platit, ˇze Pw je pˇr´ıponou vzorku P. Protoˇze P[j+1..m] je tak´e pˇr´ıponou P, dostaneme ze vztahu uveden´eho v´ yˇse, ˇze nutnˇe P[j+1..m]~Pw . Podle definice λ plat´ı, ˇze λ[j]<=m-w (neboˇt m´am w, kter´e splˇ nuje poˇzadavky, ale nemus´ı to b´ yt maxim´aln´ı takov´e ˇc´ıslo, proto je moˇzn´e, ˇze λ[j] bude menˇs´ı neˇz m-w). Jelikoˇz m´ame w=π[m], plyne odtud rovnou vztah λ[j]<=m-π[m] pro vˇsechna j, coˇz jsme chtˇeli dok´azat.D´ıky tomu m˚ uˇzeme naˇsi definici funkce λ pˇrepsat do n´asleduj´ıc´ı podoby. $\lambda$[j]=m-max\{k: $\pi$[m]$<$=k$<$m \& P[j+1..m]\textasciitilde{}P$_k$\} Tuto definici jsme z pˇredchoz´ıho dostali n´asledovnˇe. (1) $\lambda$[j]=m-max\{k: 0$<$=k$<$m \& ...\} $<$= m-$\pi$[m] (2) $\pi$[m] $<$= max\{k: 0$<$=k$<$m \& ...\} (3) k $>$= $\pi$[m] ´ Uprava mezi (1) a (2) je trivi´aln´ı. Vztah (3) plyne z (2), neboˇt nejvˇetˇs´ı k budevˇzdy vˇetˇs´ı neˇz π[m], proto takhle omezen´e k mohu hledat od zaˇc´atku. ˇ Pokraˇcujme v u ´prav´ach naˇs´ı nov´e definice λ. Z podm´ınky P[j+1..m]~Pk vypl´ yv´a, ˇze bud P[j+1..m] je pˇr´ıponou Pk nebo Pk je pˇr´ıponou P[j+1..m]podle definice ˜. Druh´a moˇznost pˇr´ımo implikuje, ˇze Pk je pˇr´ıponoucel´eho vzorku P ( Pk je pˇr´ıponou P[j+1..m],coˇz je ale pˇr´ıpona P. Je tedy jasn´e, ˇze i Pk je pˇr´ıponou P). Odtud dostaneme vztah, ˇze k<=π[m] z definice π(m´ame, ˇze Pk je pˇr´ıponou P a z´aroveˇ n π[q]=max{k: k
=k, neboˇt π[m] se rovn´a maximu, tedypro ostatn´ı k je jistˇe vˇetˇs´ı.). Z t´eto nerovnosti plyne λ[j]>=m-π[m] a to n´asledovnˇe. k $<$= $\pi$[m] m-$\pi$[m] $<$= m-k pro vˇ sechna k m-$\pi$[m] $<$= m-max\{k: ...\}=$\lambda$[j] m-$\pi$[m] $<$= $\lambda$[j] 14
Definici λ m˚ uˇzeme d´ale upravit.
$\lambda$[j]=m-max(\{$\pi$[m]\} sjednoceno s \{k: $\pi$[m]$<$k$<$m \& P[j+1..m] je pˇ r´ ıpo ˇ bude Odtud plyne v´ yznamn´a skuteˇcnost, λ[j]>0 pro vˇsechna j (z definice plyne, ˇze bud λ[j]=m-π[m] a to je urˇcitˇe kladn´e(v´ıme, ˇze π[m]<m), nebo λ[j]=m-k (k je maximem z druh´emnoˇziny), v tomto pˇr´ıpadˇe je ale λ[j] tak´e kladn´e, neboˇt k<m). To je vˇec, kterou jsme potˇrebovali, protoˇze zaruˇc´ı, ˇze BM algoritmusbude posunovat vzorek st´ale doprava (i v pˇr´ıpadˇe, ˇze prvn´ı heuristika vr´at´ı z´aporn´e ˇc´ıslo). Pokraˇcujme v naˇs´ı snaze zjednoduˇsit definici funkce λ d´ale. Pro dalˇs´ı u ´ˇcely si zavedemeobr´acen´ y vzorek P’ vzorku P a tomu odpov´ıdaj´ıc´ı prefixovou funkci π’. Potom P’[i]=P[m-i+1] pro i=1,...,m a π’[t] jenejvˇetˇs´ı u takov´e, ˇze u=1( l=(m-k)+(m-j). Prvn´ı z´avorka je d´ıky prvn´ı nerovnosti kladn´a, druh´a z´avorka jed´ıky druh´e nerovnosti nez´aporn´a. Cel´e je to tedy vˇetˇs´ı nebo rovno jedn´e.).Jelikoˇz 1<=l<=m je funkce π’ dobˇre definov´ana. Nyn´ı si dok´aˇzeme tvrzen´ı π’[l]=m-j. Jelikoˇz P[j+1..m] je pˇr´ıponou Pk , m´ame tak´e P’m − j je pˇr´ıponou P’l (pouh´e obr´acen´ı a pˇreindexov´an´ı). Odtud dostaneme π’[l]>=m-j (neboˇt m-j vyhovuje definici π’, hodnota vˇsakm˚ uˇze b´ yt d´ıky maximalizaci i vˇetˇs´ı.). Pro spor pˇredpokl´adejme, ˇze p>m-j, kde p=π’[l]. Podle definice π’ m´ame, ˇze P’p je pˇr´ıpona P’l . To se vˇsak d´a napsat tak´e jako P’[1..p]=P’[l-p+1..l].Pˇrepisem vzhledem k p˚ uvodn´ımu ˇ vzorku z´ısk´ame P[m-p+1..m]=P[m-l+1..m-l+p]. Pokud ted pouˇzijeme substituci l=2m-k-j, dostaneme P[m-p+1..m]=P[k-m+j+1..k-m+j+p]. Tedy P[m-p+1..m] je pˇr´ıpona Pk −m+j+p. Protoˇze p>m-j, pak j+1>m-p+1,a tedy P[j+1..m] je pˇr´ıpona P[m-p+1..m]. Celkem m´ame fakt, ˇze P[j+1..m] je pˇr´ıpona Pk − m + j + p (to plyne z tranzitivity”operace suffixov´an´ı” ( A je pˇr´ıpona B a B je pˇr´ıpona C, potom A je pˇr´ıponou C)). Protoˇze p>m-j, m´ame k’>k, kde k’=k-m+j+p. Jelikoˇz k’ splˇ nuje definici π’ a dokonce k’>k, doch´az´ıme ke sporu s t´ım, ˇze k je nejvˇetˇs´ı ˇc´ıslo splˇ nuj´ıc´ı definici π’. Tedy p=π’[l]=m-j a tvrzen´ı je dok´az´ano. D´ıky tvrzen´ı m´ame π’[l]=m-j, z toho plyne j=m-π’[l] a dosazen´ımdo l=(m-k)+(m-j) dostaneme k=m-l+π’[l]. D´ıky tomu m˚ uˇzeme l´epe pˇrepsat definici λ.
$\lambda$[j]=m-max(\{$\pi$[m]\} sjednoceno s \{m-l+$\pi$’[l]: 1$<$=l$<$=m \& j=m-$\pi$’[ =min(\{m-$\pi$[m]\} sjednoceno s \{l-$\pi$’[l]: 1$<$=l$<$=m \& j=m-$\pi$’[l]\}) Tato definice je jiˇz natolik dobˇre formulov´ana, ˇze se d´a pˇr´ımo pˇrepsat do pseudok´odu. Funkcedostane na vstup vzorek P a jeho d´elku m. Good\_suff\_func(P,m) (1) $\pi$=Prefix\_func(P) (2) P’=Obrat(P) (3) $\pi$’=Prefix\_func(P’) (4) for j = 0 to m (5) $\gamma$[j]=m-$\pi$[m] (6) for l = 1 to m (7) j = m-$\pi$’[l] (8) if $\gamma$[j] $>$ l-$\pi$’[l] 15
(9) (10)
then $\gamma$[j] = l-$\pi$’[l]) return $\gamma$
ˇ ˇ Casov´ a sloˇzitost t´eto procedury je O(m). Casov´ a sloˇzitost v nejhorˇs´ım pˇr´ıpadˇe cel´eho BM algoritmu je tedy O((n-m+1)*m+—Σ—) (sloˇzitost obou heuristik dohromady je O(m+—Σ—) a vyhled´avac´ı f´aze je v podstatˇe naivn´ı algoritmus). Ve skuteˇcnosti se v bˇeˇzn´e praxi dosahuje mnohem lepˇs´ıch v´ ysledk˚ u a tento algoritmus je velmi pouˇz´ıvan´ y. Postupem ˇcasu se objevilo nˇekolik u ´prav tohoto algoritmu a dos´ahlo se line´arn´ı sloˇzitosti iv nejhorˇs´ım pˇr´ıpadˇe. >>>Obsah
4. Baeza-Yates-Gonnet˚ uv algoritmus (BYG) Nyn´ı si pˇredvedeme algoritmus, kter´ y se od pˇredchoz´ıch liˇs´ı uˇz sv´ ym pˇr´ıstupem k vyhled´av´an´ıv textu. Byl publikov´an v roce 1992 a autory jsou R. Baeza-Yates a G.H. Gonnet. Narozd´ıl od dvou algoritm˚ u, kter´e jsme si jiˇz objasnili, a kde se vyhled´av´a pomoc´ıporovn´av´an´ı znak˚ u ve vzorku a v textu, algoritmus BYG pˇriˇsel s ideou vyhled´av´an´ı pomoc´ı bitov´ ychmasek. Princip je celkem jednoduch´ y. I v tomto algoritmu se pouˇz´ıv´a pˇredpoˇc´ıtan´a tabulka, nyn´ıje to vˇsak tabulka bitov´ ych vektor˚ u pro kaˇzd´ y znak ze vstupn´ı abecedy Σ. Kaˇzd´a bitov´apozice v dan´em vektoru pro dan´e p´ısmeno odpov´ıd´a pozici tohoto p´ısmena ve vzorku. Z toho plyne,ˇze kaˇzd´ y vektor mus´ı b´ yt tak dlouh´ y jako je dan´ y vzorek. Vektor je posloupnost jedniˇcek, alepokud se znak odpov´ıdaj´ıc´ı tomuto vektoru vyskytuje na k-t´e pozici ve vzorku, jena k-t´e pozici ve vektoru ˇc´ıslo nula. ˇ se pozice vektoru Zde existuje nˇekolik moˇzn´ ych variant, jak se vektory konstruuj´ı. Bud ˇc´ısluj´ıodleva nebo odprava. Nˇekdy jsou vektory nulov´e a v´ yskyt znaku ve vzorku je znaˇcen jedniˇckou.Nejbˇeˇznˇejˇs´ı je vˇsak zp˚ usob, kter´ y jsme si uk´azali a to je ˇc´ıslov´an´ı pozic odprava a v´ yskyt je znaˇcen nulou. Ukaˇzme si na pˇr´ıkladu jak takov´a tabulka vektor˚ u vypad´a pro slovo states za pˇredpokladu klasick´e abecedy Σ ={a,b,...,z}. Znak Pozice ve vzorku 654321 a 111011 b 111111 c 111111 d 111111 e 101111 f 111111 ... ... r 111111 s 011110 t 110101 u 111111 ... ... Napˇr´ıklad p´ısmeno s se ve vzorku vyskytuje na prvn´ı a ˇsest´e posledn´ı pozici, v odpov´ıdaj´ıc´ım vektoru je tud´ıˇz prvn´ı a ˇsest´ y bit nastaven na nulu. Na vˇsechny tyto vektory se m˚ uˇzeme pod´ıvat jako na masky, kde nula je transparentn´ı (”pr˚ uhledn´ a”)a jedniˇcka netransparentn´ı. Tyto masky potom m˚ uˇzeme zarovnat k dan´emu prohled´avan´emu ˇ textu.Uvedme si pˇr´ıklad. Nechˇt m´ame text misstates. Potom kdyˇz k p´ısmen˚ um zarovn´ameodpov´ıdaj´ıc´ı 16
masky dostaneme n´asleduj´ıc´ı obr´azek.
Na obr´azku je kaˇzd´a maska zarovn´ana k odpov´ıdaj´ıc´ımu p´ısmenu. To znamen´a maska pro m je zarovn´ana k p´ısmenu m v textu, maska pro i je zarovn´ana k i atd. Jelikoˇz se v textu ˇ a vzorek states nach´az´ı je na obr´azku seˇrazeno ˇsest transparentn´ıch bunˇek pod sebou.Sed´ ˇc´ara zn´azorˇ nuje paprsek svˇetla, kter´ ym by se daly jednotliv´e buˇ nky prosv´ıtit z jedn´e stranyna druhou. Abychom vidˇeli rozd´ıl mezi t´ım, kdy se vzorek v textu najde a mezi okamˇzikem, kdy dojde k neshodˇe, uk´aˇzeme se dalˇs´ı pˇr´ıklad. Tentokr´at je prohled´avan´ ym textem slov mistakes.
Na obr´azku je vidˇet, ˇze maska pro p´ısmeno k zamezuje prosv´ıcen´ı blokutransparentn´ıch bit˚ u. To znamen´a, ˇze v textu se vzorek na tomto m´ıstˇe nenach´az´ı. Nyn´ı si uk´aˇzeme, jak by mohl vypadat k´od pro hled´an´ı vzorku v textu algoritmem BYG (n´asleduj´ıc´ık´od vyhled´a pouze prvn´ı v´ yskyt, pro hled´an´ı vˇsech v´ yskyt˚ u je potˇreba k´od ˇc´asteˇcnˇe upravit).Nejprve vˇsak nˇekolik pozn´amek. Zm´ınˇen´e prosv´ıcen´ı bunˇek se v programu prov´ad´ı, ˇ ı v promˇenn´e work, ovˇsem digit´alnˇepomoc´ı bitov´ ych operac´ı. Jednotliv´e masky se shromaˇzduj´ jej´ıˇzpoˇc´ateˇcn´ı hodnota je -1 (v dvojkov´em doplˇ nku jsou to sam´e jedniˇcky). S kaˇzd´ ymnov´ ym znakem v textu se tato promˇenn´a posune o jeden bit doleva (vyn´asob´ı se dvˇema), coˇzodpov´ıd´ a odsazov´an´ı masek na obr´azc´ıch. Maska pro nov´ y znak se k promˇenn´e workpˇrid´a pomoc´ı operace OR. V kaˇzd´em cyklu se pot´e tato promˇenn´a testuje na pˇr´ısluˇsn´em bituna nulovost 17
(neboˇt operace OR zachov´av´a nulovost bit˚ u u znak˚ u, kter´e se shoduj´ı se vzorkem).Pokud se nula v bitu vyskytuje je vzorek nalezen, v opaˇcn´em pˇr´ıpadˇe se pokraˇcuje d´ale. Program dost´av´a na vstup text T a vzorek P. Nejprve se mus´ı vytvoˇrittabulka bitov´ ych masek a definovat bit, kter´ y se bude testovat na nulovost (je to vlastnˇe bits indexem d´elky vzorku). (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15)
n = length(T) m = length(P) masks = Comp\_masks(P, $\Sigma$) testbit = 2\textasciicircumm i = 1 found = false while (not found \&\& i $<$ n) while (i $<$ n \&\& T[i] != P[1]) i = i+1 work = -1 while (work != -1 \&\& not found) work = (work shl 1) or masks[T[i]] if (work and testbit = 0) then found = true print("Vzorek byl nalezen na pozici", i+1-m) else i = i+1
Cyklus na ˇr´adce (8) proch´az´ı text do doby neˇz najde poˇc´ateˇcn´ı znak vzorku, odtud zaˇc´ın´ a hledatvzorek podle masek. V cyklu (10)-(15) se prov´ad´ı vlastn´ı ˇcinnost, tedy posouv´an´ı a OR-ov´an´ımasky spolu s testem na pˇr´ıtomnost vzorku. Abychom si l´epe uk´azali, jak algoritmus funguje (podle k´odu, kter´ y jsme se sestavili a ne podlejak´esi pˇredstavy z pˇredchoz´ıch obr´azk˚ u), probereme dalˇs´ı pˇr´ıklad. Budeme hledat vzorek state v textu misstates. Program tedy podle ˇr´adky (8) projdetext aˇz naraz´ı na znak s, coˇz je poˇc´ateˇcn´ı p´ısmeno naˇseho vzorku. Potom sepromˇenn´a work nastav´ı na v´ ychoz´ı hodnotu -1. N´aslednˇe se promˇenn´a posune o jeden bit doleva (nejpravˇejˇs´ı bit bude nula) a pˇrioruje se maska pro p´ısmeno s.Jelikoˇz tato maska obsahuje nulu na nejpravˇejˇs´ım bitu, operace OR tuto hodnotu zachov´a.Abychom vidˇeli, co se bude d´ıt d´al, uvedeme si tabulku. Hodnota Posun bude vyjadˇrovat promˇennou work posunutou o jeden bit doleva, pol´ıˇcko Maska pˇredstavuje masku pro dan´ep´ısmeno a pol´ıˇcko V´ ysledek je v´ ysledkem operace OR na pˇredchoz´ı dvˇe hodnoty. Bit, kter´ y se testuje na nulovost je zv´ yraznˇen. Vstupn´ ı znaky Bitov´ e hodnoty s 1111111111111110 Posun 1111111111111110 Maska 1111111111111110 s 1111111111111100 Posun 1111111111111110 Maska 1111111111111110 t 1111111111111100 Posun 1111111111110101 Maska 1111111111111101 a 1111111111111010 Posun 1111111111111011 Maska 1111111111111011 t 1111111111110110 Posun 1111111111110101 Maska 1111111111110111 e 1111111111101110 Posun 1111111111101111 Maska 1111111111101111 D´ale algoritmus nepokraˇcuje, protoˇze vzorek byl v tomto okamˇziku odhalen otestov´an´ım pˇr´ısluˇsn´ehobitu na nulu. Nyn´ı si uk´aˇzeme obdobnou tabulku pro text, kter´ y vzorek neobsahuje, napˇr.mistakes.
18
V´ ysledek V´ ysledek V´ ysledek V´ ysledek V´ ysledek V´ ysledek
Vstupn´ ı znaky Bitov´ e hodnoty s 1111111111111110 Posun 1111111111111110 Maska 1111111111111110 t 1111111111111100 Posun 1111111111110101 Maska 1111111111111101 a 1111111111111010 Posun 1111111111111011 Maska 1111111111111011 k 1111111111110110 Posun 1111111111111111 Maska 1111111111111111 Program v tuto chv´ıli skonˇc´ı vnitˇrn´ı cyklus, neboˇt work=-1, coˇz znamen´a, ˇzebyla nalezena neshoda. D´ale by program hledal prvn´ı znak vzorku (s) v textu.Nyn´ı si ukaˇzme jednoduch´ y k´od, kter´ y pˇredpoˇc´ıt´a masky pro vˇsechny znaky abecedy Σ.Procedura dostane na vstup vzorek P a abecedu Σ. (1) (2) (3) (4) (5) (6) (7)
for kaˇ zd´ y znak a z abecedy $\Sigma$ masks[a] = -1 j = 1 for i = 1 to m masks[P[i]] = masks[P[i]] and not j j = j shl 1 return masks
Promˇenn´a j slouˇz´ı k vyznaˇcov´an´ı nul v pˇr´ısluˇsn´ ych vektorech. Poˇc´ateˇcn´ı hodnotouje jedniˇcka a s kaˇzd´ ym pr˚ ubˇehem cyklu se hodnota zdvojn´asob´ı (posun o jeden bit doleva).Napˇr´ıklad pokud j=4, coˇz je v bitov´em z´apisu 0000000000000100. T´ım,ˇze operaci AND pouˇzijeme na masku, kterou m´ame, a na dvojkov´ y doplˇ nek j( 1111111111111011), vyznaˇc´ıme nulu na tˇret´ım bitu masky. ˇ Casov´ a sloˇzitost t´eto procedury je O(m), protoˇze cyklus se vykon´a pro kaˇzd´ y znak m-kr´ at ˇ (cykly jsou sice dva, ale sloˇzitost O(2*m) odpov´ıd´a O(m)z definice O). Casov´a sloˇzitost samotn´eho vyhled´av´an´ı je O(n) v nejhorˇs´ım pˇr´ıpadˇe. Celkov´a sloˇzitost je tedy O(n+m). >>>Obsah
5. Quicksearch V roce 1990 publikoval ˇclovˇek jm´enem D.M. Sunday algoritmus Quicksearch, kter´ y se od pˇredchoz´ıchv´ yznamnˇe liˇs´ı ve dvou vˇecech. Je rychlejˇs´ı a mnohem jednoduˇsˇs´ı. Nˇekter´e jeho rysy jsou podobn´ejako u Boyer-Mooreova algoritmu. U BM algoritmu totiˇz v nejlepˇs´ım pˇr´ıpadˇe pˇreskoˇc´ıme tolik znak˚ ukolik je d´elka samotn´eho vzorku. U Quicksearch se, jak uvid´ıme pozdˇeji, nejˇcastˇeji pˇreskakuje m+1 znak˚ u (kde m je d´elka vzorku). Znamen´a to, ˇze ˇcasov´a sloˇzitostv pr˚ umˇern´em pˇr´ıpadˇe je m´enˇe neˇz O(n) a bl´ıˇz´ı se k O(n/(m+1)). To je d˚ uleˇzit´ezvl´aˇsˇt pro delˇs´ı vzorky, kde je urychlen´ı opravdu markantn´ı. U Boyer-Mooreva algoritmu sed´ıky tomu, ˇze vzorek porovn´av´ame odzadu, v textu vrac´ıme, coˇz m˚ uˇze zp˚ usobit ˇ probl´emy s pamˇetov´ ymbufferem, kter´e byly pops´any v u ´vodu Knuth-Morris-Prattova algoritmu. Quicksearch nic takov´ehonedˇel´a, takˇze se jev´ı jako bezprobl´emov´ y. M´a vˇsak jin´e nev´ yhody, kter´e jsou popsan´e v dalˇs´ıkapitole. Myˇslenka tohoto algoritmu je opravdu velice jednoduch´a. Na zaˇc´atku jako obvykle zarovn´ame vzorekk prohled´avan´emu textu. Stejnˇe jako u naivn´ıho algoritmu budeme text a vzorek porovn´avat znakpo znaku. Postup se ale liˇs´ı v pˇr´ıpadˇe, ˇze objev´ıme neshodu mezi jednotliv´ ymi p´ısmeny. V tomtookamˇziku se pod´ıv´ame na znak, kter´ y se nach´az´ı v textu pˇr´ımo za koncem vzorku (testov´ y znak).Pokud se tento znak ve vzorku na ˇz´adn´em m´ıstˇe neobjevuje, ˇz´adn´ y 19
V´ ysledek V´ ysledek V´ ysledek V´ ysledek
posun, kter´ y by um´ıstil jak´ekolip´ısmeno vzorku nad testov´ y znak, nebude platn´ y. S klidn´ ym svˇedom´ım tedy m˚ uˇzeme cel´ y vzorek pˇrem´ıstit aˇz za testov´ y znak. To pˇredstavuje posun o m+1 znak˚ u, kde mje velikost vzorku. Tato vzd´alenost je mnohem lepˇs´ı neˇz v pˇr´ıpadˇe pˇredchoz´ıch algoritm˚ u (vˇcetnˇe BM algoritmu, kde byl posun v tomto pˇr´ıpadˇe pouze m). Pokud se testov´ y znak ve vzorku na nˇejak´em m´ıstˇe nach´az´ı (pˇr´ıpadnˇe na v´ıce m´ıstech), posunemevzorek o nejmenˇs´ı vzd´alenost takovou, ˇze se testov´ y znak bude shodovat se znakem v novˇe posunut´em vzorku, kter´ y je zarovn´an k testov´emu znaku. Vˇetˇsinou to bude pˇredstavovat posuno v´ıce neˇz jeden znak. Dalˇs´ım porovn´an´ım zjist´ıme, jestli byl posun spravn´ y a vzorek se na t´eto pozici jiˇz nach´az´ı. Jinak se posuneme stejn´ ym zp˚ usobem d´ale. Pro lepˇs´ı ilustraci, jaktento algoritmus v textu vyhled´av´a, si uvedeme pˇr´ıklad. V n´asleduj´ıc´ım textu budeme hledt v´ yskytvzorku problems.
Na obr´azku (a) je vyobrazena v´ ychoz´ı situace. Hned prvn´ı znak textu zp˚ usobuje neshodu. Testov´ y znak je p´ısmeno h. Jelikoˇz se takov´e p´ısmeno ve vzorku nevyskytuje, posunemevzorek
20
o jeho d´elku zvˇetˇsenou o jedna (tedy o devˇet znak˚ u). To znamen´a, ˇze se vzorek posuneaˇz za p´ısmeno h. Situace je ilustrov´ana na obr´azku (b). Tentokr´at je testov´ y znak p´ısmeno e, kter´e se ve vzorku vyskytuje. Proto mus´ıme vzorek posunout tak, aby byly dvˇe ezarovn´any pod sebe. Tato vzd´alenost mus´ı b´ yt o jednu vˇetˇs´ı neˇz je e vzd´alenood konce vzorku. Vzorek tedy posuneme o 8-6+1=3 znaky. Na obr´azku (c) opˇet doˇslo k neshodˇe na prvn´ım porovn´avan´em znaku. Testov´ y znak je pr´azdn´e pol´ıˇcko, kter´e se ve vzorku nevyskytuje. Znovu posuneme vzorek o devˇet m´ıst. N´asleduje situace z obr´azku (d). Zde se stejnˇe jako u naivn´ıho algoritmu porovnaj´ı tˇri znaky(pro). Na ˇctvrt´em p´ısmenu dojde k neshodˇe. Protoˇze testov´ y znak i se ve vzorku nevyskytuje, pˇrem´ıst´ıme vzorek aˇz za tento testov´ y znak, tedyopˇet o devˇet m´ıst. Obr´azek (e). Zde je opˇet testov´ ym znakem p´ısmeno e a stejnˇe jako v pˇr´ıpadˇe (b),posuneme vzorek o devˇet m´ıst. Na obr´azku (f) je zobrazena koneˇcn´a situace. Vzorek je nalezen a bylo k tomu potˇreba pouh´ ychpˇet posun˚ u a celkem 16 porovn´an´ı. Nyn´ı se uˇz m˚ uˇzeme uv´est jak bude algoritmus vypadat zaps´an v pseudok´odu. Na vstup proceduradostane text T, vzorek P a abecedu Σ. Procedura opˇet vyhled´a pouze prvn´ı v´ yskyt pro nalezen´ı vˇsech v´ yskyt˚ u jsou vˇsak tˇreba jen drobn´e u ´pravy. Tabulku posun˚ u shift je nutno pˇred samotn´ ym vyhled´av´an´ım pˇredpoˇc´ıtat. (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
n = length(T) m = length(P) shift = Comp\_shift(P,$\Sigma$) pat = 1 s = 0 while (pat $<$= m \&\& pat+s $<$= n) if P[pat] == T[pat+s] then pat = pat+1 else s = s+shift[T[s+m+1]] pat = 1
Comp\_shift(P,$\Sigma$) (1) for kaˇ zd´ y znak a z abecedy $\Sigma$ (2) shift[a] = m+1 (3) for i = 1 to m (4) shift[P[i]] = m-i+1 (5) return shift K´od je pouze pˇrepisem fakt˚ u, kter´e tu byly vysvˇetleny. Snad jen pozn´amka k funkci Comp shift.V prvn´ım cyklu se vˇsem znak˚ um pˇriˇrad´ı hodnota maxim´aln´ıho posunu a teprve pot´e se prov´ad´ı proznaky, kter´e se ve vzorku vyskytuj´ı, pˇresnˇejˇs´ı u ´prava. V nejlepˇs´ım pˇr´ıpadˇe se neshoda objev´ı pokaˇzd´e hned u prvn´ıho porovn´avan´eho znaku (u prvn´ıho myˇsleno jako prvn´ıho po kaˇzd´em posunu). To znamen´a, ˇze posun bude pokaˇzd´e o ˇ m+1 znak˚ u. Casov´ a sloˇzitost je potom asi O(n/(m+1)). Kompletn´ı anal´ yza ˇcasov´e sloˇzitosti tohoto algoritmu zat´ım nebyla poskytnuta, ale Sunday tvrd´ı, ˇze nen´ı horˇs´ı neˇz O(n). >>>Obsah
21
IV. Srovn´ an´ı algoritm˚ u V t´eto kapitole si ˇrekneme v´ yhody a nev´ yhody algoritm˚ u, kter´e zde byly pops´any. Na jak´e u ´ˇcely se hod´ı a na jak´e ne. Prvn´ı algoritmus, kter´emu jsme se vˇenovali, byl tzv. naivn´ı algoritmus (odkaz). Mysl´ım, ˇze nem´a cenu se tomuto algoritmu vˇenovat moc dlouho, neboˇt svou ˇcasovou sloˇzitost´ı nen´ı pˇredurˇcen k pˇr´ıliˇs velk´emu pouˇzit´ı. Na druhou stranu pro relativnˇe kr´atk´e texty (ˇr´adovˇe o stovk´ach maxim´alnˇe tis´ıc´ıch znac´ıch) a kr´atk´e vzorky (20 p´ısmen) je tentoalgoritmus asi dobrou volbou, a to uˇz jenom z d˚ uvodu, ˇze ostatn´ı efektivn´ı algoritmy si pro sv´e potˇreby pˇredpoˇc´ıt´avaj´ı r˚ uzn´e tabulky, coˇz tento algoritmus nedˇel´a, a proto se u kr´atk´ ych text˚ u jeho pomalost neprojev´ı a vzhledem ke sv´e jednoduchosti implementace je mnohdy pouˇz´ıv´an (implementace v assembleru, pouˇzit´ı v jednoduch´ ych textov´ ych editorech apod.). Jeho nev´ yhodou je, ˇze pˇri pouˇzit´ı pro vyhled´av´an´ı v souborech m˚ uˇze doj´ıt k probl´emu s pamˇeˇtov´ ym bufferem, kter´ y je pops´an v u ´vodu kapitoly vˇenovan´e Knuth-Morris-Prattovu algoritmu. Dalˇs´ım algoritmem, kter´ y jsme si ukazovali, je pr´avˇe Knuth-Morris-Pratt˚ uv algoritmus (odkaz). Tento algoritmus odstraˇ nuje hlavn´ı nev´ yhody naivn´ıho algoritmu. Je to pˇredevˇs´ım v´ıcen´asobn´e testov´an´ı jednoho znaku a vracen´ı se v textu. D´ıky tomu je vhodn´ y pro vyhled´av´an´ı v textov´ ych souborech, neboˇt nevznikaj´ı probl´emy s pamˇeˇtov´ ym bufferem (pravdˇepodobnost, ˇze se tento probl´em vyskytne, je sice mal´a, ale pˇrihodit se m˚ uˇze). Nev´ yhodou ale je, ˇze se st´ale porovn´avaj´ı vˇsechny znaky textu (i kdyˇz jak uvid´ıme pozdˇeji, pro jist´e speci´aln´ı u ´ˇcely je to nezbytn´e). Algoritmus se hod´ı pro vyhled´av´an´ı vzork˚ u, o kter´ ychnejsou k dispozici ˇz´adn´e informace, a tedy nen´ı jist´e, jestli by bylo v´ yhodnˇejˇs´ı pouˇz´ıt obyˇcejn´ y naivn´ı algoritmus. V dalˇs´ı kapitole jsme se vˇenovali algoritmu Boyera a Moorea (odkaz). Tento algoritmus je asi vˇseobecnˇe nejl´epe pouˇziteln´ y i pˇres svou relativn´ı sloˇzitost implementace.Je zvl´aˇstˇe vhodn´ y pro vzorky vˇetˇs´ı d´elky a pro relativnˇe velkou abecedu znak˚ u, kde se obˇeheuristiky mohou plnˇe uplatnit. Narozd´ıl od pˇredchoz´ıch algoritm˚ u, tento prozkoum´a pouzezlomek vˇsech znak˚ uv textu (to se ale v nˇekter´ ych pˇr´ıpadech m˚ uˇze nevyplatit). Bohuˇzel d´ıkyzpˇetn´emu porovn´av´an´ı vzorku s textem m˚ uˇze doj´ıt stejnˇe jako u naivn´ıho algoritmu k probl´em˚ ums pamˇeˇtov´ ym bufferem, kter´ y vyˇzaduje dalˇs´ı reˇzii v´ ypoˇctu. I pˇres nepˇr´ıliˇs dobrou ˇcasovou sloˇzitost je v pr˚ umˇeru velmi dobr´ y. N´asleduje algoritmus Baeza-Yates-Gonnet (odkaz). Tento algoritmus je velmispecifick´ y, a proto jsou s n´ım spjat´a i jist´a omezen´ı co do implementace. Prvn´ım omezen´ım jepoˇzadavek na schopnost programovac´ıho jazyka (a poˇc´ıtaˇce) prov´adˇet bitov´e operace OR, AND a bitov´ y posun, na ˇc´ıslech typu integer. Druh´ ym a po pravdˇe ˇreˇceno asi drastiˇctˇejˇs´ım omezen´ım je d´elka bitov´ ych masek, kter´e se v algoritmu pouˇz´ıvaj´ı. Tyto masky mus´ı m´ıt stejnou d´elku ˇ v 32-bitov´e nebo v 64-bitov´e aritmetice, jako dan´ y vzorek. Dneˇsn´ı poˇc´ıtaˇce poˇc´ıtaj´ı vˇse bud coˇz je omezen´ı pro kompil´atory programovac´ıch jazyk˚ u a t´ım i pro d´elku bitov´e masky. Proto v pˇr´ıpadˇe, ˇze chceme hledat vzorek delˇs´ı neˇz 32 (potaˇzmo 64) bit˚ u, nen´ı tento algoritmus i pˇres svou rychlost tou spr´avnou volbou. Na druhou stranu, pokud chceme sestrojit algoritmus, kter´ y nebude case-sensitive (tedy nebude rozliˇsovat velikost p´ısmen), nen´ı probl´em upravitBaeza-Yates-Gonnet˚ uv algoritmus tak, aby tento poˇzadavek bez probl´em˚ u ˇreˇsil. Staˇc´ı ˇ pouze vyrobit masky zvl´aˇst pro velk´a a mal´a p´ısmena a trochu upravit vyhled´avac´ı ˇc´ast. T´ım se dost´av´ame k posledn´ımu algoritmu, kter´ y zde byl pops´an, Quicksearch (odkaz). Nejdˇr´ıve dvˇe fakta. Za prv´e tento algoritmus se stejnˇe jako KMP a BYG v textu nevrac´ı zpˇet. Za druh´e, stejnˇe jako Boyer-Moore˚ uv algoritmus i tento pˇreskakuje velk´e mnoˇzstv´ı neporovnan´ ych znak˚ u. Jak bylo ˇreˇceno, je tato skuteˇcnost v´ yhodou co do urychlen´ı algoritmu, ale ve speci´aln´ıch pˇr´ıpadech nen´ı toto pˇreskakov´an´ı ˇz´adouc´ı. Takov´ ym pˇr´ıkladem m˚ uˇze b´ yt situ22
ace, kdy pˇri kaˇzd´em nalezen´ı vzorku v textu chceme, aby program nahl´asil ˇc´ıslo ˇr´adky, kde se vzorek vyskytuje. V pˇr´ıpadˇe, kdy program poˇc´ıt´a kaˇzd´ y znak pro novou ˇr´adku a tento znak se posunut´ım vzorku o nˇekolik pozic pˇreskoˇc´ı, doch´az´ı pˇri nahl´aˇsen´ı v´ yskytu vzorku ke zkreslen´ı informace o ˇc´ısle ˇr´adky. Proto je pˇri v´ ybˇeru algoritmu nutn´e uvaˇzovat, k ˇcemu bude slouˇzit.Testy uk´azaly (na textech o d´elce pˇribliˇznˇe 200000 znak˚ u), ˇze Quicksearch si velmi dobˇre poˇc´ın´a v situac´ıch, kdy je vzorek relativnˇe delˇs´ı. Pˇri nejˇcastˇejˇs´ıch d´elk´ach vzork˚ u (od ˇsesti do osmip´ısmen) porovn´a algoritmus pouze pˇribliˇznˇe jednu ˇsestinu vˇsech znak˚ u. Z´aleˇz´ı vˇsak i na tom, jakvzorek vypad´a. Existuj´ı dvˇe upraven´e verze (maximal shift algorithm a optimal shiftalgorithm), kter´e dosahuj´ı o pˇet procent lepˇs´ıch v´ ysledk˚ u neˇz z´akladn´ı algoritmus. Vzhledemk tomu, ˇze pˇred vlastn´ım vyhled´av´an´ım pˇredpoˇc´ıt´avaj´ı spoustu r˚ uzn´ ych vˇec´ı, jsou ale vhodn´e pouze pro texty d´elky ˇr´adovˇe o stot´ıs´ıc´ıch znac´ıch. >>>Obsah
V. Z´ avˇ er
V tomto dokumentu jsme popsali nˇekolik algoritm˚ u zab´ yvaj´ıc´ıch se vyhled´av´an´ım vzork˚ uv textu.Vˇsechny maj´ı jednu vlastnost spoleˇcnou, vyhled´avaj´ı jeden vzorek v textu. Samozˇrejmˇe existuj´ıi algoritmy, kter´e vyhled´avaj´ı cel´e mnoˇziny vzork˚ u (algoritmus Aho-Corasickov´e, algoritmusCommentzWalterov´e) i mnoˇziny zadan´e pomoc´ı regul´arn´ıch v´ yraz˚ u (B-algoritmus). I pˇresto jsoutyto algoritmy velice uˇziteˇcn´e a svou vz´ajemnou rozd´ılnost´ı je spektrum jejich pouˇzitelnostipomˇernˇe ˇsirok´e. D´ale jsme si uvedli v´ yhody a nev´ yhody jednotliv´ ych algoritm˚ u, k ˇcemu sehod´ı a k ˇcemu. U kaˇzd´eho je vedle podrobn´eho vysvˇetlen´ı i pseudok´od, podle kter´eho by nemˇelb´ yt probl´em dan´ y algoritmus naprogramovat. Tento dokument je tedy jak´ ysi u ´vod do problematiky vyhled´av´an´ı v textu, neboˇt tato u ´lohaje velice rozs´ahl´a a zasahuje do mnoha obor˚ u teoretick´e informatiky. >>>Obsah
VI. Literatura Zde jsou uvedeny pouˇzit´e materi´aly. • T.H.Cormen, C.E.Leiserson, R.L.Rivest: Introduction to Algorithms, MIT Press 1990, kapitola34 - String matching • Ivana Vovsov´a: Vyhled´av´an´ı vzork˚ u v textu, diplomov´a pr´ace, MFF 1994 • String Searching, ˇcl´anek z nezn´am´e knihy od nezn´am´eho autora ´ • A. Koubkov´a, J. Pavelka: Uvod do teoretick´e informatiky, MFFPress 1998 >>>Obsah
23
