Cautarea de siruri Knuth-Morris-Pratt

Cautarea de siruri Knuth-Morris-Pratt

Noul algoritm se bazeaza pe observatia ca avansul modelului in cadrul sirului cu o singura pozitie la intalnirea unei nepotriviri, asa cum se realizeaza in metoda anterioara, pe langa o eficienta scazuta, conduce la pierderea unor informatii utile.

Astfel dupa o potrivire partiala a inceputului modelului cu sirul,

Intrucat se cunoaste partial sirul (pana in punctul baleat),

Daca avem cunostinte apriorice asupra modelului obtinute prin precompilare,

Le putem folosi pentru a avansa mai rapid in sir.

Acest lucru este pus in evidenta de exemplul urmator in care:

Se cauta modelul MARGINE in textul sursa;

Caracterele care se compara sunt cele subliniate;

Dupa fiecare nepotrivire, modelul este deplasat de-a lungul intregului drum parcurs intrucat deplasari mai scurte nu ar putea conduce la o potrivire totala [4.3.3.a].

MAREA MARMARA SE MARGINESTE

MARGINE

MARGINE

MARGINE

MARGINE

MARGINE [4.3.3.a]

MARGINE

. . .

MARGINE

Rezultatul esential este acela ca valoarea lui d este determinata exclusiv din structura modelului si nu depinde de textul propriu-zis.

Analiza cautarii KMP.

Analiza exacta a performantei cautarii de siruri Knuth-Morrison-Pratt este asemeni algoritmului foarte sofisticata.

Inventatorii demonstreaza ca numarul de comparatii de caractere este de ordinul  n + m , ceea ce reprezinta o imbunatatire substantiala fata de  m  n .

De asemenea se subliniaza faptul ca pointerul  i care baleeaza sirul nu merge niciodata inapoi spre deosebire de cautarea directa, unde dupa o potrivire partiala se reia cautarea cu modelul deplasat cu o pozitie, chiar daca o parte din caracterele sirului au fost deja parcurse.

Acest avantaj permite aplicarea acestei metode si in cazul unor prelucrari secventiale.