Knuth-Morris-Pratt algoritmus

Knuth-Morris-Pratt algoritmus  

KMP féle sztringkezelő algoritmus Szükséges matematikai fogalmak: Legyen Ω egy ábécé és x=x1x2…xn, k∈N karakterekből álló sztring, melynek elemei (xi) az Ω ábécé betűi. Az x sztringnek u-val jelölt részsztringjét x prefixének nevezzük, ha u=x1…xb, 0<=b<=k. Az x sztringnek u-val jelölt részsztringjét x suffixének nevezzük, ha u=xk-b+1…xk, 0<=b<=k. Az x-nek egy u prefixet vagy suffixet valódi prefixnek ill. valódi suffixnek nevezzük, ha u≠x, azaz ha b
14:59:33

1

Knuth-Morris-Pratt algoritmus  

Példa X=abacab 6 db valódi prefixe van: ε, a, ab, aba, abac, abaca 6 db valódi suffice van: ε, b, ab, cab, acab, bacab Borderek: ε, ab





Az üres sztring (ε), minden legalább 1 hosszúságú Ω ábécé feletti sztringnek bordere. Ugyanakkor ε-nak nincs bordere.

14:59:33

2

Knuth-Morris-Pratt algoritmus 

Az alapsztringben megtartjuk azt a pozíciót, amelyen áll, mégpedig úgy toljuk arréb a mintát, hogy a pozíciónktól balra továbbra is fennálljon az egyezés. Mekkora legyen a léptetés?

A P P P 14:59:33

bacbababaabcbab ↕↕↕↕↕↕ ababaca ababaca ababaca 3

Knuth-Morris-Pratt algoritmus



ababaca, ababaca, ababaca, ababaca ababaca, ababaca, ababaca Megoldás: A minta léptetésének mértékét a minta egyező prefixenek a legszélesebb bordere határozza meg. Ebben a példában az egyező prefix hossza 5. Ennek a leghosszabb bordere pedig 2. A léptetés teljes mértéke 5-2=3. Előfordulhat, hogy ezután sem lesz egyezés. Ekkor még inkább jobbra kell a mintát csúsztatni. Újabb egyező bordereket kerresve. (Ujabb léptetések: 3-2=1, ill. 1-0=1.)

15:04:11

4

KMP és mezítlábas algoritmusok

AA

PP

bacbababaabcbab bacbababaabcbab ↕↕↕ ↕↕↕↕↕↕↕↕ ↕ ababaca ababaca ababaca ababaca ababaca ababaca ababaca ababaca ababaca

1+2+1+1+6 1+2 1+2+1 1+2+1+1 1+2+1+1+6+0 1+2+1+1+6+0+1+0 1 1+2+1+1+6+0+1 1+2+1+1+6+0+1+0+1=13

AA

P PP

bacbababaabcbab bacbababaabcbab ↕↕↕ ↕↕↕↕↕↕↕↕ ↕↕↕↕↕ ↕↕↕ ababaca ababaca ababaca ababaca ababaca ababaca ababaca ababaca ababaca

1+2+1+1+6 1+2 1+2+1 1+2+1+1 1 1+2+1+1+6+1 1+2+1+1+6+1+4+1 1+2+1+1+6+1+4 1+2+1+1+6+1+4+1+2=19 14:59:33

5


Legyen x egy hosszú sztring. Legyen az x sztringnek r is és s is egy bordere, úgy hogy r|<|s|.

x=abacabacaba s=abacaba r=aba 

Ekkor belátható, hogy r bordere az s-nek is: r prefixe volt x-nek, a hosszuk miatt (|r|<|s|) látható, hogy s-nek is. A suffixre ez hasonlóan belátható.



Ha s a legszélesebb bordere x-nek, akkor az x következő (második legszélesebb) bordere az s legszélesebb bordere lesz. 14:59:33

6






A minta egy x prefixének az r bordere, néha bővíthető az a karakterrel úgy, hogy ra bordere xa-nak. (Ha szerencsénk van, a minta a-val folytatódik.) abacababadabacabaca abacababadabacabaca abacababadabacabaca Könnyű belátni, hogy amennyiben r a legszélesebb bordere volt x-nek, akkor ra is a legszélesebb bordere lesz xa-nak. Az algoritmus előfeldolgozási szakaszában egy m+1 elemű következő névvel ellátott tömböt számítunk ki. A tömb KÖV[i] eleme (i-edik eleme) a minta sztring i hosszúságú prefixéhez tartozó legszélesebb border hossza. i=0,..,m.

14:59:33

7








Mivel a 0 hosszúságú üres sztringnek nincs bordere, a KÖV[0]=-1 lesz. m értéke mindig a mintasztring hossza. Például, ha a számítás során már meghatároztuk a KÖV tömb 0-ás indexű elemét, és még néhány további elemét az i.-ig: KÖV[0],…,KÖV[i], és most meg szeretnénk határozni az következő elemet: KÖV[i+1]. Meg kell nézni, hogy a mintának a p1…pi prefixének egy bordere bővíthető-e az előbbi módon a minta következő, pi+1-edik karakterével.

14:59:33

abacababadabacabaca abacababadabacabaca

8

Knuth-Morris-Pratt algoritmus 1:abacababadabacabaca, 2:abacababadabacabaca 3:abacababadabacabaca, 4:abacababadabacabaca 5:abacababadabacabaca, 6:abacababadabacabaca 7:abacababadabacabaca, 8:abacababadabacabaca 9:abacababadabacabaca, 10:abacababadabacabaca 11:abacababadabacabaca, 12:abacababadabacabaca 13:abacababadabacabaca, 14:abacababadabacabaca 15:abacababadabacabaca, 16:abacababadabacabaca 17:abacababadabacabaca, 18:abacababadabacabaca 19:abacababadabacabaca  A bővítés akkor tehető meg, ha p köv[i]+1=pi+1.  A bordereket KÖV [i], KÖV[KÖV[i]], … behelyettesítve egyre mélyebben a KÖV értékeket, csökkenő sorrendjükben kell megvizsgálni.  Ha a border nem bővíthető egy kisebb bordert veszünk veszünk, hátha az bővíthető. Ha az sem, akkor egy 14:59:33 mégkisebbet, szűkebbet és így tovább.

9

Előfeldolgozó ciklus pszeudo-kódja Function KÖVFELTÖLT(P) 1. mhossz(P) 2. i0 3. j-1 4. KÖV[0] -1 5. While i<m do 6. If j=-1 vagy P[i+1]=P[j+1] then 7. ii+1

14:59:33

8. jj+1 9. KÖV[i]j 10. Else 11. j KÖV[j] 12. End if 13. End while 14. Return KÖV End function

10

KMP előfeldolgozó algoritmus 







Olyan ciklust tartalmaz, amelyben egy j változó rendre felveszi a KÖV tömb eggyel csökkenő indexű értékeit, addig amíg az értéke -1-re nem csökken. Egy j szélességű border bővíthető lesz a pi+1-s karakterrel, ha a pj+1=pi+1 Ha bővíthető volt a border tovább léptetjük a változókat, majd a KÖV tömb aktuális elemének értékül adjuk a j-t (border hosszát). Ha nem, a j változónak új értéket adunk.

14:59:33

11

KMP algoritmus pszeudo-kódja Function KMP(A,P) 1. nhossz(A) 2. mhossz(P) 3. KÖVKÖVFELTÖLT(P) 4. ij0 5. KÖV[0] -1 6. While i
10. Else 11. j KÖV[j] 12. End if 13. End while 14. If j=m then 15. Return i-m+1 16. Else 17. Return 0 18. End If End function 12






A borderek vizsgálata akkor ér véget, ha már nincs bővíthető border (j értéke -1). Ha a j változót növeltük, akkor p1…pi+1 prefix legszélesebb bordere j hosszúságú.

Példa: p=abacababadabacabaca

14:59:33

13


A P P P

Ha eltérést talál az algoritmus a j+1-edik pozíción, a továbbiakban a minta j hosszúságú, illeszkedő prefixének a legszélesebb borderét vizsgáljuk. (Ennek hossza: KÖV[j]). Úgy léptetjük a mintát, hogy ez a border továbbra is illeszkedjen az alapsztring már ellenőrzött részére. A léptetés mértéke: j-KÖV[j]. Ha még mindig eltérés van, a következő bordert vizsgáljuk, addig amíg el nem fogy a border (j=-1), vagy a j+1-edik helyen egyezés van, és a ciklus folytatódhat. bacbababaabcbab ↕↕↕↕↕↕ ababaca ababaca ababaca

14:59:33

14






Ha a minta minden karaktere (m db) illeszkedik az alapsztring megfelelő részére (j=m, 14-dik sor), akkor i-m+1-et adja (az illeszkedés következő indexét). Az összehasonlítások során az alapsztringben soha nem vizsgál meg újra a korábban már vizsgált karaktereket (i-t nem csökkenti), szemben a mezítlábas algoritmussal. j változó csökkentésének felső korlátja m (a minta hossza)

14:59:33

15

Shift-And (Dömölki-féle) algoritmus 



(Dömölki Bálint formális nyelvekkel foglalkozott). Később publikálták az algoritmust Baeza és Yates. (Dömölki-alg., Baeza-Yates-alg.) Az algoritmus alapötlete: Legyen p a minta sztringünk, amelynek hossza m. Vegyünk egy m elemű D vektort, amelynek a j-edik eleme 1 értékű, akkor, és csak akkor, ha a minta első j karaktere (p1…pj) szuffixe az alapsztring első i karakterének (a1…ai), egyébként pedig nulla.

14:59:33

16




Ha a p minta mérete kisebb mint a számítógép processzorának szóhossza, akkor ez a vektor a processzor egy regiszterében is tárolható. (Ilyenkor a későbbi keresés ezzel gyorsítható.) Tegyük fel, hogy az alapsztringet már megvizsgáltuk az i-edik karakteréig, és most olvassuk az i+1-edik karaktert. Ehhez egy új D’-vel jelölt vektort kell meghatározni.

14:59:33

17


Megfigyelés: A D’ vektor j+1-edik elemének értéke akkor és csak akkor lesz egy, ha egyrészt a D vektor j-edik eleme 1-es volt, vagyis p1…pj szuffixe volt a1…ai-nek,

másrészt, ai+1=pj+1,azaz a soron következő karaktere megegyezik a minta soron következő karakterével. 

Két része van az algoritmusnak: előfeldolgozás és keresés.

14:59:33

18

Shift-And (Dömölki-féle) algoritmus Előfeldolgozás: Fel kell építeni egy 2 dimenziós B bitmátrixot. Ennek a mátrixnak az oszlopait (m db van belőlük) a minta karaktereivel cimkézzük fel, a sorait pedig az ábécé egymástól különböző karaktereivel cimkézzük. A sorok cimkéi között nem lehet egyforma, de az oszlopoknál igen. A mátrixban egy elem értéke 1-es, ha a sorának és oszlopának az értéke megegyezik, és nulla egyébként. 14:59:33

19




További 3 db m elemű segédvektor is kell, amelyeket a következő kezdőértékkel látunk el: D segédvektort kezdetben csupa nulla értékkel töltjük fel. Az U segédvektor legelső eleme 1, a többi 0, és végül a V segédvektor utolsó, azaz m-edik eleme 1 és a többi 0. Az algoritmus egy shiftelő műveletet is fog még alkalmazni: SHIFT(X)=SHIFT(x1,x2,…xm)=(0,x1,…,xm-1).



Jobbra shiftelés: balról bejön egy nulla, jobboldalt az utolsó elem eltűnik.

14:59:33

20




Algoritmus: a sztringet karakterenként vizsgálja, és minden ai egyező karakterenként a D vektort frissiti a következő formula felhasználásával: D’=(SHIFT(D) U) Bai Ha a keresés során az i-edik karakter feldolgozásakor teljesül D V ≠(0,…..0), akkor megtaláltuk p egy előfordulását a-ban. p első karaktere a i-m+1-edik karakterére illeszkedik.

V=(0,0,0,…,0,0,1) 14:59:33

21

Shift-And (Dömölki-féle) algoritmus Egy Példa: a=atacgatatata p=atat

B:

a

t

a

t

a

1

0

1

0

t

0

1

0

1

*

0

0

0

0

i

ai

D(régi)

Shift(D)

Shift(D) U

Bai

D(új)

1

a

(0,0,0,0)

(0,0,0,0)

(1,0,0,0)

(1,0,1,0)

(1,0,0,0)

2

t

(1,0,0,0)

(0,1,0,0)

(1,1,0,0)

(0,1,0,1)

(0,1,0,0)

3

a

(0,1,0,0)

(0,0,1,0)

(1,0,1,0)

(1,0,1,0)

(1,0,1,0)

4

c

(1,0,1,0)

(0,1,0,1)

(1,1,0,1)

(0,0,0,0)

(0,0,0,0)

5

g

(0,0,0,0)

(0,0,0,0)

(1,0,0,0)

(0,0,0,0)

(0,0,0,0)

6

a

(0,0,0,0)

(0,0,0,0)

(1,0,0,0)

(1,0,1,0)

(1,0,0,0)

7

t

(1,0,0,0)

(0,1,0,0)

(1,1,0,0)

(0,1,0,1)

(0,1,0,0)

8

a

(0,1,0,0)

(0,0,1,0)

(1,0,1,0)

(1,0,1,0)

(1,0,1,0)

9

t

(1,0,1,0)

(0,1,0,1)

(1,1,0,1)

(0,1,0,1)

(0,1,0,1)

14:59:33

22






A keresés akkor ér véget, ha a D vektor utolsó pozícióján megjelenik egy 1-es érték. A Dömölki algoritmus viszonylag gyors, a bitmátrix egyszer kerül kiszámításra, aztán bitenkénti ÉS illetve VAGY műveletek vannak csak. (Itt az a lényeg, hogy amit mi egy vektorral elvégzendő műveletsornak látunk (Shift, „vagyolás”, „éselés”), az valójában a számítógépnek egy, vagy két változóval történő egyetlen elemi művelet elvégzését jelenti.) De még mindig lehet javítani ezen az algoritmuson is.

14:59:33

23

SHIFT-OR-Algoritmus 







A SHIFT-AND algoritmusnál az 1-es bit sorra vándorolt az utolsó pozícióig. A Shift-Or algoritmus 0-s bittel éri el ugyanezt, mindent a fordítottjával jelöl.

A vektorok is fordított bitekkel szerepelnek majd (D,V vektorok). A „vagyolás” kimaradhat, vagyis egy művelettel kevesebbet kell végrehajtani. (Az első „vagyolás” maradhat el, mivel nincs U tömb, az „éselés” pedig „vagyolás” lesz: itt ezt az egy műveletet kell elvégezni.)

14:59:33

24

SHIFT-OR-Algoritmus 

Változások a SHIFT-AND algoritmushoz képest:



SHIFT(x1,x2,…xm)=(0,x1,…,xm-1)



B: negáció, 0: ha a sor és az oszlop cimkéi megegyeznek.



V: negáció  V=(1,1,…,1,0)



U: nincs, megszűnik



Az algoritmus lépései módosulnak: D’=SHIFT(D) Bai

Az U-t megspóroljuk, mert (0,1,…,1) csak 0-ra állítja az első bitet, ami amúgy is nulla, így ez a vektor és ez a lépés felesleges. 14:59:33



25

Több minta egyidejű illesztése 





A Shift-And-algoritmussal egyszerre több mintát is kereshetünk az alapsztringben. (A Shift-Or-ral nem lehet egyszerre több mintát vizsgálni, kivéve ha viszavesszük az U vektort.)

A B bitmátrixot ki kell egészíteni Sorai ugyanazok Az oszlopai kiegészülnek a többi minta karaktereivel

Kitöltése ugyanúgy történik 

D, U és V is változik: U=(1,0,…,0,0|1,0,…,0,0|…)

14:59:33

V=(0,0,…,0,1|0,0,…,0,1|…)

26

Több minta egyidejű illesztése Példa: a=atacgatatata p1=atat p2=gat p3=tata

B: a t g *

| | | | |

atat 1010 0101 0000 0000

gat 010 001 100 000

tata 0101 1010 0000 0000

U=(1,0,0,0|1,0,0|1,0,0,0) V=(0,0,0,1|0,0,1|0,0,0,1)

D=(0,0,0,0|0,0,0|0,0,0,0) SHIFT(D) U=(1,0,0,0|1,0,0|1,0,0,0) (SHIFT(D) 14:59:33

U) Ba1=(1,0,0,0|0,0,0|0,0,0,0) 27

Minta illesztő algoritmusok  

Sok sztringkezelő algoritmus létezik még. Olyanok is vannak, amelyek összetett mintákát is tudnak illeszteni. Pl. „ab*c?d.e+f” *: tetszőleges számú karakter, ?: 0 vagy 1 karakter, .: tetszőleges karakter +: 1 vagy több karakter

Igy a fenti minta illeszkedik az alábbi alapsztringekre: „fgabbbdreefad”, „rtacdhefr”, „sabbbcdeeefh”, „addef” de nem illeszkedik az alábbiakra: „abbckld”, „acdb”, „cvfdcd” 14:59:33

28

Knuth-Morris-Pratt algoritmus

Recommend Documents