Algoritmul Knuth-Morris-Pratt

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 13 octombrie 2019; verificările necesită 6 modificări .

Algoritmul Knuth-Morris-Pratt (algoritmul KMP) este un algoritm eficient care caută un subșir într-un șir . Timpul de rulare al algoritmului depinde liniar de cantitatea de date de intrare, adică este imposibil să se dezvolte un algoritm asimptotic mai eficient .

Algoritmul a fost dezvoltat de D. Knuth și W. Pratt și, independent de aceștia, de D. Morris [1] . Ei au publicat în comun rezultatele muncii lor în 1977 [2] .

Enunțul problemei

Dat un model (șir) și un șir . Este necesar să se determine indexul pornind de la care modelul este conținut în șir . Dacă nu este conținut în , returnează un index care nu poate fi interpretat ca o poziție în șir (de exemplu, un număr negativ). Dacă trebuie să urmăriți fiecare apariție a unui model în text, este logic să aveți o funcție suplimentară care este apelată de fiecare dată când este găsit un model. $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Idee

Algoritmul Aho-Korasik vă permite, de asemenea, să căutați un singur șir în timp liniar. Dar punctul slab al acestui algoritm este automatul finit, care este construit în mod explicit în operații O (| ac |·|Σ|) și necesită aceeași cantitate de memorie.

Dacă căutați doar o linie, fiecare stat va avea o singură tranziție „directă”. Tranzițiile laterale vor fi calculate dinamic, fără a le stoca în vreun fel.

dacă carul de fân[i] = ac[starea] atunci stare = stare + 1 altfel stare = tranziție laterală (stare, car de fân[i])

Este ușor de observat că legăturile sufixe ale algoritmului Aho-Korasik sunt o funcție de prefix a șablonului dorit.

Descrierea algoritmului și estimarea timpului de rulare

Luați în considerare o comparație de șiruri la poziție , unde modelul este potrivit cu o bucată de text . Să presupunem că prima nepotrivire a avut loc între și , unde . Apoi și . $\displaystyle i$ $\displaystyle S[0,m-1]$ $\displaystyle \displaystyle T[i,i+m-1]$ $\displaystyle \displaystyle T[i+j]$ $\displaystyle S[j]$ $\displaystyle 1<j<m$ $\displaystyle T[i,i+j-1]=S[0,j-1]=P$ $\displaystyle a=T[i+j]\neq S[j]=b$

La schimbare, este foarte posibil să ne așteptăm ca prefixul (caracterele inițiale) modelului să convergă cu un sufix (caracterele de sfârșit) ale textului . Lungimea celui mai lung prefix, care este și un sufix, este valoarea funcției de prefix din șirul pentru index . $\displaystyle S$ $\displaystyle P$ $\displaystyle S$ $\displaystyle j$

Aceasta ne conduce la următorul algoritm: fie valoarea funcției de prefix din șirul pentru index . Apoi, după tură, putem relua comparațiile de la fața locului și fără a pierde posibila locație a probei. Se poate arăta că tabelul poate fi calculat (amortizat) pentru comparații înainte de a începe căutarea. Și deoarece șirul va fi parcurs exact o dată, timpul total de rulare al algoritmului va fi egal cu , unde este lungimea textului . $\displaystyle {\rm {{\pi }[j]}}$ $\displaystyle S[0,m-1]$ $\displaystyle j$ $\displaystyle T[i+j]$ $\displaystyle S[{\rm {{\pi }[j]]}}$ $\displaystyle {\rm {\pi )}$ $\displaystyle \Theta (m)$ $\displaystyle T$ $\displaystyle \Theta (m+n)$ $n$ $\displaystyle T$

Pseudocod pentru algoritm

funcția KMP(S, T) k ← 0 A ← ø // A - set gol π ← Prefix_Function(S) // luați în considerare funcția de prefix din modelul S pentru i = 1 la |T| face // |T| - lungimea coardei T în timp ce k > 0 și T[i] ≠ S[k + 1] fac k ← π[k] sfârşitul în timp ce dacă T[i] = S[k + 1] atunci k ← k + 1 sfârşitul dacă dacă k = |S| apoi A ← A ⋃ {i - |S| + 1} // asta dacă luăm în considerare funcția de prefix la început A ← A ⋃ {i} // asta dacă am calculat mai întâi funcția z k ← π[k] sfârşitul dacă sfârşitul pentru întoarce A funcția finală

Funcția returnează — setul de numere de elemente ale șirului care termină aparițiile găsite în . $\displaystyle A$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Vezi și

Note

↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmi: construcție și analiză = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
↑ Donald Knuth; James H. Morris, Jr, Vaughan Pratt. Potrivire rapidă a modelelor în șiruri // SIAM Journal on Computing : jurnal. - 1977. - Vol. 6 , nr. 2 . - P. 323-350 . - doi : 10.1137/0206024 .

Link -uri

Algoritmul Knuth-Morris-Pratt pe Algolist, tradus de Thierry Lecroq, Christian Charras, algoritmul Knuth-Morris-Pratt // Seria de cursuri Exact String Matching Algorithms, Université de Rouen, 1997

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun

Donald Knuth
Publicaţii	Arta de a programa „ Scor de dificultate a cântecului ” Calculatoare și compoziție Matematică concretă Numere suprareale Lucruri un informatician Serii de lucrări alese
Software	Τ Ε Χ MIXAL ( MIX MMIX GNU MDK )
Fonturi	AMS Euler Computer modern METAFONT
Programare competenta	WEB CWEB
Algoritmi	Algoritmul X al lui Knuth Algoritmul de completare Knuth–Bendix Algoritmul Knuth-Morris-Pratt Schimbarea biciului Corespondența Robinson–Schensted–Knuth Algoritmul Trabb Pardo–Knuth
Alte	Legături de dans Verificare recompensă Knuth Premiul Knut test bărbat sau băiat Baza cvater-imaginară -yllion Potrzebie sistem de greutăți și măsuri