logo

L'algoritme Knuth-Morris-Pratt (KMP).

Knuth-Morris i Pratt introdueixen un algorisme de temps lineal per al problema de concordança de cadenes. S'aconsegueix un temps de concordança de O (n) evitant la comparació amb un element de 'S' que s'ha implicat prèviament en comparació amb algun element del patró 'p' que s'ha de fer coincidir. és a dir, el retrocés a la cadena 'S' no es produeix mai

Components de l'algoritme KMP:

1. La funció de prefix (Π): La funció de prefix, Π per a un patró, encapsula el coneixement sobre com el patró coincideix amb el canvi de si mateix. Aquesta informació es pot utilitzar per evitar un canvi inútil del patró 'p.' En altres paraules, això permet evitar el retrocés de la cadena 'S'.

2. Les coincidències KMP: Amb la cadena 'S', el patró 'p' i la funció de prefix 'Π' com a entrades, trobeu l'ocurrència de 'p' a 'S' i retorna el nombre de torns de 'p' després dels quals es troben les ocurrències.

La funció de prefix (Π)

El pseudocodi següent calcula la funció de prefix, Π:

 <strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m &#x2190;length [P] //&apos;p&apos; pattern to be matched 2. &#x3A0; [1] &#x2190; 0 3. k &#x2190; 0 4. for q &#x2190; 2 to m 5. do while k &gt; 0 and P [k + 1] &#x2260; P [q] 6. do k &#x2190; &#x3A0; [k] 7. If P [k + 1] = P [q] 8. then k&#x2190; k + 1 9. &#x3A0; [q] &#x2190; k 10. Return &#x3A0; 

Anàlisi del temps de funcionament:

Al pseudocodi anterior per calcular la funció de prefix, el bucle for del pas 4 al pas 10 s'executa 'm' vegades. El pas 1 al pas 3 pren un temps constant. Per tant, el temps d'execució de la funció de prefix de càlcul és O (m).

Exemple: Calculeu Π per al patró 'p' següent:

exemples d'autòmats dfa
Algorisme Knuth-Morris-Pratt

Solució:

 Initially: m = length [p] = 7 &#x3A0; [1] = 0 k = 0 
Algorisme Knuth-Morris-Pratt
Algorisme Knuth-Morris-Pratt

Després d'iterar 6 vegades, el càlcul de la funció de prefix s'ha completat:

Algorisme Knuth-Morris-Pratt

El KMP coincideix amb:

El KMP Matcher amb el patró 'p', la cadena 'S' i la funció de prefix 'Π' com a entrada, troba una coincidència de p a S. Seguint el pseudocodi calcula el component coincident de l'algorisme KMP:

 <strong>KMP-MATCHER (T, P)</strong> 1. n &#x2190; length [T] 2. m &#x2190; length [P] 3. &#x3A0;&#x2190; COMPUTE-PREFIX-FUNCTION (P) 4. q &#x2190; 0 // numbers of characters matched 5. for i &#x2190; 1 to n // scan S from left to right 6. do while q &gt; 0 and P [q + 1] &#x2260; T [i] 7. do q &#x2190; &#x3A0; [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q &#x2190; q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print &apos;Pattern occurs with shift&apos; i - m 12. q &#x2190; &#x3A0; [q] // look for the next match 

Anàlisi del temps de funcionament:

El bucle for que comença al pas 5 s'executa 'n' vegades, és a dir, sempre que la longitud de la cadena 'S'. Com que el pas 1 al pas 4 pren temps constants, el temps d'execució està dominat per aquest per al bucle. Així, el temps d'execució de la funció de concordança és O (n).

Exemple: Donada una cadena 'T' i un patró 'P' de la següent manera:

L'algoritme Knuth-Morris-Pratt

Executem l'algoritme KMP per trobar si 'P' apareix a 'T'.

Per a 'p' la funció de prefix, ? s'ha calculat anteriorment i és el següent:

L'algoritme Knuth-Morris-Pratt

Solució:

 Initially: n = size of T = 15 m = size of P = 7 
Algorisme Knuth-Morris-Pratt
Algorisme Knuth-Morris-Pratt
Algorisme Knuth-Morris-Pratt
Algorisme Knuth-Morris-Pratt
Algorisme Knuth-Morris-Pratt
Algorisme Knuth-Morris-Pratt

S'ha trobat que el patró 'P' té complexitat en una cadena 'T'. El nombre total de torns que s'han fet per trobar la coincidència és i-m = 13 - 7 = 6 torns.