Knuth-Morris-Pratt-algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 oktober 2019; kontroller kräver 6 redigeringar .

Knuth-Morris-Pratt- algoritmen (KMP-algoritmen) är en effektiv algoritm som söker efter en delsträng i en sträng . Algoritmens körtid beror linjärt på mängden indata, det vill säga det är omöjligt att utveckla en asymptotiskt mer effektiv algoritm.

Algoritmen utvecklades av D. Knuth och W. Pratt och, oberoende av dem, av D. Morris [1] . De publicerade resultaten av sitt arbete gemensamt 1977 [2] .

Förklaring av problemet

Givet ett mönster (sträng) och en sträng . Det krävs att bestämma indexet från vilket mönstret finns i strängen . Om det inte ingår i returnerar du ett index som inte kan tolkas som en position i strängen (till exempel ett negativt tal). Om du behöver hålla reda på varje förekomst av ett mönster i texten, är det vettigt att ha en extra funktion som anropas när ett mönster hittas. $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Idé

Aho-Korasik-algoritmen låter dig också söka efter en enda sträng i linjär tid. Men den svaga punkten med denna algoritm är den finita automaten, som är explicit inbyggd i O (| nål |·|Σ|) operationer och kräver samma mängd minne.

Om du bara söker efter en rad kommer varje stat att ha bara en "direkt" övergång. Sidoövergångar kommer att beräknas dynamiskt, utan att cachelagra dem på något sätt.

om höstack[i] = nål[tillstånd] sedan state = state + 1 annars tillstånd = sidoövergång(tillstånd, höstack[i])

Det är lätt att se att suffixlänkarna i Aho-Korasik-algoritmen är en prefixfunktion för den önskade mallen.

Beskrivning av algoritmen och uppskattning av körtid

Överväg en strängjämförelse vid position , där mönstret matchas mot en textbit . Antag att den första missmatchningen inträffade mellan och , där . Sedan och . $\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$

När du skiftar är det fullt möjligt att förvänta sig att prefixet (starttecken) i mönstret kommer att konvergera med något suffix (sluttecken) i texten . Längden på det längsta prefixet, som också är ett suffix, är värdet på prefixfunktionen från strängen för indexet . $\displaystyle S$ $\displaystyle P$ $\displaystyle S$ $\displaystyle j$

Detta leder oss till följande algoritm: låt vara värdet på prefixfunktionen från strängen för index . Sedan, efter skiftet, kan vi återuppta jämförelser från platsen och utan att förlora den möjliga platsen för provet. Det kan visas att tabellen kan beräknas (amorteras) för jämförelser innan sökningen påbörjas. Och eftersom strängen kommer att korsas exakt en gång, kommer den totala körtiden för algoritmen att vara lika med , där är längden på texten . $\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$

Pseudokod för algoritmen

funktion KMP(S, T) k ← 0 A ← ø // A - tom uppsättning π ← Prefix_Function(S) // betrakta prefixfunktionen från mönstret S för i = 1 till |T| gör // |T| - stränglängd T medan k > 0 och T[i] ≠ S[k + 1] gör det k ← π[k] avsluta medan om T[i] = S[k + 1] då k ← k + 1 sluta om om k = |S| sedan A ← A ⋃ {i - |S| + 1} // detta är om vi betraktade prefixfunktionen i början A ← A ⋃ {i} // detta är om vi först beräknade z-funktionen k ← π[k] sluta om slut för tillbaka A slutfunktion

Funktionen returnerar — uppsättningen av antalet element i strängen som slutar de hittade förekomsterna i . $\displaystyle A$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Se även

Anteckningar

↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 .
↑ Donald Knuth; James H. Morris, Jr, Vaughan Pratt. Snabb mönstermatchning i strängar // SIAM Journal on Computing : journal. - 1977. - Vol. 6 , nr. 2 . - S. 323-350 . - doi : 10.1137/0206024 .

Länkar

Knuth-Morris-Pratt-algoritm på Algolist, översatt av Thierry Lecroq, Christian Charras, Knuth-Morris-Pratt-algoritm // Föreläsningsserie Exact String Matching Algorithms, Université de Rouen, 1997

Strängar
Stränglikhetsmått	Avstånd från Damerau till Loewenstein Levenshtein avstånd Hamming avstånd Jaro-Winkler likhet
Sök efter delsträng	Boyer-Moore algoritm Boyer-Moore-Horspool-algoritm Knuth-Morris-Pratt-algoritm Rabin-Karps algoritm prefixfunktion Z-funktion Algoritm Aho - Korasik
palindromer	palindromträd Manakers algoritm
Sekvensjustering	Needleman-Wunsha algoritm Smith-Waterman algoritm
Suffixstrukturer	Suffix array Suffix automat suffixträd prefixträd
Övrig	analysera Mönstermatchning Största vanliga följden Största gemensamma delsträngen

Donald Knuth
Publikationer	Konsten att programmera " Sångsvårighetsscore " Datorer och sättning Konkret matematik Surrealistiska siffror Saker en datavetare Utvalda pappersserier
programvara	Τ Ε Χ MIXAL ( MIX MMIX GNU MDK )
Teckensnitt	AMS Euler Modern dator METAFONT
Kompetent programmering	WEBB CWEB
Algoritmer	Knuths algoritm X Knuth–Bendix kompletteringsalgoritm Knuth-Morris-Pratt-algoritm Vispa blandar Robinson–Schensted–Knuth korrespondens Trabb Pardo–Knuth-algoritm
Övrig	Dansande länkar Knuth belöningscheck Knut Award man eller pojke test Kvartsimaginär bas -yllion Potrzebie system av vikter och mått