Proiect Analiza Algoritmilor
Ideea de bază a algoritmului descoperit de Knuth, Morris şi Pratt este următoarea: când o nepotrivire este detectată, "începutul fals" se constituie din caractere pe care le ştim deja, din moment ce ele se află în şablon. Într-un anumit mod, ar trebui să ne putem folosi de această informaţie, în loc să deplasăm indicele i înapoi peste toate aceste caractere cunoscute.
Ca un simplu exemplu, să presupunem că primul caracter din şablon nu mai apare din nou (şablonul este de forma 10000000 ). De asemenea, să presupunem că avem un început fals de lungime j , la o poziţie oarecare în text. Când nepotrivirea este detectată, ştim deja că j caractere s-au potrivit şi că nu avem nevoie să deplasăm înapoi indicele i , din moment ce nici unul dintre cele j - 1 caractere precedente nu se potriveşte cu primul caracter din şablon. Această schimbare ar putea fi implementată înlocuind i ← i - (j - 1) cu i ← i + 1 . Efectul practic al acestei schimbări este limitat datorită faptului că un asemenea şablon particular este puţin probabil, însă ideea merită reţinută iar algoritmul Knuth - Morris - Pratt este o generalizare a ei. Surprinzător, întotdeauna este posibilă o aranjare a lucrurilor astfel încât i nu este decrementat niciodată.
Deplasarea peste întreg şablonul la detectarea unei nepotriviri nu conduce la o soluţie corectă atunci când acesta s-ar putea afla la poziţia detectării nepotrivirii. De exemplu, atunci când căutăm 10100111 în 1010100111 , detectăm o primă nepotrivire la al cincilea caracter, dar pentru a continua căutarea ar trebui să ne întoarcem la al treilea caracter, deoarece altfel am pierde potrivirea. Cu toate acestea, ne putem da seama dinainte exact de ceea ce trebuie să facem, deoarece depinde numai de şablon, ca în figura următoare:
| j | urmator[j] | |
| 1 | 0 | 10100111 10100111 |
| 2 | 0 | 10100111 10100111 |
| 3 | 1 | 10100111 10100111 |
| 4 | 2 | 10100111 10100111 |
| 5 | 0 | 10100111 10100111 |
| 6 | 1 | 10100111 10100111 |
| 7 | 1 | 10100111 10100111 |
Vectorul urmator[m] va fi folosit pentru a determina cât de mult trebuie ca algoritmul "să se întoarcă" atunci când o nepotrivire este detectată. Să ne imaginăm că deplasăm o copie a primelor j caractere ale şablonului de la stînga la dreapta, începând cu primul caracter al copiei peste cel de-al doilea caracter al şablonului şi oprindu-ne când toate caracterele suprapuse se potrivesc (sau nu există nici unul). Caracterele suprapuse definesc următorul loc posibil unde şablonul s-ar putea potrivi, dacă o nepotrivire este detectată la p[j] . Distanţa de întoarcere ( urmator[j] ) este dată de numărul de caractere suprapuse. În particular, pentru j > 0 , valoarea lui urmator[j] este valoarea maximă k < j pentru care primele k caractere ale şablonului se potrivesc cu ultimele k caractere dintre primele j caractere ale şablonului. După cum vom vedea, este util să luăm prin definiţie urmator[0] ← -1 .
Vectorul urmator dă o metodă imediată de a limita (de fapt, după cum vom vedea, de a elimina) întoarcerea indicatorului i în text, după cum am specificat mai sus. Atunci când i şi j indică spre caractere care nu se potrivesc (testarea pentru o potrivire începând la poziţia i - j + 1 în text), următoarea poziţie posibilă pentru o potrivire este i - urmator[j] . Dar, prin definiţia tabloului urmator , primele urmator[j] caractere de la acea poziţie se potrivesc cu primele urmator[j] caractere ale şablonului, deci nu este nevoie ca i să se întoarcă atât de mult: putem să îl lăsăm nemodificat şi să setăm indicatorul j la urmator[j] , ca în următorul algoritm:
01: KMP(p, a)
|
Când j = 0 şi a[i] nu se potriveşte cu p[0] , nu este nici o suprapunere, deci dorim să incrementăm i şi să-l păstrăm pe j la începutul şablonului. Definind urmator[0] ca -1 , j va fi setat la -1 în bucla cât timp ; apoi i este incrementat şi j va primi valoarea 0 când bucla pentru este iterată Funcţional, acest algoritm este asemănător cu algoritmul forţei brute , dar este posibil să ruleze mai repede pentru şabloane care se repetă des.
Mai rămâne de calculat tabloul urmator . Programul care face acest lucru este înşelător: este acelaşi program ca cel de mai sus, însă potriveşte şablonul cu el însuşi:
01: INIŢIALIZEAZĂ-URMĂTOR(p)
|
Imediat ce i şi j sunt incrementate, s-a stabilit că primele j caractere ale şablonului se potrivesc cu caracterele din poziţiile p[i - j - 1]..p[i - 1] - ultimele j caractere din primele i caractere ale şablonului. Iar acesta este cel mai mare j cu această proprietate, din moment ce o "posibilă potrivire" a şablonului cu sine însuşi ar fi fost pierdută. De aceea, j este exact valoarea ce trebuie atribuită lui urmator[i] .
Proprietatea 3.2.1: Algoritmul Knuth - Morris - Pratt are complexitatea Θ(M + N).
(nu foloseşte niciodată mai mult de M + N comparaţii)
Această proprietate reiese evident din pseudocod: ori j este incrementat ori este resetat
din tabloul urmator cel mult o dată pentru fiecare i .
Figura următoare arată că acest algoritm foloseşte cu siguranţă mult mai puţine comparaţii decât algoritmul forţei brute, pentru exemplul nostru binar. Cu toate acestea, algoritmul Knuth - Morris - Pratt nu este semnificativ mai rapid decât metoda precedentă în multe aplicaţii practice. Însă, metoda are un avantaj practic major: începe secvenţial prin intrare şi nu se "întoarce" prin ea niciodată. Astfel este convenabilă de utilizat pentru fişiere mari citite de la un dispozitiv extern.
Figura 3.2.1 Algoritmul Knuth - Morris - Pratt aplicat pe un text binar
Prezentăm în continuare implementarea algoritmului în limbajul C++:
01: int urmator[MAX_LEN];
|