Algoritmo Knuth-Morris-Pratt

El algoritmo KMP tiene por objeto buscar la existencia de palabra dentro de una cadena de texto. 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.

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 entre si las cadenas se utiliza para hacer saltos cuando se localiza un fallo.

Supongamos una tabla ya precalculada, y supongamos que la cadena a buscar esté contenida en el array 'W()', y la cadena donde buscamos esté contenida en un array 'S()'. 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 'S' 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 'W'. Se dan 2 situaciones:

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

Si se da un fallo, el puntero de avance de 'S' se actualiza hasta, con la suma actual del puntero de 'W' + el valor de la tabla 'T' apuntado por el mismo que 'W'. A continuación se actualiza el puntero de 'W', bajo una de 2 cicunstancias; Si el valor de T es mayor que -1 el puntero de 'W', toma el valor que indica la tabla de salto T, 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, S (el texto donde se busca)
   un array de caracteres, W (la palabra que se busca)
 Salida:
   un entero que expresa la posición en S en la cual se encontró W. 
      (nota: opcionalmente puede convenir devolver un entero con signo).

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

El objetivo de la tabla (precalculada) es no permitir que cada carácter de S() 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'  La última e tiene a una distancia de 1 la última aparición de T.

Ahora un ejemplo más interesante

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

Y terminamos con un ejemplo de 2 coincidencias de 3 letras consecutivas.

'01234567890123456789012345
'PARTICIPARIA EN PARACAIDAS'  
-10000000123000000123000000 La P es la 0ª letra, luego en la posición 7 vuelve a aparecer, por tanto la 8ª, 
marca un 1, luego coinciden las 2 siguientes, luego se marcan su distancia, luego vuelve a fallar...
las mismas ocurrencias vuelven a aparecer por 3ª vez. 'PAR'

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

 Algoritmo TablaKMP:
    Entrada:
        un array de caracteres, W (el texto que va a ser analizada)
        un array de enteros, T (la tabla que será rellenada) debe tener el mismo tamaño que W
    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 T)
        un entero, cnd ← 0 (el índice en W del sigiente 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)
    asignar T[0] ← -1, T[1] ← 0

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

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 T, 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 W ="ABCDEFG". El peor caso se da cuando la cadena se compone de 1 único carácter, por ejemplo: W= "AAAAAAAA", obsérvese la Tabla para dicho texto:

i	0	1	2	3	4	5	6	7
W[i]	A	A	A	A	A	A	A	A
T[i]	-1	0	1	2	3	4	5	6

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 S es el array de caracteres donde queremos buscar y W el array que se quiere hallar en S, usando m como puntero absoluto para los caracteres de S e i como puntero para los caracteres de W. Se usa también, una tabla (matriz) precalculada de la palabra a buscar T. A continuación se ve una figura que representan las variables consideradas para el ejemplo.

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
T:-1000012

Se muestra la tabla T, precalculada para el ejemplo.

i	0	1	2	3	4	5	6
W[i]	A	B	C	D	A	B	D
T[i]	-1	0	0	0	0	1	2

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
T:-1000012

Comienza el cálculo, los punteros 'm' e 'i' inicialmente valen 0. Si W(i) = S(m + i), se evalúa a continuación si i = tamaño de W 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 W(3) tenemos 'D' y en W(m + i) tenemos ' '(un espacio), momento en que actualizamos 'm', m = m + i - T(i) (m = 3). A continuación verificamos si T(i) > -1 (t(3) vale 0), como se da el caso hacemos para i = T(i). Es decir saltamos a la posición sobre el array 'W' que señala 'T(i)', que en este caso es 0, por tanto al principio del array 'W', pero ahora el puntero del array 'S' está en 3 (m = 3).

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

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:    ABCDABD
i:    0123456
T:   -1000012

Volvemos al principio del bucle (cada vez que se vuelve a este punto se comprueba si m alcanzó el tamaño de 'S' y de nuevo verificamos si W(i) = S(m + i). Vemos que en el punto actual en 'W' hay un espacio, por lo que, nuevamente se actualiza 'm', m = m + i - T(i) (m = 4), porque 'T(i) = -1'. Ahora entonce 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 'm', (m = 4)

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456
T:    -1000012

Ahora vemos que varias veces se cumple que W(i) = S(m + i), pero no tantas que se alcance el tamaño de 'W', 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 W luego devolver m (si no habríamos alcanzado la solución). Al analizar de nuevo al inicio del bucle la posición 6, falla ya que 'W(6) = D' y 'S(4 + 6) =' . en este punto toca actualizar 'm', y hacemos m = m + i - T(i) (m = 4 + 6 - T(6), en este punto T(6) vale 2, por lo que finalmente damos un salto 'm = 4 + 6 - 2 = 8'. Y actualizamos 'i', si t(6) > -1 luego i = t(i), es decir no solo acanzamos el puntero de 'S', sino que además avanzamos el puntero de 'W' 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 T.

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

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456
T:        -1000012

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

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

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:           ABCDABD
i:           0123456
T:          -1000012

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

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

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456
T:           -1000012

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

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

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456
T:               -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 comrpobaciones pero ahora en 15 + 2, que era: Si W(i) = S(m + i) luego... si i = tamaño de w luego devolver m. 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 como los punteros de 'm' e 'i' empiezan en 0.