Za iskanje podnizov v besedilu obstaja več različnih algoritmov(npr: Brute Force algoritem/Groba Sila, Algoritem Boyer-Moore, Rabin-Karpov algoritem, Algoritem Knuth-Morris-Pratt...) in še veliko drugih algoritmov.

Njihova skupna naloga je, da v besedilu poiščejo nek krajši vzorec ali besedo. Vendar je njihov način iskanja podniza v besedilu različen.

Algoritem Knuth-Morris-Pratt zagotavlja, da pri iskanju podniza v besedilu, ne bo več kot n primerjav, pri katerem je n dolžina besedila (vsak znak besedila oz. niza ne pregledamo več kot enkrat). Algoritem Knuth-Morris-Pratt primerja besedilo z vzorcem od leve prosti desni. Zato je podoben Brute Force (Groba Sila) algoritmu, vendar je algoritem KMP bolj učinkovit, ker si pri pregledovanju in primerjanju zapomni že pregledani del besedila in to uporabi pri nadaljnem iskanju.

Že pregledani del besedila si zapomni s pomočjo funkcije failure function (funkcija neuspeha/funkcija delnega ujemanja). Ta funkcija nam omogoča, da pri premikanju ne spregledamo ujemanja med besedilom in vzorcem.

Primer

Denimo, da v besedilu SPOMLADANSKI DAN iščemo vzorec DAN. Funkcija Knuth-Morris-Pratt nam kot rezultat vrne 6. To število predstavlja indeks v besedilu, torej se ujemanje začne na 7 mestu v besedilu. Če v besedilu SONČEN DAN iščemo vzorec SONCE, pa za rezultat dobimo -1, saj funkcija v besedilu ne najde vzorca.

Ideja algoritma Brute Force ali Groba sila je, da zaporedoma pregledamo vsak znak v besedilu B in preverimo ali se naš vzorec V začne na tem trenutem mestu v besedilu. Naš vzorec V v besebilu B iščemo tako, da primerjamo vsak znak posebej. Če najdemo znaka, ki se ne ujemata, se naše primerjanje konča in celoten vzorec pomaknemo za en znak v desno po besedilu. Če pa s primerjanjem pridemo do konca vzorca V, smo našli vzorec V v besedilu B. Kadar pri primerjanju vzorca in besedila, ne najdemo našega vzorca v besedilu, pa za rezultat dobimo -1.

Primer iskanja vzorca "mati" v besedilu "matematika".

Iskanje vzorca v besedilu z algoritmom Groba sila

Primerjamo posamezne znake od leve proti desni. Primerjamo znaka "m" in "m", znaka sta enaka, zato nadaljujemo primerjanje. Primerjamo znaka "a" in "a" in ponovno najdemo ujemanje. Sledi primerjava znakov "t" in "t" in nadaljujemo primerjanje znakov. Pri primerjavi znakov "e" in "i" smo prišli do neujemanja. Sedaj se moramo s celotnim vzorcem za en znak pomakniti v desno.

Iskanje vzorca v besedilu z algoritmom Groba sila

Nadaljujemo primerjanje. In takoj najdemo neujemanje (znak "a" je različen od znaka "m" ). Zato se s celotnim vzorcem za en znak pomaknemo v desno.

Iskanje vzorca v besedilu z algoritmom Groba sila

Nadaljujemo primerjanjein ugotovimo, da znaka "t" in "m" nista enaka. Torej se ponovno s celotnim vzorcem za en znak pomaknemo v desno.

Iskanje vzorca v besedilu z algoritmom Groba sila

Primerjamo znaka "e" in "m" in ugotovimo, da se ne ujemata. Zato se ponovi postopek: s celotnim vzorcem se pomaknemo za en znak v desno.

Iskanje vzorca v besedilu z algoritmom Groba sila

Primerjamo znaka "m" in "m", ker smo našli enaka znaka nadaljujemo primerjanje (sedaj vzorca ne premikamo). Primerjamo "a" in "a" in gotovimo enakost, zato nadaljujemo primerjanje. Znaka "t" in "t" sta enaka ter prav tako znaka "i" in "i". Ker smo prišli do konca vzorca smo našli vzorec v besedilu. Algoritem nam vrne 4, ker to označuje začetek vzorca v besedilu.

Algoritem Groba sila deluje zelo počasi, saj se vsak znak večkrat pregleda. Z izboljšavo algoritma Groba sila je eden od algoritmov, Algoritem Knuth-Morris-Pratt. Algoritem KMP je podoben algoritmu Groba sila, vendar slednji s pomočjo funkcije neuspeha preskoči določene enake pojavitve vzorca v besedilu in tako hitreje najde vzorec v besedilu (če je v njem).

Funkcijo failure function (funkcija neuspeha) uporabljamo na vzorcu, ki ga iščemo v besedilu. Pove nam za koliko mest se lahko premaknemo po besedilu, da s tem ne spregledamo nobene pojavitve vzorca v besedilu. Ko funkcijo uporabimo na besedi, nam vrne seznam števil.

Primer uporabe funcije neuspeha v Python-u

Funkcija neuspeha besede ananas

Če uporabimo funkcijo neuspeha (oznaka F(k)) na vzorcu SONCE kot rezultat dobimo [0,0,0,0,0]. Same ničle v seznamu pomenijo, da se vsak znak v nizu pojavi samo enkrat. Pri vzorcu ANANAS kot rezultat dobimo [0,0,1,2,3,0].

Sestavljanje F(k) tabele za vzorec ANANAS in kaj posamezno število predstavlja:

• F(0) = 0 velja za vsak vzorec, saj je na mestu 0 tisti znak vedno prvi v vzorcu in še ni imel ponovitve;
• F(1) = 0, saj se znak "n", še ni pojavil v vzorcu;
• F(2) = 1, našli smo podniz "a",če se z "a" vrnemo na začetek vzorca vidimo, da se znaka ujemata in podniz je dolžine 1;
• F(3) = 2, našli smo podniz "an", ker če se z podnizom vrnemo na začetek vzorca, najdemo ujemanje. Podniz je dolžine 2, zato je vrednost funkcije enaka 2;
• F(4) = 3, našli smo podniz "ana". Podniz se ujema z začetkom vzorca V in je dolžine 3, zato je vrednost funkcije enaka 3.
• F(5) = 0, našli smo niz "s", ki se v vzorcu še ni pojavil.

Funkcija neuspeha-filemček

Funkcija v Python-u

RAZLAGA KODE:

Funkcija neuspeha bo vedno sprejela niz. Zapomniti oz. shraniti v spremenljivko (»d«) si bo potrebno dolžino podanega niza, da bomo vedeli, kdaj smo pregledali celoten niz. Potrebovali bomo »števec« (»j«), ki bo na začetku enak nič, ker pregledujemo vzorec od leve proti desni. Števec "j" se bo povečal, ko bomo našli enaka znaka v nizu ter dobil novo vrednost, ko bosta znaka različna. Števec "k" ima na začetku vrednost 1, ker primerjamo j-ti in k-ti element niza (pri k=0, ima funkcija neuspeha vedno vrednost 0). Narediti bo potrebno seznam ničel(»sez«), ki bo enak dolžini podanega niza. Ta seznam se bo spreminjal pri določanju funkcije Failure function (funkcija neuspeha) in na koncu ga vrnemo kot rezultat funkcije. Zanka »while« bo potrebna, da bomo pregledali celoten niz od indeksa 1 do konca niza. Znake z indeksom 0, ni potrebno vključiti v zanko »for«, ker je vrednost funkcije neuspeha vedno enaka 0. Znotraj »for« zanke ločimo 3 možnosti(pomagamo si s pogojnimi stavki):

• V primeru, da sta »j«-ti in »k«-ti znak v nizu enaka, v seznamu na »k«-tem mestu povečamo njegovo vrednost za 1 (v nizu smo našli podniz) in spremenljivkama »j« in »k« povečamo vrednost za 1, ker smo našli enaka znaka in z naslednjim primerjanjem bomo ugotavljali če se podniz nadaljuje(oz. če se ujemata tudi znaka na (j+1)-tem in (k+1)-tem mestu);
• V kolikor zgornji pogoj ne drži, preverimo, če sta »j«-ti in »k«-ti znak v nizu različna in je hkrati sprem. »j>0«. Če je slednji pogoj izpolnjen, spremenljivki »j« spremenimo vrednost, ki bo enaka vrednosti na j-1 mestu v seznamu »sez« (z kazalcem j se pomaknemo po vzorcu nazaj, da preverimo enakosti z ostalimi znaki);
• Če ni izpolnjen nobeden od zgornjih pogojev, v seznamu na »k«-tem mestu nastavimo vrednost 0, ker tega znaka v nizu še ni bilo (znak nima trenutno nobenega podniza).

Na koncu vrnemo seznam »sez« , ki smo ga ustvarili na začetku začetku in smo ga seveda spreminjali tekom naše funkcije.

Če želimo predstaviti delovanje Knuth-Morris-Pratt algoritma, to najlažje storimo s pomočjo tabele.
B nam predstavlja besedilo in V vzorec katerega iščemo. Primerjamo znaka B[i] in V[j]

• Če se ujemata i-ti element B-ja in j-ti element V-ja, preverimo, če j slučajno predstavlja zadnji indeks vzorca V.

  • Če ga, smo našli naš vzorec v besedilu in vrnemo indeks začetne črke vzorca v besedilu B.
  • Če indeks j ne predstavlja zadnje črke, i in j povečamo za 1.
• Drugače pa pogledamo vrednost j-ja. Če je večja od nič, to pomeni, da trenutno ne gledamo prve črke vzorca, zato spet začnemo iskati celoten vzorec znotraj besedila. Se pravi, moramo ju »premakniti« na mesto,ki ga dobimo s pomočjo funkcije neuspeha oz. na mesto neujemanja besedila z vzorcem (takrt je premik maksimalen). Posledično vemo kje se lahko naše primerjanje besedila in vzorca nadaljuje. To ponavljamo dokler je spremenljivka i manjša od dolžine besedila oz. dokler ne najdemo celotnega vzorca v besedilu.

Kadar ne uspemo najti delnega ujemanja (posamezne črke) v besedilu se s celotnim vzorcem premikamo za en znak v desno. Tudi če je vzorec v besedilu, a se noben drug del besedila ne ujema, se zgodi podobno.

Primer: Pri primerjavi B[0] in V[0] velja neenakost, zato se z vzorcem V premaknemo v desno za ena.

Začetek reševanja naloge(lahke naloge, saj najdemo rešitev, ko vzorec V enkrat premaknemo v desno)

Pri ponovnem primerjanju vidimo popolno ujemanje in tako dobimo končno rešitev.

Rešitev

Prvi korak

Prvi štirje znaki se ujemajo, zato velja B[0]=V[0], B[1]=V[1], B[2]=V[2], B[3]=V[3]. Znak B[4]->'o' pa ni enak znaku V[4]->'a'. Zadnje ujemanje smo našli na V[3] in sedaj si pomagamo s funkcijo neuspeha. Z začetkom vzorca se pomaknemo na mesto našega neujemanja (i=4) in pogledamo vrednost funkcije pri k=3, F(k=3)=0(zaradi zadnjega ujemanja) in ker je njena vrednost enaka 0, naš premik ni bil prevelik. Lahko tudi izračunamo, za koliko mest se lahko premaknemo z vzorcem V po besedilu B: 4-F(3)=4-0 = 4. Torej se lahko premaknemo za 4 mesta v desno (v vzorcu "mojca" ni podnizov in se vsak znak pojavi samo enkrat, zato je premik maksimalen) in primerjamo B[4] in V[0].

Drugi korak

Primerjamo B[4]->'o' in V[0]->'m' in iz tega sledi, da enakost ne velja. Torej se premaknemo za en znak v desno, ker nismo našli ujemanja že pri prvem znaku . Ponovno ne najdemo ujemanja, torej ponovimo in se še enkrat pomaknemo v desno. Ponovno najdemo ujemanje: B[6]=V[0] in B[7]=V[1]. Pri naslednjem primerjanju enakost ponovno ni izpolnjena. Pri zadnjem ujemanju je: j=1->k=1. Z začetkom vzorca se pomaknemo na mesto našega neujemanja (i=8) in v tabeli funkcije neujemanja preverimo za koliko mest smo se preveč premaknili v desno. Vrednost funkcije pri F(2)=0, torej se nismo premaknili preveč in nadaljujemo iskanje vzorca v besedilu.

Peti korak

Pri prvem primerjanju velja enakost, torej B[8]=V[0], nato pa sledi neenakost, zato se z vzorcem pomaknemo za en znak v desno. In to ponavljamo, dokler ne primerjamo B[14] in V[0] in ponovno najdemo enakost. Prav tako velja: B[15]=V[1], B[16]=V[2], B[17]=V[3], B[18]=V[4]. In tako smo našli podniz v danem besedilu.

Rešitev

Iskanje vzorca v besedilu

Funkcija neuspeha

Tabela funkcije neuspeha

Algoritem Knuth-Morris-pratt

Vzorec "cbcbcd" bomo poiskušali poiskati v besedilu "cbcbccbcaacbcbcd"

Začetek iskanja vzorca v besedilu

Velja:

• B[0]=V[0];i in j povečamo za 1
• B[1]=V[1];i in j povečamo za 1
• B[2]=V[2];i in j povečamo za 1
• B[3]=V[3];i in j povečamo za 1
• B[4]=V[4];i in j povečamo za 1
  
  Pri primerjanju B[5] in V[5] ugotovimo da enakost ne velja. Sedaj se z začetkom vzorca premaknemo na mesto neujemanja in preverimo za koliko mest smo se preveč premaknili v desno. S tem bi spregledali določene pojavitve vzorca v besedilu. Zadnje ujemanje smo našli pri j=4 in iz tega sledi, da je k=4. Pogledamo vrednost F(k)=F(4)=3 in to pomeni, da smo se z vzorcem premaknili za 3 mesta preveč v desno. Vzorec premaknemo (nazaj) v levo za 3 mesta. Lahko naredimo tudi izračun premika: 5 (mesto neujemanja znakov)-F(4)(zadnje ujemanje znakov, pri j=4)=5-3=2 mesta v desno. Na naslednjem koraku primerjamo B[2] in V[0].

Drugi korak pri iskanja vzorca

Velja:

• B[2]=V[0];i in j povečamo za 1
• B[3]=V[1];i in j povečamo za 1

• B[4]=V[2];i in j povečamo za 1

  • Pri primerjanju B[5] in V[3] ugotovimo da enakost ne velja.

• Z začetkom vzorca se premaknemo na mesto našega neujemanja (i=5; na mesto v besedilu: B[5])

  • Zadnje ujemanje smo našli pri j=2, iz tega sledi k=2;

  • Pogledamo vrednost F(k) za k=2 -> F(2)=1

    • Za en znak smo se preveč premaknili v desno, torej se za en znak premaknemo (nazaj) v levo
    • Izračun premika: 5-F(2)=5-1=4

  • Na naslednjem koraku primerjamo B[4] in V[0]
    

    Tretji korak pri iskanju vzorca

    
    Velja:

• B[4]=V[0]
• Pri naslednjem primerjanju B[5] in V[1] ugotovimo, da znaka nista enaka.Z začetkom vzorca se premaknemo na mesto našega neujemanja (i=5). Zadnje ujemanje pri j=0, iz tega sledi, da je k=0. Vrednost funkcije neujemanja F(0)=0 in to pomeni, da se z vzorcem nismo preveč premaknili v desno. Nadaljujemo iskanje vzorca v besedilu.

Četrti korak iskanja vzorca

Velja:

• B[5]=V[0]; i in j povečamo za 1
• B[6]=V[1]; i in j povečamo za 1
• B[7]=V[2]; i in j povečamo za 1
• pri primerjanju B[8] in V[3] ugotovimo da znaka nista enaka.

Z začetkom vzorca se premaknemo na mesto našega neujemanja(i=8).

• Zadnje ujemanje na mestu j=2. Iz tega sledi, da je k=2.
• Pogledamo vrednost F(2), ki ima vrednost 1 (za en znak smo se premaknili preveč v desno)

• Izračun premika: premaknemo na 8 (mesto neujemanja)-F(2)(vrednost funkcije neujemanja pri k=2)=8-1=7 mesto v besedilu.
  

  Peti korak iskanja vzorca

Velja:

• B[7]=V[0]
• Pri naslednjem primerjanju B[8] in V[1] ugotovimo, da enakost ne velja. Z začetkom vzorca se premaknemo na mesto neujemanja(i=8) Zadnje ujemanje imamo pri j=0, zato je k=0. Vrednost funkcije neuspeha pri k=0 je enaka 0. Zato vemo, da se z vzorcem nismo preveč premaknili v desno. Ta korak se ponovi še dvakrat.

Zadnji korak iskanja vzorca

Velja:

• B[10]=V[0]; i in j povečamo za 1
• B[11]=V[1]; i in j povečamo za 1
• B[12]=V[2]; i in j povečamo za 1
• B[13]=V[3]; i in j povečamo za 1
• B[14]=V[4]; i in j povečamo za 1
• B[15]=V[5] -> našli smo vzorec v besedilu

Funkcija KnuthMorrisPratt nam za rezultat vrne 10. Torej ujemanje se v besedilu začne na 11 mestu.

Koda v programu Python

RAZLAGA KODE:

Funkcija »KnuthMorrisPratt« bo sprejela 2 niza. Prvi niz bo predstavljal besedilo in drugi vzorec, katerega bomo v besedilu iskali. V primeru, če bo besedilo krajše od vzorca, sprožimo izjemo, ker mora biti besedilo vedno daljše oz. vsaj enako dolgo kot vzorec. V spremenljivki »b« in »v« bomo shranili dolžini besedila in vzorca. S pomočjo metode »list« bomo naredili tabeli znakov niza »b« in niza »v«. Na vzorcu bomo poklicali funkcijo »funkcijaNeuspeha« in jo shranili v spremenljivko (»fx«). Potrebovali bomo tudi dva števca, enega (»j«), ki bo »šel« po vzorcu in drugega(»i«), ki bo «šel« po besedilu. Sledila bo »while« zanka, ki se bo izvajala dokler bo i (števec, ki »gre« po besedilu)manjši od b (dolžina besedila). Znotraj zanke »while« bodo trije pogojni stavki:

• Stavek »if« bo preveril, če sta »i«-ti znak besedila in »j«-ti znak vzorca enaka, ker iščemo vzorec v besedilu. Če bo pogoj izpolnjen, sledi še en pogojni stavek.

  • Slednji bo izpolnjen če velja i=v-1 (če je vrednost sprem. »i« enaka dolžini vzorca-1) in vrnili bomo indeks besedila, kjer se začne vzorec,
  • Sicer bomo samo povečali vrednosti sprem. »j« in »i« za ena;
• če se bo izvršil stavek »elif«, pomeni, da »i«-ti znak besedila in »j«-ti znak vzorca nista enaka. Slednji bo izpolnjen, če bo »j>0«. Takrat bomo spremenili vrednost sprem. »j«, ki bo enaka vrednosti na j-1 mestu v »fx« (tabela sestavljena z funkcijo neuspeha);
• sicer pa bomo sprem. »i«, ki »gre« po besedilu povečali vrednost za 1. Če se bo while zanka izvršila do konca, torej bo i>=b, bo pomenilo, da nismo našli vzorca v besedilu, zato vrnemo -1.

http://en.wikibooks.org/wiki/Algorithm_Implementation/String_searching/Knuth-Morris-Pratt_pattern_matcher

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

http://rc.fmf.uni-lj.si/matija/OpravljeneDiplome/Diploma_TekstovniAlgoritmi_AnjaRozac.pdf

http://www.ics.uci.edu/~eppstein/161/960227.html