Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a tananyag kezdőlapjára (P)Ugrás a tananyag előző oldalára (E)Ugrás a tananyag következő oldalára (V)Fogalom megjelenítés (nem elérhető funkció)Fogalmak listája (nem elérhető funkció)Oldal nyomtatása (nem elérhető funkció)Oldaltérkép megtekintése (D)Keresés az oldalon (nem elérhető funkció)Súgó megtekintése (S)

Algoritmusok és adatszerkezetek / A Knuth-Morris-Pratt algoritmus

32. A Knuth-Morris-Pratt algoritmus

A „nyers erőt” használó egyszerű mintaillesztés műveletigénye legrosszabb esetben m*n-es volt. A Knuth-Morris-Pratt algoritmus (KMP-vel rövidítjük) egyike azon mintaillesztő eljárásoknak, amelyek ügyes észrevételek és mélyebb megfontolások alapján hatékonyabb módon oldják meg az stringkeresés feladatát.

32.1. Az algoritmus elve

Amikor az egyszerű mintaillesztés során az illeszkedés elromlott, a mintát egy pozícióval eltoltuk és az elejétől újra kezdtük a minta és a lefedett szövegrész összehasonlítását. Nem biztos azonban, hogy a már megvizsgált szövegrész minden karakterén újra át kell haladni. Amennyiben az illeszkedés elromlik, akkor egy „hibás kezdetünk” van, de ez a kezdet ismert, mivel az elromlás előtti karakterig egyezett a mintával. Ezt az információt használjuk fel arra, hogy elkerüljük az állandó visszalépést a szövegben a minta kezdetére. Tekintsük a 32.1. ábrán látható illeszkedési feladatot.

A példában a minta 6. pozíciójánál romlik el az illeszkedés, hiszen a minta első 5 pozíciója illeszkedett. Kérdés, hogy hová pozícionálhatjuk a mintát a szövegben, és honnan vizsgáljuk tovább az illeszkedést, hogy a minta előfordulását megtaláljuk (ha létezik, át ne "ugorjuk") és az eddig megszerzett 5 illeszkedő karakternyi információt felhasználjuk.

Látható, hogy a minta illeszkedő részének () van olyan valódi kezdőszelete (valódi prefixe), amely egyezik ezen illeszkedő rész egy valódi végszeletével (valódi szuffixével), hiszen ('ABA'='ABA'). A vizsgálatot ezért úgy is folytathatjuk, hogy a kezdőszelete „rátoljuk” a vele megegyező végszeletre, ahogyan a 32.2. ábrán látható.

(A továbbiakban inkább a karakterisztikusabb prefix és szuffix kifejezéseket használjuk a leírásban.) Egy prefix vagy szuffix valódi, ha hossza legalább 1, és kisebb, mint annak a sorozatnak a hossza, amelynek a prefixe vagy szuffixe.

Amennyiben a mintával akkorát ugrunk, hogy a minta eleje az említett szuffixnél kezdődjön, azaz az prefix a vele egyező szuffixszel kerüljön fedésbe, a prefixet már nem kell újra vizsgálni, mivel az azonos a szuffixel, ami megegyezik a szöveg lefedett részével, mivel az részsorozata az eredetileg illeszkedő szövegrésznek. Ezek után az illeszkedés vizsgálatot a szöveg "elromlott" karakterével, és az említett prefix utáni első karakterrel lehet tovább folytatni.

Mi a teendő több ilyen egyező prefix és szuffix pár esetén? A példában is találhatunk egy másik párost, az ('A'='A'). Ha annak megfelelően pozícionáljuk a mintát, ahogyan a 32.3. ábra is mutatja, majd a következő karaktertől kezdünk összehasonlítani, azt tapasztaljuk, hogy nem illeszkedik a minta a szövegre, mert "átugrottunk" egy illeszkedést.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej32_08_full.png32.3. ábra. Nem megfelelő eltolás több egyező prefix és suffix pár esetén

Tehát a legkisebb olyan ugrást kell választanunk, ahol a minta részsorozatának egy prefixe illeszkedik a részsorozat egy szufixére. Akkor "ugrunk" a legkisebbet, ha a legnagyobb ilyen prefixet választjuk.

Vissza a tartalomjegyzékhez

32.2. Az algoritmus helyessége

Ahhoz, hogy az algoritmus helyességét belássuk, a következő kérdéseket kell tisztáznunk. Tegyük fel, hogy a minta részsorozata illeszkedett a szöveg részsorozatára és az illeszkedés a következő pozíción romlott el, azaz

1.Ha létezik részsorozatnak olyan valódi prefixe () és szuffixe hogy , akkor valóban állítható-e, hogy az ugrás után biztosan nem kell újra vizsgálni az és az általa lefedett szövegrészt?

Biztosan nem kell, mivel , azaz , továbbá az illeszkedés az pozíción romlott el, tehát , és ezek tetszőleges, jelenleg fedésben lévő részsorozatai is azonosak, azaz . Érvelésünket alátámasztja a 32.4. ábra.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej32_435_full.png32.4. ábra. Példa egyező valódi prefix-szuffix párosra

2.Mit tegyünk, ha nincs ilyen egymással megegyező valódi prefix-szuffix páros?

Mivel illeszkedett és , eltolásra a minta biztosan nem fog illeszkedni. Ahogyan a 32.5. ábrán is látszik, ahhoz hogy ilyen i eltolással illeszkedjen, az kellene, hogy legyen legalább 1 hosszú valódi, egymással azonos prefix-szuffix páros (), mert az részsorozatoknak illeszkedniük kell (ekkor ) ahhoz, hogy teljes illeszkedés lehessen. Ebből pedig következik, hogy {alg2_kep_4425}, mivel .

(Beláttuk tehát, hogy az feltétel esetén, az érvényes eltolás szükséges feltételét is.)

Tehát a mintával "átugorhatjuk" a már vizsgált részt, és az illesztést a minta elejétől és a szöveg pozíciójától újra kezdhetjük. Ezt a konklúziót a 32.5. ábra is alátámasztja.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej32_448_full.png32.5. ábra. Példa nem egyező valódi prefix-szuffix párra

3.Mit tegyünk, ha több ilyen egymással megegyező, valódi prefix-szuffix páros is van?

Ha több ilyen prefix-szuffix páros is van, akkor a leghosszabbat kell venni, mert ekkor "ugrunk" a legkisebbet. Ilyenkor nem fordulhat elő, hogy átugrunk egy előfordulást.

Definiáljuk a next függvényt, amely megadja a minta egyes kezdőrészleteire a leghosszabb egymással egyező prefix-szuffix párok hosszát. Ezt felhasználva meg tudjuk adni a mintával való "ugrás" mértékét.

A next függvénnyel kapcsolatban a következő megjegyzéseket tesszük.

Vissza a tartalomjegyzékhez

32.3. A KMP algoritmus

A minta elejétől kezdjük összehasonlítani a szöveg és a minta egymással fedésben lévő karaktereit. Amennyiben a szöveg és minta karakterei azonosak, akkor a szövegben és a mintában egyaránt eggyel továbblépünk. Azonban, ha a karakterek különböznek, a következőket tesszük.

Mivel a szövegben legfeljebb 1 hosszú lépésekkel haladunk végig, az egyszerűség kedvéért a k eltolásnak megfelelő változó helyett használjunk egy i változót, amellyel a szövegben szekvenciálisan haladunk (), majd az algoritmus végén beállítjuk a k változó értékét. A KMP algoritmus a 32.6. ábrán látható.

Az initnext eljárás során töltjük fel a next vektort. A feltöltés ötlete: a minta elcsúsztatott keresése önmagán (KMP algoritmussal), miközben feljegyezzük a legnagyobb illeszkedő részek hosszát.

Nézzük meg egy példán a feltöltés menetét. Legyen a minta M='ABABAC'. Már korábban láttuk, hogy . Ezután a értékét szeretnénk meghatározni. Ekkor az kezdőrészletnek keressük a legnagyobb egymással megegyező, valódi prefix-szuffix párját. A legnagyobb ilyen valódi prefix-szuffix 1 hosszúságú lehet. Tehát az a kérdés, hogy az egyenlőség teljesül-e? Ehhez a mintát csúsztassuk el eggyel, és a fedésben lévő karaktereket vizsgáljuk (lásd: 32.7. ábra):

Látható, hogy a két karakter nem azonos, így .

Most a meghatározása következik. Ekkor az kezdőrészletnek keressük a legnagyobb egymással megegyező, valódi prefix-szuffix párját. A legnagyobb ilyen valódi prefix-szuffix 2 hosszú lehet. Azaz egyenlőség teljesül-e? Azonban ez nem teljesülhet, mivel már sem teljesült. Ezt nem is vizsgáljuk, mivel már az előző menetben sem volt egyezés. Helyette a mintát eggyel jobbra csúsztatjuk, és az egyenlőséget vizsgáljuk (lásd: 32.8. ábra):

A vizsgált egyenlőség fennáll, ezért feljegyezzük, hogy

Ezután a kiszámítása a cél. Ekkor az kezdőrészletnek keressük a legnagyobb egymással megegyező, valódi prefix-szuffix párját. A legnagyobb ilyen valódi prefix-szuffix 3 hosszú lehetne, de egyenlőséget már korábban is megvizsgáltuk és nem teljesült, így ez nem jöhet szóba. Azonban, az előző menetben teljesült, így az ennek megfelelő elcsúsztatott pozíciót megtartva vizsgáljunk tovább, mert további karakter egyezés esetén ez lehetne a leghosszabb prefix-szuffix pár (lásd: 32.9. ábra):

Valóban az teljesül, így feljegyezzük értéket.

A meghatározásához, az előző menethez hasonlóan a mintát nem csúcstatjuk el, hanem a következő karaktert vizsgáljuk (lásd: 32.10. ábra):

Azt látjuk, hogy , így feljegyezzük .

Összefoglaljuk egy ábrán a next függvény kiszámítását (lásd: 32.11. ábra):

A kép (nagyobb változata) külön ablakban is megtekinthető.fej32_488_full.png32.11. ábra. A next vektor kiszámítása (összefoglalás)

A next vektor kitöltésének részletes végigkövetése után már nem nehéz felírni az initnext eljárást, amely 32.12. ábrán látható. Ezzel teljessé vált a 32.6. ábrán megadott KMP mintaillesztő algoritmus, ugyanis az inicializáló eljárását is megalkottuk.

Az initnext eljárás különlegessége az, hogy a KMP mintaillesztés inicializálására szolgál, de a next vektor kitöltésére is lényegében a KMP algoritmust használjuk. Ezt az teszi lehetővé, hogy a kitöltés éppen olyan mértékben halad előre a next vektoron, mint ami a számítás továbblépéséhez szükséges, amivel egy saját belső inicializáló eljárást valósítunk meg.

A KMP algoritmus műveletigényének megállapításához vegyük figyelemben, hogy inicializáló tevékenység, az initnext eljárás lépésszáma Tegyük fel, hogy ; ekkor a keresés műveletigénye legjobb és legrosszabb esetben is egyaránt . A KMP algoritmust ezért stabil eljárásnak mondhatjuk.

Mivel a KMP algoritmus működése során a szövegben csak legfeljebb egy pozícióval történő előre lépést teszünk (nincs visszalépés), így az algoritmus puffer használata nélkül is átírható szekvenciális sorozat, illetve fájl formában adott szövegre.

Vissza a tartalomjegyzékhez

Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.

A tananyag az ELTE - PPKE informatika tananyagfejlesztési projekt (TÁMOP-4.1.2.A/1-11/1-2011-0052) keretében valósult meg.
A tananyag elkészítéséhez az ELTESCORM keretrendszert használtuk.