Algoritm Knuth-Morris-Pratt

Algoritmul Knuth-Morris-Pratt (adesea prescurtat ca algoritm KMP ) este un algoritm de potrivire a modelelor pe șiruri , care permite găsirea aparițiilor unui șir (model) $P.$ ${\ displaystyle P}$ $P.$ într-un text $S.$ ${\ displaystyle S}$ $S.$ . Particularitatea sa constă în tratarea prealabilă a șirului de căutat, care conține indicația suficientă pentru a determina poziția din care să continue căutarea în caz de necorespondență. Acest lucru permite algoritmului să nu reexamineze caracterele care au fost verificate anterior și, prin urmare, să limiteze numărul de comparații necesare.

Algoritmul a fost inventat de Knuth și Pratt și independent de JH Morris în 1975 .

Principiul de funcționare

Abordare banală

Pentru a înțelege mai bine logica algoritmului Knuth-Morris-Pratt, este bine să înțelegem abordarea banală a problemei.

Șirul B poate fi găsit în textul A cu următorul algoritm:

Sigur $i=1$ ${\ displaystyle i = 1}$ ${\ displaystyle i = 1}$ ;
Atâta timp cât există poziții de analizat
- Comparați șirul B și textul A literă cu literă începând de la poziție $the$ ${\ displaystyle i}$ $the$ ;
- Dacă șirul a fost găsit, atunci terminați tratamentul și reveniți $the$ ${\ displaystyle i}$ $the$ ca poziție inițială a apariției;
- În caz contrar, remediați $i=i+1$ ${\ displaystyle i = i + 1}$ ${\ displaystyle i = i + 1}$ ;
Finalizați căutarea, nu s-au găsit apariții.

Această procedură poate fi îmbunătățită prin întreruperea comparației la al treilea pas, imediat ce este găsit un caracter diferit, fără a verifica întregul șir.

Această soluție are un dezavantaj: după o comparație nereușită, următoarea comparație va începe de la poziție $i+1$ ${\ displaystyle i + 1}$ ${\ displaystyle i + 1}$ , fără a lua în considerare acele comparații care au fost făcute în pasul anterior, adică poziția $the$ ${\ displaystyle i}$ $the$ . Algoritmul Knuth-Morris-Pratt examinează mai întâi șirul B deducând informații care vă permit să evitați tratarea fiecărui caracter de mai multe ori.

Etape

Prima fază a algoritmului construiește un tabel, care indică o „schimbare de fază” pentru fiecare poziție, adică următoarea poziție în care este posibil să se găsească o potențială apariție a șirului B.
A doua fază efectuează căutarea efectivă, comparând caracterele șirului care trebuie căutat cu cele ale textului. În caz de diferență, utilizați tabelul pentru a cunoaște „defazarea” care trebuie luată în considerare pentru a continua căutarea fără a vă întoarce.

Exemplu

Pentru a prezenta principiul funcționării algoritmului, să luăm în considerare un exemplu particular: șirul $P.$ ${\ displaystyle P}$ $P.$ este ABCDABD în timp ce textul $S.$ ${\ displaystyle S}$ $S.$ este ABC ABCDAB ABCDABCDABDE .

Notare : Pentru a reprezenta șiruri de caractere, în această intrare vom folosi tabele în care indexurile încep de la zero. Prin urmare, C al șirului $P.$ ${\ displaystyle P}$ $P.$ va fi exprimat ca $P[2]$ ${\ displaystyle P [2]}$ ${\ displaystyle P [2]}$ . $m$ ${\ displaystyle m}$ $m$ desemnează poziția, în text $S.$ ${\ displaystyle S}$ $S.$ , la care șirul $P.$ ${\ displaystyle P}$ $P.$ este verificat, e $the$ ${\ displaystyle i}$ $the$ poziția personajului în curs de verificare $P.$ ${\ displaystyle P}$ $P.$ .

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
    0123456

Algoritmul începe prin testarea potrivirii de caractere, unul după altul. Deci, la a patra treaptă, $m=0$ ${\ displaystyle m = 0}$ $m = 0$ Și $i=3$ ${\ displaystyle i = 3}$ ${\ displaystyle i = 3}$ . $S[3]$ ${\ displaystyle S [3]}$ ${\ displaystyle S [3]}$ este un spațiu și $P[3]='D'$ ${\ displaystyle P [3] = 'D'}$ ${\ displaystyle P [3] = 'D'}$ , potrivirea nu este posibilă.

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
    0123456

Decât să o iau de la început $m=1$ ${\ displaystyle m = 1}$ $m = 1$ , Algoritmul ia în considerare faptul că nici un prezent în era $P.$ ${\ displaystyle P}$ $P.$ între pozițiile 0 și 3, cu excepția poziției 0. În consecință, deoarece toate caracterele precedente au fost testate, algoritmul știe că nu există nicio posibilitate de a găsi începutul unei potriviri dacă se verifică din nou. Din acest motiv, algoritmul avansează la următorul caracter în care ar putea exista o posibilă apariție, prin plasare $m=4$ ${\ displaystyle m = 4}$ ${\ displaystyle m = 4}$ Și $i=0$ ${\ displaystyle i = 0}$ ${\ displaystyle i = 0}$ (este important să rețineți că $m$ ${\ displaystyle m}$ $m$ mai întâi devine $3$ ${\ displaystyle 3}$ $3$ cu $i=0$ ${\ displaystyle i = 0}$ ${\ displaystyle i = 0}$ , la fel de $m+i-T[i]=3+0-0=3$ ${\ displaystyle m + iT [i] = 3 + 0-0 = 3}$ ${\ displaystyle m + i-T [i] = 3 + 0-0 = 3}$ , atunci, deoarece nu există corespondență, devine $4$ ${\ displaystyle 4}$ $4$ cu $i=0$ ${\ displaystyle i = 0}$ ${\ displaystyle i = 0}$ , la fel de $T[0]=-1$ ${\ displaystyle T [0] = - 1}$ ${\ displaystyle T [0] = - 1}$ ; consultați algoritmul de mai jos pentru clarificări pe tabel $T.$ ${\ displaystyle T}$ $T.$ ).

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
        0123456

O corespondență aproape completă se obține când cu m = 4 și cu $i=6$ ${\ displaystyle i = 6}$ ${\ displaystyle i = 6}$ , verificarea eșuează.

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
        0123456

Cu toate acestea, chiar înainte de sfârșitul acestui meci parțial, algoritmul a trecut la modelul AB , care ar putea fi începutul unui alt meci. Prin urmare, aceste informații trebuie luate în considerare. Deoarece algoritmul știe deja că primele două caractere se potrivesc celor două caractere care preced poziția curentă, nu este nevoie să le verificăm din nou. Apoi, algoritmul reia tratamentul la caracterul curent, cu $m=8$ ${\ displaystyle m = 8}$ ${\ displaystyle m = 8}$ Și $i=2$ ${\ displaystyle i = 2}$ ${\ displaystyle i = 2}$ .

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
            0123456

Această verificare eșuează imediat ( C nu se potrivește cu spațiul din $S[10]$ ${\ displaystyle S [10]}$ ${\ displaystyle S [10]}$ ). Deoarece șirul nu conține spații (ca în primul pas), algoritmul continuă căutarea de la $m=11$ ${\ displaystyle m = 11}$ ${\ displaystyle m = 11}$ și reinitializarea $i=0$ ${\ displaystyle i = 0}$ ${\ displaystyle i = 0}$ (ca mai sus, de fapt $m$ ${\ displaystyle m}$ $m$ mai întâi devine $10$ ${\ displaystyle 10}$ $10$ cu $i=0$ ${\ displaystyle i = 0}$ ${\ displaystyle i = 0}$ , la fel de $m+i-T[i]=8+2-0=10$ ${\ displaystyle m + iT [i] = 8 + 2-0 = 10}$ ${\ displaystyle m + i-T [i] = 8 + 2-0 = 10}$ , atunci, deoarece nu există corespondență, devine $11$ ${\ displaystyle 11}$ $11$ cu $i=0$ ${\ displaystyle i = 0}$ ${\ displaystyle i = 0}$ , la fel de $T[0]=-1$ ${\ displaystyle T [0] = - 1}$ ${\ displaystyle T [0] = - 1}$ ).

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
               0123456

Din nou, algoritmul găsește o potrivire parțială ABCDAB , dar următorul caracter C nu se potrivește cu caracterul final D al șirului.

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
               0123456

Folosind același raționament ca înainte, algoritmul reia cu $m=15$ ${\ displaystyle m = 15}$ ${\ displaystyle m = 15}$ , pentru a reporni comparația începând de la cele două caractere AB , fixând $i=2$ ${\ displaystyle i = 2}$ ${\ displaystyle i = 2}$ ca nouă locație curentă.

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
                   0123456

De data aceasta, potrivirea dintre șir și text este completă, astfel încât algoritmul returnează poziția 15 (adică $m$ ${\ displaystyle m}$ $m$ ) ca punct de plecare.

 1 2
    01234567890123456789012
m: v
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: ^
                   0123456

Algoritmul de căutare

Exemplul anterior ilustrează intuitiv principiul de funcționare al algoritmului. Adică, presupune prezența unui tabel de „potriviri parțiale” (vezi articolul de mai jos), care indică începutul probabil al următoarei apariții, în cazul în care verificarea apariției curente eșuează. Deocamdată, acest tabel, cu care denotăm $T.$ ${\ displaystyle T}$ $T.$ , poate fi considerat ca o cutie neagră care are următoarea proprietate: dacă avem o potrivire parțială până la $S[m]$ ${\ displaystyle S [m]}$ ${\ displaystyle S [m]}$ , dar asta eșuează atunci când comparăm $S[m+i]$ ${\ displaystyle S [m + i]}$ ${\ displaystyle S [m + i]}$ Și $P[i]$ ${\ displaystyle P [i]}$ ${\ displaystyle P [i]}$ , apoi următoarea apariție parțială va începe de la poziție $m+i-T[i]$ ${\ displaystyle m + iT [i]}$ ${\ displaystyle m + i-T [i]}$ . În special, $T[0]$ ${\ displaystyle T [0]}$ ${\ displaystyle T [0]}$ există și este plasat la $-1$ ${\ displaystyle -1}$ $-1$ . Având acest tabel, algoritmul este relativ simplu:

Sigur $i=m=0$ ${\ displaystyle i = m = 0}$ ${\ displaystyle i = m = 0}$ . să presupunem că $P.$ ${\ displaystyle P}$ $P.$ au o lungime de $n$ ${\ displaystyle n}$ $n$ personaje, ed $S.$ ${\ displaystyle S}$ $S.$ din $L$ ${\ displaystyle l}$ $L$ personaje;
De sine $m$ $+$ $the$ $=$ $L$ {\ displaystyle m + i = l} ${\ displaystyle m + i = l}$ , apoi terminați comparația, nu a fost găsită nicio potrivire. În caz contrar, comparați $P.$ $[$ $the$ $]$ {\ displaystyle P [i]} ${\ displaystyle P [i]}$ Și $S.$ $[$ $m$ $+$ $the$ $]$ {\ displaystyle S [m + i]} ${\ displaystyle S [m + i]}$ ;
- Dacă sunt la fel, atunci remediați $i=i+1$ ${\ displaystyle i = i + 1}$ ${\ displaystyle i = i + 1}$ . De sine $i=n$ ${\ displaystyle i = n}$ ${\ displaystyle i = n}$ , atunci meciul este complet. Încheiați comparația și reveniți $m$ ${\ displaystyle m}$ $m$ ca poziție inițială a corespondenței;
- Dacă sunt diferite, remediați $m=m+i-T[i]$ ${\ displaystyle m = m + iT [i]}$ ${\ displaystyle m = m + i-T [i]}$ , si daca $i>0$ ${\ displaystyle i> 0}$ ${\ displaystyle i> 0}$ , sigur $i=T[i]$ ${\ displaystyle i = T [i]}$ ${\ displaystyle i = T [i]}$ ;
Reluați de la pasul 2.

Această descriere pune în practică algoritmul utilizat în exemplul anterior. Ori de câte ori apare o eroare de verificare, tabelul este consultat pentru a găsi începutul următoarei apariții potențiale și contoare sunt actualizate în consecință. Ca urmare, verificarea caracterului nu se face niciodată înapoi. În special, fiecare caracter este verificat o singură dată (cu excepția cazului în care poate fi eliminat de mai multe ori în urma unei nepotriviri, a se vedea mai jos eficiența algoritmului).

Exemplu de cod pentru algoritmul de căutare

Următorul cod C este o implementare a acestui algoritm.

 int kmp_research ( char * P, char * S)
{
    extern int T [];
    int m = 0;
    int i = 0;
    
    while (S [m + i]! = '\ 0' && P [i]! = '\ 0') {
        if (S [m + i] == P [i]) {
            ++ i;
        } altceva {
            m + = i - T [i];
            if (i> 0) i = T [i];
        }
    }
    
    if (P [i] == '\ 0') {
        retur m;
    } altceva {
        returnează m + i;
    }
}

Eficiența algoritmului de căutare

Presupunând existența unui tabel $T.$ ${\ displaystyle T}$ $T.$ , faza de „cercetare” a algoritmului Knuth-Morris-Pratt este de complexitate O $(l)$ ${\ displaystyle (l)}$ ${\ displaystyle (l)}$ , unde este $L$ ${\ displaystyle l}$ $L$ desemnează lungimea $S.$ ${\ displaystyle S}$ $S.$ . Dacă excludem tratamentul fix suplimentar, indus de începutul și sfârșitul funcției, toate tratamentele se efectuează în ciclul principal. Pentru a calcula o limită a numărului de iterații, este necesară o primă observație cu privire la natura $T.$ ${\ displaystyle T}$ $T.$ . Prin definiție, este construit astfel încât, dacă un meci parțial începe de la $S[m]$ ${\ displaystyle S [m]}$ ${\ displaystyle S [m]}$ eșuează la comparare $S[m+i]$ ${\ displaystyle S [m + i]}$ ${\ displaystyle S [m + i]}$ Și $P[i]$ ${\ displaystyle P [i]}$ ${\ displaystyle P [i]}$ , următorul potențial meci nu începe înainte $S[m+(i-T[i])]$ ${\ displaystyle S [m + (iT [i])]}$ ${\ displaystyle S [m + (i-T [i])]}$ . În special, următorul meci potențial trebuie localizat cu o poziție mai târziu $m$ ${\ displaystyle m}$ $m$ , astfel încât $T[i]<i$ ${\ displaystyle T [i] <i}$ ${\ displaystyle T [i] <i}$ .

Pornind de la această ipoteză, se arată că ciclul este realizat la maxim $2l$ ${\ displaystyle 2l}$ ${\ displaystyle 2l}$ ori. La fiecare iterație, una dintre cele două ramuri ale instrucțiunii if este executată.

prima ramură crește invariabil $the$ ${\ displaystyle i}$ $the$ și nu modifică $m$ ${\ displaystyle m}$ $m$ , astfel încât indexul $m+i$ ${\ displaystyle m + i}$ ${\ displaystyle m + i}$ a caracterelor comparate în șir $S.$ ${\ displaystyle S}$ $S.$ este mărită.
a doua ramură crește $m$ ${\ displaystyle m}$ $m$ din $i-T[i]$ ${\ displaystyle iT [i]}$ ${\ displaystyle i-T [i]}$ . Fiind $i-T[i]$ ${\ displaystyle iT [i]}$ ${\ displaystyle i-T [i]}$ întotdeauna pozitiv, așa cum am văzut anterior, deducem că indicele $m$ ${\ displaystyle m}$ $m$ de la începutul posibilului meci este mărită.

Ciclul se încheie dacă $S[m+i]='\backslash 0'$ ${\ displaystyle S [m + i] = '\ backslash 0'}$ ${\ displaystyle S [m + i] = '\ backslash 0'}$ , ceea ce înseamnă, având în vedere convenția C că caracterul NUL indică sfârșitul unui șir, că $m+i=l$ ${\ displaystyle m + i = l}$ ${\ displaystyle m + i = l}$ . În consecință, fiecare ramură a instrucțiunii if poate fi executată cel mult $L$ ${\ displaystyle l}$ $L$ ori, deoarece cele două ramuri cresc respectiv sau $m+i$ ${\ displaystyle m + i}$ ${\ displaystyle m + i}$ sau $m$ ${\ displaystyle m}$ $m$ , cu $m\leq m+i$ ${\ displaystyle m \ leq m + i}$ ${\ displaystyle m \ leq m + i}$ ; astfel încât dacă $m=l$ ${\ displaystyle m = l}$ ${\ displaystyle m = l}$ , asa de $m+i\geq l$ ${\ displaystyle m + i \ geq l}$ ${\ displaystyle m + i \ geq l}$ , și fiind creșterea la fiecare ciclu a cel puțin o unitate, $m+i=l$ ${\ displaystyle m + i = l}$ ${\ displaystyle m + i = l}$ este neapărat adevărat în trecut.

Prin urmare, ciclul se desfășoară la maximum $2l$ ${\ displaystyle 2l}$ ${\ displaystyle 2l}$ ori, deci complexitatea de calcul este $O(l)$ ${\ displaystyle O (l)}$ ${\ displaystyle O (l)}$ .

Tabelul „corespondențelor parțiale”

Scopul acestui tabel este de a permite algoritmului să nu verifice fiecare caracter al textului de mai multe ori. Observația cheie pentru a stabili natura liniară a căutării, care permite acest algoritm să funcționeze, este că după verificarea unei bucăți de text care conține o "porțiune de pornire" a șirului, este posibil să se determine în ce poziții pot apărea următoarele posibile apariții începe.și din ele continuă comparația începând de la poziția actuală a textului. Cu alte cuvinte, motivele (sub-porțiunile șirului) sunt „preidentificate” în șir și se creează o listă care indică toate pozițiile posibile din care să continue, sărind cel mai mare număr de caractere inutile, fără a sacrifica orice potrivire potențială.

Pentru fiecare poziție din șir, este necesar să se determine lungimea maximă a motivului de pornire, care se termină în poziția curentă, dar care nu permite o potrivire completă (și, prin urmare, probabil va eșua). Prin urmare, $T[i]$ ${\ displaystyle T [i]}$ ${\ displaystyle T [i]}$ indică exact lungimea maximă a motivului de început care se termină cu $P[i]$ ${\ displaystyle P [i]}$ ${\ displaystyle P [i]}$ . Prin convenție, șirul nul are lungimea zero. Deoarece verificarea inițială a șirului este un caz particular (deoarece nu există nicio posibilitate de backtracking ), apare $T[0]=-1$ ${\ displaystyle T [0] = - 1}$ ${\ displaystyle T [0] = - 1}$ , după cum sa discutat mai sus.

Descrierea pseudocodului

Principiul este cel al cercetării în general: o mare parte a muncii a fost deja realizată pentru a ajunge la poziția actuală și, prin urmare, a rămas puțin. Folosim partea deja populată a tabelului $T.$ ${\ displaystyle T}$ $T.$ pentru a găsi potențiale șiruri de caractere, similar algoritmului de căutare. Singura complicație minoră este că logica care este corectă mai târziu, din păcate, returnează șiruri incorecte la început. Această problemă necesită un anumit cod de inițializare.

 algoritm kmp_table :
    intrare :
        o serie de caractere, W (cuvântul care trebuie analizat)
        o serie de numere întregi, T (tabelul care trebuie completat)
    ieșire :
        nimic (dar în timpul operației populăm tabelul)

    definiți variabilele :
        un număr întreg, pos ← 2 (poziția curentă a calculului lui T)
        un întreg, cnd ← 0 (indexul începând de la zero în W al următorului caracter al șirului candidat)

    (primele valori sunt fixe, dar diferite de ceea ce ar putea sugera algoritmul)
    Fie T [0] ← -1, T [1] ← 0

    în timp ce poziția este mai mică decât lungimea lui W, faceți:
        (primul caz: șirul continuu)
        în cazul în care W [pos - 1] = W [CND], lăsați T [pos] ← + 1 cnd, pos pos ← + 1, ← cnd + 1 CND

        (al doilea caz: nu, dar nu ne putem întoarce)
        altfel , dacă cnd> 0, să cnd ← T [cnd]

        (al treilea caz: rămânem fără candidați. Notă cnd = 0)
        altfel , lasă T [pos] ← 0, pos ← pos + 1

Eficiența construcției mesei

Complexitatea algoritmului tabelului este O(n) , unde n este lungimea lui W În afară de inițializare, toate lucrările se realizează în bucla while , arătând doar că bucla execută O(n) ori, ceea ce ar trebui făcut prin examinarea simultană a valorilor pos și pos - cnd .

În prima ramură, pos - cnd rămâne constant, deoarece pos și cnd sunt incrementate împreună, dar, desigur, pos crește continuu.
În cel de-al doilea caz, cnd este înlocuit cu T[cnd] , pe care l-am văzut a fi strict mai mic decât cnd , astfel încât pos - cnd este crescut.
În al treilea caz, pos este crescut, în timp ce cnd rămâne stabil și, astfel, pos și pos - cnd crește.

Deoarece pos ≥ pos - cnd , aceasta înseamnă că la fiecare ciclu crește ambele pos și o cantitate mai mică decât pos; de aceea, deoarece algoritmul se termină când se atinge pos = n , acesta trebuie să se termine după cel mult 2n iterații, deoarece pos - cnd începe de la 1 . Deci complexitatea algoritmului tabelului este O(n) .

Eficiența algoritmului KMP

Deoarece cele două părți ale algoritmului au, respectiv, complexități O(k) și O(n) , complexitatea totală este O(n + k) .

Bibliografie

(EN) Donald Knuth , James H. Morris, Jr. și Vaughan Pratt . Potrivire rapidă a modelelor în șiruri . SIAM Journal on Computing, 6 (2): 323-350. 1977. Citații . Publicație originală
( EN ) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein .Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capitolul 32.4: Algoritmul Knuth-Morris-Pratt, pp. 923-931.

Elemente conexe

Algoritmul Boyer-Moore .

linkuri externe

( EN ) O explicație a algoritmului .
( EN ) Un exemplu al algoritmului Knuth-Morris-Pratt , pe site-ul web al lui J Strother Moore , co-inventator al algoritmului Boyer-Moore .

Portal IT : accesați intrările Wikipedia care se ocupă cu IT