SHPORA.net :: PDA

[ Back ]

Täpne otsimine



Antud on:



1. sõne t pikkusega n (n võib olla suur) - tekst

2. sõne s pikkusega m (m <n) - muster, otsisõne



Leida: kõik positsioonid k, mille korral muster s esineb tekstis t positsioonis k



Naiivne algoritm selle ülesande lahendamiseks vaatab läbi kogu otsinguruumi, sobitades s kõikvõimalikesse positsioonidesse tekstis t, niisuguseid positsioone on n-m +1 tükki ja iga sobitus võtab halvimal juhul m võrdlust: seega on naiivse algoritmi keerukus O((n-m+1)m) ~ O(mn), m<n.

Knuth-Morris-Pratti algoritm



Naiivset algoritmi saab oluliselt parandada, analüüsides eelnevalt otsisõne struktuuri. Kui praegu "nihutatakse" mustrit igal sammul ühe positsiooni võrra, siis Knuth-Morris-Pratti algoritmis arvutatakse võimalikud nihked ette välja ning kantakse tabelisse, mida siis nihutamisel kasutatakse (tabelis sisalduvat nn. prefiksfunktsiooni võib tõlgendada ka lõpliku automaadi terminites).



Prefiksfunktsiooni väärtus arvutatakse otsisõne s iga positsiooni i jaoks ning see on pikima sellise s prefiksi pikkus, mis on positsioonis i-1 lõppeva s alamsõne sufiksiks.





Sama algoritm pseudokoodis





Rabin-Karpi algoritm



Täpse otsimise ülesannet oleme siiani lahendanud jõumeetodi parandamise teel pikemate hüpete suunas. Teine lähenemine on parandada otsisõne ja vastava tekstilõigu võrdlemise kiirust (seni O(m)). Sõnede võrdlemise asemel võrdleme nende räsisid (potentsiaalse valehäire hinnaga). Räsifunktsiooni väärtust arvutame järgneva tekstilõigu jaoks kasutades eelmise lõigu räsi. Selline lähenemine töötab siis, kui m ei ole suur ja tähestiku võimsus ei ole suur. Olgu näiteks tähestik { 0, 1, 2, ..., 9 }. Siis iga sõnet selles tähestikus esindab täisarv, mille kümnendkujuks see sõne on. Selle arvu väljaarvutamise keerukus on O(m). Samas saab mustri nihutamist paremale arvutada kiiremini (lahutame räsi väärtusest suurima järgu, korrutame tähestiku võimsusega ning lisame uue vähima järgu). Valehäired tekivad sellest, et me arvutame mingis jäägiklassiringis (ei ole otstarbekas arvutada väga suurte täisarvudega). Seega tuleb räside kokkulangemisel alati kontrollida, kas ka sõned tegelikult kokku langesid.