Knuth-Morris-Pratt algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. oktober 2019; checks kræver 6 redigeringer .

Knuth-Morris-Pratt- algoritmen (KMP-algoritmen) er en effektiv algoritme , der søger efter en understreng i en streng . Algoritmens køretid afhænger lineært af mængden af inputdata, det vil sige, at det er umuligt at udvikle en asymptotisk mere effektiv algoritme.

Algoritmen er udviklet af D. Knuth og W. Pratt og, uafhængigt af dem, af D. Morris [1] . De offentliggjorde resultaterne af deres arbejde i fællesskab i 1977 [2] .

Udtalelse af problemet

Givet et mønster (streng) og en snor . Det er nødvendigt at bestemme det indeks, der starter, hvorfra mønsteret er indeholdt i strengen . Hvis det ikke er indeholdt i , skal du returnere et indeks, der ikke kan fortolkes som en position i strengen (f.eks. et negativt tal). Hvis du har brug for at holde styr på hver forekomst af et mønster i teksten, giver det mening at have en ekstra funktion, der kaldes, hver gang et mønster er fundet. $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Idé

Aho-Korasik-algoritmen giver dig også mulighed for at søge efter en enkelt streng i lineær tid. Men det svage punkt ved denne algoritme er den endelige automat, som er eksplicit bygget i O (| nål |·|Σ|) operationer og kræver den samme mængde hukommelse.

Hvis du kun søger efter én linje, vil hver tilstand kun have én "direkte" overgang. Sideovergange vil blive beregnet dynamisk uden at cache dem på nogen måde.

hvis høstak[i] = nål[tilstand] så stat = tilstand + 1 ellers tilstand = sideovergang(tilstand, høstak[i])

Det er let at se, at suffikslinkene i Aho-Korasik-algoritmen er en præfiksfunktion af den ønskede skabelon.

Beskrivelse af algoritmen og estimering af køretid

Overvej en strengsammenligning ved position , hvor mønsteret matches mod et stykke tekst . Antag, at den første uoverensstemmelse opstod mellem og , hvor . Så og . $\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 skifter, er det meget muligt at forvente, at præfikset (starttegn) i mønsteret vil konvergere med et eller andet suffiks (sluttegn) i teksten . Længden af det længste præfiks, som også er et suffiks, er værdien af præfiksfunktionen fra strengen for indekset . $\displaystyle S$ $\displaystyle P$ $\displaystyle S$ $\displaystyle j$

Dette fører os til følgende algoritme: lad være værdien af præfiksfunktionen fra strengen for indeks . Derefter, efter skiftet, kan vi genoptage sammenligninger fra stedet og uden at miste den mulige placering af prøven. Det kan påvises, at tabellen kan beregnes (amortiseres) til sammenligninger, inden søgningen påbegyndes. Og da strengen vil blive krydset præcis én gang, vil den samlede køretid for algoritmen være lig med , hvor er længden af teksten . $\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$

Pseudokode for algoritmen

funktion KMP(S, T) k ← 0 A ← ø // A - tomt sæt π ← Prefix_Function(S) // overvej præfiksfunktion fra mønster S for i = 1 til |T| gør // |T| - strenglængde T mens k > 0 og T[i] ≠ S[k + 1] gør k ← π[k] slutte mens hvis T[i] = S[k + 1] så k ← k + 1 Afslut Hvis hvis k = |S| derefter A ← A ⋃ {i - |S| + 1} // dette er, hvis vi betragtede præfiksfunktionen i begyndelsen A ← A ⋃ {i} // dette er, hvis vi først beregnede z-funktionen k ← π[k] Afslut Hvis ende for retur A afslutte funktion

Funktionen returnerer — mængden af numre af elementer i strengen , der ender de fundne forekomster i . $\displaystyle A$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Se også

Noter

↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
↑ Donald Knuth; James H. Morris, Jr., Vaughan Pratt. Hurtig mønstermatchning i strenge // SIAM Journal on Computing : journal. - 1977. - Bd. 6 , nr. 2 . - S. 323-350 . - doi : 10.1137/0206024 .

Links

Knuth-Morris-Pratt algoritme på Algolist, oversat af Thierry Lecroq, Christian Charras, Knuth-Morris-Pratt algoritme // Forelæsningsrække Exact String Matching Algorithms, Université de Rouen, 1997

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng

Donald Knuth
Publikationer	Kunsten at programmere " Sangsværhedsscore " Computere og sætning Konkret matematik Surrealistiske tal Ting en datamatiker Udvalgte papirserier
Software	Τ Ε Χ MIXAL ( MIX MMIX GNU MDK )
Skrifttyper	AMS Euler Moderne computer METAFONT
Kompetent programmering	WEB CWEB
Algoritmer	Knuths algoritme X Knuth-Bendix færdiggørelsesalgoritme Knuth-Morris-Pratt algoritme Pisk Blanding Robinson–Schensted–Knuth korrespondance Trabb Pardo-Knuth algoritme
Andet	Dansende links Knuth belønning check Knut prisen mand eller dreng test Kvart-imaginær base -yllion Potrzebie system af vægte og mål