Algoritmo Knuth-Morris-Pratt

El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella se precalcula una tabla de valores), para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca.

El algoritmo originalmente fue elaborado por Donald Knuth y Vaughan Pratt y de modo independiente por James H. Morris en 1977, pero lo publicaron juntos los tres.

Descripción del algoritmo KMP

El algoritmo KMP trata de localizar la posición de comienzo de una cadena dentro de otra. Antes que nada con la cadena a localizar se precalcula una tabla de saltos (conocida como tabla de fallos) que después al examinar las cadenas se utiliza para hacer saltos cuando se localiza un fallo.

Supongamos una tabla 'F' ya precalculada, y supongamos que la cadena a buscar esté contenida en el arreglo 'P()', y la cadena donde buscamos esté contenida en un array 'T()'. Entonces ambas cadenas comienzan a compararse usando un puntero de avance para la cadena a buscar, si ocurre un fallo en vez de volver a la posición siguiente a la primera coincidencia, se salta hacia donde sobre la tabla, indica el puntero actual de avance de la tabla. El array 'T' utiliza un puntero de avance absoluto que considera donde se compara el primer carácter de ambas cadenas, y utiliza como un puntero relativo (sumado al absoluto) el que utiliza para su recorrido el array 'P'. Se dan 2 situaciones:

Mientras existan coincidencias el puntero de avance de 'P', se va incrementando y si alcanza el final se devuelve la posición actual del puntero del array 'T'

Si se da un fallo, el puntero de avance de 'T' se actualiza hasta, con la suma actual del puntero de 'P' + el valor de la tabla 'F' apuntado por el mismo que 'P'. A continuación se actualiza el puntero de 'P', bajo una de 2 circunstancias; Si el valor de 'F' es mayor que -1 el puntero de 'P', toma el valor que indica la tabla de salto 'F', en caso contrario vuelve a recomenzar su valor en 0.

Pseudocódigo del algoritmo

En el pseudocódigo no se incluye la verificación de las cadenas vacías.

 Algoritmo BúsquedaKMP:
 Entrada:
   un array de caracteres, T (el texto donde se busca)
   un array de caracteres, P (la palabra/s que se busca)
 Salida:
   un entero que expresa la posición en T en la cual se encontró P. 
      (nota: opcionalmente puede convenir devolver un entero con signo).

 Definición de variables:
   un entero, k ← 0 (puntero de examen en T)
   un entero, i ← 0 (la posición del carácter actual en P, y avance relativo respecto de k, para T)
   un array de enteros, F (la tabla de fallo, calculada a continuación, o en otra parte)
 Si tamaño de T es mayor o igual que tamaño de P entonces
   Precalcular TablaKMP(P,F)
   Mientras k + i es menor que la longitud de T, hacer
     Si P[i] = T[k + i] entonces
       Si i es igual a la longitud de P - 1 entonces
         Devolver k
       Fin si
       Asignar i ← i + 1
     Si no entonces
       Asignar k ← k + i - F[i]
       Si i es mayor que 0 entonces
         Asignar i ← F[i]
       Fin si
     Fin si
   Repetir
 Fin si
            
 (si se alcanza este punto, se buscó en todas las T sin éxito)
 Devolver longitud de T, ó si se usa una variable con signo, devolver  -1

Descripción de la tabla adicional (conocida como 'función de fallo')

El objetivo de la tabla (precalculada) de fallo 'F' es no permitir que cada carácter del array 'T()' sea examinado más de 1 vez. El método clave para lograr esto, consiste en haber comprobado algún trozo de la cadena donde se busca con algún trozo de la cadena que se busca, lo que nos proporciona en qué sitios potenciales puede existir una nueva coincidencia, sobre el sector analizado que indica fallo.

Dicho de otro modo, partiendo del texto a buscar, elaboramos una lista con todas las posiciones, de salto atrás que señalen cuanto se retrocede desde la posición actual del texto a buscar. Por ejemplo si el texto a buscar es 'esconderse' y estamos examinando un texto como 'se esconden tras la mesa', cuando llegamos a la 2ª 'n' de 'esconden' (posición 7 en el texto a buscar es una 'r'), falla, la pregunta lógica sería ¿ dónde se encuentra de nuevo (si existe) la primera letra en el texto 'esconderse'(antes del fallo), y hasta donde logra repetirse ?. La respuesta a esta pregunta será el punto de salto, en el caso propuesto ('esconderse'). Dicho punto se encuentra en la posición 6 (antes de la 'r'), luego para la tabla en la siguiente posición debería de haber un 1.

Por tanto esta tabla se confecciona con la distancia que existe desde un punto en la palabra a la última ocurrencia (de la 0ª letra de la palabra) distinta de la primera vez que aparece,y mientras sigan coincidiendo, se marca la distancia, cuando haya una ruptura de coincidencia se marca 0 o un valor previo ya calculado anteriormente, y así sucesivamente hasta terminar con el texto.

La tabla tiene sus 2 primeros valores fijados, de modo que la función de fallo empieza siempre examinando el 3 carácter del texto. La razón por la que dichos valores están fijados es obvia: si para el 2º carácter se marcara 1, nunca se lograría un salto, pues siempre retornaría a dicho punto. En cuanto al primero, por necesidad se marca -1, pues de ese modo le es imposible regresar más atrás, sino siempre adelante.

Ejemplos de texto y su tabla de fallo

Primero un sencillo ejemplo donde sólo hay una ocurrencia.

'01234567
'TANGENTE' 
-10000001'  Se busca la 1ª 'T', que aparece tras la de comienzo, ocurre en la posición 6, 
la siguiente letra a la 'T' hallada, la 'e' está a una distancia de 1 de esta aparición de 'T',  
por ello se marca con un 1.

Ahora un ejemplo más interesante

'0123456789012
'MAREMAGNUM EL'
-1000012000100 Hay 2 ocurrencias con 'MA' y más adelante otra con 'M'

Y terminamos con un ejemplo de 4 coincidencias, 2 de 3 letras consecutivas 'PAR' y la 3ª de 6 letras 'PARTIC'. Se ha coloreado los tramos coincidentes, para más claridad.

 0 10 20 30 40  <-Posiciones de los caracteres en tramos de 10.
'01234567890123456789012345678901234567890'
 -      +            +          +           <- Marcando posiciones donde, aparece la 1ª letra.
'PARTICIPARIA CON MI PARACAIDAS PARTICULAR' <- Texto a calcular su tabla de fallos.
-100000001230000000000 
La 'P' es la 0ª letra, luego en la posición 7 vuelve a aparecer, por tanto en la 8ª posición, 
se marca un '1' (la distancia a la 'P' hallada, mientras continúe coincidiendo), luego coinciden
las 2 siguientes letras, entonces se marca la distancia, luego falla, hay una 'A' y se esperaba
una 'T', entonces se marca '0' hasta que vuelva a aparecer de nuevo la 1ª letra del texto 'P'.

'PARTICIPARIA CON MI PARACAIDAS PARTICULAR'  
                      12300000000 
Lo cual sucede otra vez en la posición 20, por tanto en la 21, se marca '1', de nuevo coinciden
tras la 'P', la 'A' y la 'R', pero la 24ª falla, es una 'C', no una 'T', de nuevo se marca 
con '0', hasta que se dé otra ocurrencia del comienzo del texto.

'PARTICIPARIA CON MI PARACAIDAS PARTICULAR'  
                                 123456 
En la posición 31ª, vuelve a aparecer una 'P', se marca en la siguiente la distancia '1', 
coincide también la siguiente , marcamos '2' y así correlativamente mientras exista
correspondencia entre la examinada y la correspondiente del inicio... en total se encuentra
coincidencia entre ambos tramos en 'PARTIC', de ahí que marquemos '0123456' y volvemos 
a marcar '0' otra vez ante el fallo.
    
Finalmente tenemos nuestra tabla de fallos:
'PARTICIPARIA CON MI PARACAIDAS PARTICULAR'  
-10000000123000000000012300000000123456000

Pseudocódigo de la tabla (función de fallo)

 Algoritmo TablaKMP:
    Entrada:
        un array de caracteres, P (la palabra/texto que va a ser analizada)
        un array de enteros, F (la tabla de fallos a rellenar) debe tener el mismo tamaño que P.
    Salida:
        nada, no devuelve valores( pero por referencia, devuelve la tabla rellenada)

    variables que se usan:
        un entero, pos ← 2 (la posición actual donde se está calculando F)
        un entero, cnd ← 0 (el índice en P del siguiente carácter del actual candidato en la
          subcadena)

    (algunos valores se fijan con determinado valor, y por tanto no están sujetos a lo que cabría
       esperar del algoritmo, esto se explica más arriba, en el apartado de la descripción)
    asignar F[0] ← -1, F[1] ← 0

    Hacer mientras pos sea menor o igual que el tamaño de P:
           (caso 1º: siguiente candidato coincidente en la cadena)
        Si P[pos - 1] = P[cnd] entonces
          Asignar cnd ← cnd + 1, F[pos] ← cnd, pos ← pos + 1
           (caso 2º: cuando empieza a fallar las coincidencias consecutivas, entonces 
              asignamos un valor ya conocido la 1ª vez)
        Pero si cnd > 0 entonces
          Asignar cnd ← F[cnd]
           (caso 3º: no se halló candidatos coincidentes (otra vez))
        Y si no entonces
          Asignar F[pos] ← 0, pos ← pos + 1
        Fin si
    Repetir

Eficiencia del algoritmo

Debido a que el algoritmo precisa de 2 partes donde se analiza una cadena en cada parte, la complejidad resultante es O(k) y O(n), cuya suma resulta ser O(n + k).

La capacidad del algoritmo queda patente al apreciar como logra saltar varios caracteres a la vez cuando hay un fallo. Esto se aprecia mejor, mirando la tabla F, cuantos más ceros existan tanto más grande es el salto resultante. De modo que puede deducirse caso peores y óptimos. Los casos óptimos se denotan porque son todos ceros, o lo que es lo mismo, no se repiten caracteres desde el principio. Ejemplo P ="ABCDEFG". El peor caso se da cuando la cadena se compone de 1 único carácter, por ejemplo: P= "AAAAAAAA", obsérvese la tabla F para dicho texto:

`i`	0	1	2	3	4	5	6	7
`P[i]`	A	A	A	A	A	A	A	A
`F[i]`	-1	0	1	2	3	4	5	6

Ejemplo

Una forma de entender correctamente el funcionamiento del algoritmo es seguir paso a paso un ejemplo reseñando en cada punto lo que hace o puede hacer el algoritmo en una situación dada.

Se considera tanto en los ejemplos como en el pseudocódigo que los array de caracteres se basan en índice 0.

Sean 2 cadenas, que se entregan como arrays de caracteres a la función, donde T es el array de caracteres donde queremos buscar y P el array que se quiere hallar en T, usando k como puntero absoluto para los caracteres de T e i como puntero para los caracteres de P. Se usa también, una tabla (matriz) precalculada de la palabra a buscar F. A continuación se ve una figura que representan las variables consideradas para el ejemplo.

k: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: 0123456
F:-1000012

Se muestra la tabla F, precalculada para el ejemplo.

`i`	0	1	2	3	4	5	6
`P[i]`	A	B	C	D	A	B	D
`F[i]`	-1	0	0	0	0	1	2

k: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: 0123456
F:-1000012

Comienza el cálculo, los punteros 'k' e 'i' inicialmente valen 0. Si P(i) = T(k + i), se evalúa a continuación si i = tamaño de P en cuyo caso se habría encontrado la posición de la cadena. En caso contrario, se incrementa 'i'. Esto sucede 3 veces, hasta que en la 4ª ocasión, en P(3) tenemos 'D' y en T(k + i) tenemos ' '(un espacio), momento en que actualizamos 'k', k = k + i - F(i) (k = 3). A continuación verificamos si F(i) > -1 (F(3) vale 0), como se da el caso hacemos para i = F(i). Es decir saltamos a la posición sobre el array 'P' que señala 'F(i)', que en este caso es 0, por tanto al principio del array 'P', pero ahora el puntero del array 'T' está en 3 (k = 3).

Por tanto en la siguiente figura avanzamos hasta la posición absoluta de T actual, 3.

k: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P:    ABCDABD
i:    0123456
F:   -1000012

Volvemos al principio del bucle (cada vez que se vuelve a este punto se comprueba si 'k' alcanzó el tamaño de 'T' y de nuevo verificamos si P(i) = T(k + i). Vemos que en el punto actual en 'P' hay un espacio, por lo que, nuevamente se actualiza 'k', k = k + i - F(i) (k = 4), porque 'F(i) = -1'. Ahora entonces se hace i = 0 (aunque antes también era 0).

Como volvemos al inicio del bucle (se da por comprobado si el bucle finaliza), actualizamos la figura con el puntero en 'k', (k = 4)

k: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P:     ABCDABD
i:     0123456
F:    -1000012

Ahora vemos que varias veces se cumple que P(i) = T(k + i), pero no tantas que se alcance el tamaño de 'P', y con cada coincidencia 'i' se ha incrementado, por lo que ahora 'i=6', pero se ha incrementado justo después de verificar si i = tamaño P luego devolver k (si no habríamos alcanzado la solución). Al analizar de nuevo al inicio del bucle la posición 6, falla ya que 'P(6) = D' y 'T(4 + 6) =' . en este punto toca actualizar 'k', y hacemos k = k + i - F(i) (k = 4 + 6 - F(6), en este punto F(6) vale 2, por lo que finalmente damos un salto 'k = 4 + 6 - 2 = 8'. Y actualizamos 'i', si F(6) > -1 luego i = F(i), es decir no solo acanzamos el puntero de 'T', sino que además avanzamos el puntero de 'P' a 2, porque precisamente en la posición 8, hay una coincidencia 'AB' tal como comienza la cadena del array 'w'. es justo e este punto donde hemos visto el salto y la eficacia de la tabla F.

Actualizamos la figura, damos por verificado la comprobación del inicio del bucle.

k: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P:         ABCDABD
i:         0123456
F:        -1000012

Una nueva vez volvemos comprobar si P(i) = T(k + i) (P(2) = T(8+2)), es decir 'C' = ' '), como falla toca actualizar el puntero de 'T'. k = k + i - F(i) (k=8 + 2 - 0 = 10), y actualizamos 'i', (si F(i) > -1 luego i = F(i)) 'i = 0'.

Actualizamos a la siguiente figura (como cada vez que se actualiza 'k' el puntero absoluto de 'T').

k: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P:           ABCDABD
i:           0123456
F:          -1000012

Con la siguiente comparación también falla ya que 'A' <> ' ', y nuevamente debe actualizarse el puntero 'k', con su salto de tabla (si procede), k = k + i - F(i) (k = 10 + 0 - (-1) = 11), y también actualizamos 'i', como esta vez 'F(i)= -1', entonces volvemos al principio de 'P', es decir i = 0.

Actualizamos la figura a la nueva posición que apunta el puntero de 'T', (k = 11)

k: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P:            ABCDABD
i:            0123456
F:           -1000012

En esta ocasión de nuevo varias veces se cumplirá que P(i) = T(k +i), hasta que se llega a la posición de 'i = 6, que sucede que 'P(6)=D' que esdistinto de 'T(11 + 6)=C', por lo tanto es necesario una nueva bifurcación hacia la actualización de 'k', k = k + i - F(i) (k = 11 + 6 - 2 = 15). De nuevo entra en juego el salto de la tabla, puesto que 'F(i) = 2', toca actualizar 'i', si F(i) > -1 luego i = F(i), por tanto 'i = 2.

Actualizamos una vez más la figura, hasta avanzar hasta 'k = 15'.

k: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P:                ABCDABD
i:                0123456
F:               -1000012

Como 'i = 2' (porque conseguimos avanzar hasta el índice 6 que en la tabla vale 2, porque antes de la 'D' final hay 2 posiciones coincidentes consecutivamente), entonces ahora volvemos a hacer las comprobaciones pero ahora en 15 + 2, que era: Si P(i) = T(k + i) luego... si i = tamaño de w luego devolver k. Esta parte se cumple hasta finalmente encontrar por completo la cadena, antes de que 'i' pueda ser aumentado a 7 en la parte que sigue a la condición anterior i = i + 1 .

El algoritmo Knuth-Morris-Pratt realiza 26 comparaciones (y el último carácter de la cadena buscada se halla en la posición 21) en el ejemplo, hasta encontrar la solución, en la posición 15. Es necesario recordar solamente que al estar basado en array en índice 0, la solución es 15, aunque por otra parte, en las figuras se ve cómo los punteros de 'k' e 'i' empiezan en 0.

Véase también

Datos: Q45285