Knuth-Morris-Pratt algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. október 13-án felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A Knuth-Morris-Pratt algoritmus (KMP-algoritmus) egy hatékony algoritmus , amely egy karakterláncban lévő részkarakterláncot keres . Az algoritmus futási ideje lineárisan függ a bemenő adatok mennyiségétől, vagyis nem lehet aszimptotikusan hatékonyabb algoritmust kidolgozni.

Az algoritmust D. Knuth és W. Pratt , valamint tőlük függetlenül D. Morris dolgozta ki [1] . Munkájuk eredményét 1977 -ben közösen publikálták [2] .

A probléma leírása

Adott egy minta (karakterlánc) és egy karakterlánc . Meg kell határozni azt az indexet, amelytől kezdve a minta szerepel a karakterláncban . Ha nem szerepel benne , akkor olyan indexet ad vissza, amely nem értelmezhető pozícióként a karakterláncban (például negatív szám). Ha nyomon kell követnie egy minta minden előfordulását a szövegben, akkor érdemes egy további függvényt beiktatni, amely minden minta megtalálásakor meghívódik. $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Ötlet

Az Aho-Korasik algoritmus azt is lehetővé teszi, hogy egyetlen karakterláncot keressen lineáris időben. De ennek az algoritmusnak a gyenge pontja a véges automata, amely kifejezetten O (| tű |·|Σ|) műveletekbe van beépítve, és ugyanannyi memóriát igényel.

Ha csak egy sort keres, minden állapotnak csak egy „közvetlen” átmenete lesz. Az oldalsó átmenetek kiszámítása dinamikusan történik, anélkül, hogy bármilyen módon gyorsítótáraznák őket.

ha szénakazal[i] = tű[állapot] akkor állapot = állapot + 1 egyébként állapot = side-transition(állapot, szénakazal[i])

Könnyen belátható, hogy az Aho-Korasik algoritmus utótag hivatkozásai a kívánt sablon előtagfüggvényei.

Az algoritmus leírása és a futási idő becslése

Tekintsünk egy karakterlánc-összehasonlítást a pozícióban , ahol a minta egy szövegrészhez illeszkedik . Tegyük fel, hogy az első eltérés a és között fordult elő , ahol . Aztán és . $\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$

Eltoláskor teljesen elképzelhető, hogy a minta előtagja (kezdőkarakterek) konvergál a szöveg egyes utótagjaihoz (vég karakterei) . A leghosszabb előtag hossza, amely egyben utótag is, az index karakterláncából származó előtag függvény értéke . $\displaystyle S$ $\displaystyle P$ $\displaystyle S$ $\displaystyle j$

Ez a következő algoritmushoz vezet: legyen az index karakterláncából származó előtag függvény értéke . Ezután az eltolódást követően a helyről folytathatjuk az összehasonlítást anélkül , hogy elveszítené a minta lehetséges helyét. Megmutatható, hogy a táblázat a keresés megkezdése előtt összehasonlításra számítható (amortizálható) . És mivel a karakterláncot pontosan egyszer fogjuk bejárni, az algoritmus teljes futási ideje egyenlő lesz , ahol a szöveg hossza . $\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$

Pszeudokód az algoritmushoz

függvény KMP(S,T) k ← 0 A ← ø // A - üres halmaz π ← Prefix_Function(S) // az S mintából származó előtagfüggvény figyelembevétele i = 1-től |T|-ig do // |T| - húrhossz T míg k > 0 és T[i] ≠ S[k + 1] igen k ← π[k] vége közben ha T[i] = S[k + 1] akkor k ← k + 1 vége ha ha k = |S| akkor A ← A ⋃ {i - |S| + 1} // ez akkor van, ha az elején az előtag függvényt vesszük figyelembe A ← A ⋃ {i} // ez az, ha először kiszámítottuk a z-függvényt k ← π[k] vége ha véget ért visszaküldeni A végfunkció

A függvény visszaadja – a karakterlánc azon elemeinek számát, amelyek a talált előfordulásokat -ben fejezik be . $\displaystyle A$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Lásd még

Jegyzetek

↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
↑ Donald Knuth; James H. Morris, Jr., Vaughan Pratt. Gyors mintaillesztés karakterláncokban // SIAM Journal on Computing : folyóirat. - 1977. - 1. évf. 6 , sz. 2 . - P. 323-350 . - doi : 10.1137/0206024 .

Linkek

Knuth-Morris-Pratt algoritmus az Algolistán, fordította Thierry Lecroq, Christian Charras, Knuth-Morris-Pratt algoritmus // Előadássorozat Pontos karakterlánc-illesztési algoritmusok, Université de Rouen, 1997

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Mintaillesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc

Donald Knuth
Publikációk	A programozás művészete " A dal nehézségi pontszáma " Számítógépek és szedés Konkrét matematika Szürreális számok Számítógépes dolgok Válogatott cikksorozatok
Szoftver	Τ Ε Χ MIXÁL ( MIX MMIX GNU MDK )
Betűtípusok	AMS Euler Modern számítógép METAFONT
Hozzáértő programozás	WEB CWEB
Algoritmusok	Knuth X algoritmusa Knuth–Bendix befejezési algoritmus Knuth-Morris-Pratt algoritmus Whip Shuffling Robinson–Schensted–Knuth levelezés Trabb Pardo–Knuth algoritmus
Egyéb	Táncoló linkek Knuth jutalom csekk Knut-díj férfi vagy fiú teszt Negyed képzeletbeli alap - millió Potrzebie súlyok és mértékek rendszere