Knuth-Morris-Pratt-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 13. lokakuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Knuth-Morris-Pratt- algoritmi (KMP-algoritmi) on tehokas algoritmi , joka etsii alimerkkijonoa merkkijonosta . Algoritmin ajoaika riippuu lineaarisesti syötetyn datan määrästä, eli asymptoottisesti tehokkaampaa algoritmia on mahdotonta kehittää.

Algoritmin ovat kehittäneet D. Knuth ja W. Pratt sekä heistä riippumatta D. Morris [1] . He julkaisivat työnsä tulokset yhdessä vuonna 1977 [2] .

Ongelman selvitys

Annettu kuvio (merkkijono) ja merkkijono . On määritettävä indeksi, josta alkaen kuvio sisältyy merkkijonoon . Jos ei sisällä , palauttaa indeksin, jota ei voida tulkita asemaksi merkkijonossa (esimerkiksi negatiivinen luku). Jos sinun on seurattava jokaista kuvion esiintymistä tekstissä, on järkevää käyttää lisätoimintoa, jota kutsutaan aina, kun kuvio löytyy. $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Idea

Aho-Korasik-algoritmin avulla voit myös etsiä yksittäistä merkkijonoa lineaarisessa ajassa. Mutta tämän algoritmin heikko kohta on äärellinen automaatti, joka on eksplisiittisesti rakennettu O (| neula |·|Σ|) -operaatioihin ja vaatii saman määrän muistia.

Jos haet vain yhtä riviä, jokaisessa tilassa on vain yksi "suora" siirtymä. Sivusiirtymät lasketaan dynaamisesti ilman, että niitä tallennetaan millään tavalla välimuistiin.

jos heinäsuovasta[i] = neula[tila] sitten tila = tila + 1 muuten tila = sivusiirtymä(tila, heinäsuovasta[i])

On helppo nähdä, että Aho-Korasik-algoritmin suffiksilinkit ovat halutun mallin etuliitefunktio .

Algoritmin kuvaus ja käyntiajan arvio

Harkitse merkkijonojen vertailua kohdassa , jossa kuvio on sovitettu tekstinpalaan . Oletetaan, että ensimmäinen epäsuhta tapahtui välillä ja , jossa . Sitten ja . $\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$

Siirrettäessä on täysin mahdollista odottaa, että kuvion etuliite (alkumerkit) suppenee jonkin tekstin päätteen (loppumerkkien) kanssa . Pisimmän etuliitteen pituus, joka on myös jälkiliite, on etuliitefunktion arvo merkkijonosta indeksille . $\displaystyle S$ $\displaystyle P$ $\displaystyle S$ $\displaystyle j$

Tämä johtaa meidät seuraavaan algoritmiin: olkoon etuliitefunktion arvo merkkijonosta indeksi . Vuoron jälkeen voimme jatkaa vertailuja paikan päällä menettämättä mahdollista näytteen sijaintia. Voidaan osoittaa, että taulukko voidaan laskea (poisto) vertailuja varten ennen haun aloittamista. Ja koska merkkijono ajetaan tasan kerran, algoritmin kokonaisajoaika on yhtä suuri kuin , missä on tekstin pituus . $\displaystyle {\rm {{\pi }[j]}}$ $\displaystyle S[0,m-1]$ $\displaystyle j$ $\displaystyle T[i+j]$ $\displaystyle S[{\rm {{\pi }[j]]}}$ $\displaystyle {\rm {\pi ))$ $\näyttötyyli \Theta (m)$ $\displaystyle T$ $\displaystyle \Theta (m+n)$ $n$ $\displaystyle T$

Algoritmin pseudokoodi

funktio KMP(S, T) k ← 0 A ← ø // A - tyhjä joukko π ← Prefix_Function(S) // harkitse kuvion S etuliitefunktiota kun i = 1 - |T| do // |T| - nauhan pituus T kun taas k > 0 ja T[i] ≠ S[k + 1] tekevät k ← π[k] lopettaa hetkeksi jos T[i] = S[k + 1] niin k ← k + 1 loppu Jos jos k = |S| sitten A ← A ⋃ {i - |S| + 1} // tämä on jos otamme huomioon etuliitefunktion alussa A ← A ⋃ {i} // tämä on jos laskemme ensin z-funktion k ← π[k] loppu Jos loppu varten palauttaa A lopputoiminto

Funktio palauttaa — joukon merkkijonon elementtien lukumäärää, jotka päättävät löydetyt esiintymät kohtaan . $\displaystyle A$ $\displaystyle T$ $\displaystyle S$ $\displaystyle T$

Katso myös

Muistiinpanot

↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
↑ Donald Knuth; James H. Morris, Jr, Vaughan Pratt. Nopea kuvioiden sovitus merkkijonoissa // SIAM Journal on Computing : päiväkirja. - 1977. - Voi. 6 , ei. 2 . - s. 323-350 . - doi : 10.1137/0206024 .

Linkit

Knuth-Morris-Pratt algoritmi Algolistissa, kääntäjä Thierry Lecroq, Christian Charras, Knuth-Morris-Pratt algoritmi // Luentosarja Exact String Matching Algorithms, Université de Rouen, 1997

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
muu	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono

Donald Knuth
Julkaisut	Ohjelmoinnin taito " Laulun vaikeusaste " Tietokoneet ja ladonta Konkreettista matematiikkaa Surrealistisia numeroita Tietojenkäsittelytieteilijän asioita Valitut paperisarjat
Ohjelmisto	Τ Ε Χ MIXAL ( SEK MMIX GNU MDK )
Fontit	AMS Euler Tietokone moderni METAFONT
Osaava ohjelmointi	WEB CWEB
Algoritmit	Knuthin algoritmi X Knuth–Bendix-suoritusalgoritmi Knuth-Morris-Pratt-algoritmi Piiskan sekoitus Robinson-Schensted-Knuthin kirjeenvaihto Trabb Pardo–Knuthin algoritmi
muu	Tanssivia linkkejä Knuthin palkintosekki Knut-palkinto mies tai poika testi Neljänneksen kuvitteellinen pohja -miljoonaa Potrzebie-järjestelmä painoja ja mittoja