Algoritmo Knuth-Morris-Pratt

El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple. Por lo tanto su objetivo es buscar la existencia de una subcadena (habitualmente llamada patrón) dentro de otra cadena. La búsqueda se lleva a cabo utilizando información basada en los fallos previos. Información obtenida del propio patrón creando previamente una tabla de valores sobre su propio contenido. El objetivo de crear dicha tabla es poder 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.

En 1970 S.A. Cook sugirió la existencia de un algoritmo que resuelve la búsqueda en un tiempo equivalente a M+N, en el peor caso, a raíz de unos resultados teóricos que obtuvo mientras probaba un tipo de máquina abstracta.^[1]​ Knuth y Pratt siguiendo los pasos que Cook usó para probar su teorema, lograron crear el algoritmo que lleva sus nombres. De modo independiente Morris mientras trabajaba en un editor de texto acabó descubriendo el mismo algoritmo, para satisfacer la cuestión de la búsqueda eficiente de subcadenas, y que publicaron juntos los tres en 1976.

El algoritmo KMP trata de localizar la posición de comienzo de una cadena dentro de otra. Previamente sobre el patrón a localizar se calcula una tabla de saltos (conocida como tabla de fallos) que después se utiliza (al examinar las cadenas) para hacer saltos cuando se localiza un fallo de coincidencia en la comparación de un carácter.

Supongamos una tabla 'F' ya precalculada, y supongamos que el patrón a buscar esté contenido en la matriz 'P()', y la cadena donde buscamos esté contenida en la matriz 'T()'. Entonces ambas cadenas comienzan a compararse usando un puntero de avance para el patrón, si ocurre un fallo (de coincidencia), el puntero salta hacia donde indica el valor en la posición del puntero actual sobre la tabla de fallos . El array 'T' utiliza un puntero de avance absoluto que determina el comienzo de una sección del mismo tamaño que el patrón. Dentro de dicha sección se desplaza con el puntero del patrón, analizando cada carácter en la sección con cada carácter en el patrón. Se dan 2 situaciones:

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

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 patrón a buscar, se localiza sobre sí mismo que partes se repiten enteramente dentro del patrón desde el comienzo y para ello se elabora una lista con todas las posiciones, de salto atrás que señalen cuanto se retrocede desde la posición actual (que ya hayan coincido y luego fallado) del patrón. Por ejemplo si el texto a buscar es 'posponer' y estamos examinando un texto como 'el presente texto es pospositivo mientras nos falte el ingenio', cuando llegamos a encontrar 'pospo'sitivo coincidente con 'pospo'ner, tras esa 2ª 'po', en el patrón ahora se espera encontrar una 'n', que falla, pues aparece una 's' en el array 'T', la pregunta lógica sería ¿ dónde se encuentra de nuevo (si existe) la primera letra en el texto (antes del fallo), y hasta donde logra repetirse ?. La respuesta a esta pregunta será el punto de salto, en el caso de ejemplo (el patrón 'posponer'). Dicho punto nos lo 'susurra' la tabla de fallos en la posición que falla 'n' (posición 5), con un valor de 3, que viene a decir que coinciden tres caracteres desde el comienzo hasta justo antes del fallo, luego puede hacerse un salto para alinear 'pos'poner con pos'pos'itivo, y continuar comparando desde 'p' con 'i' respectivamente en cada palabra.

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, 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 (el valor que contiene la tabla siempre se usa restando en la función de búsqueda, luego restar un -1, supone en efecto sumar 1 y por tanto avanza).

Es importante notar que las únicas repeticiones que cuentan son aquellas que se repiten enteramente desde el comienzo del patrón. Por ejemplo, si el patrón fuera 'cateter', que aparezca repetido las letras 'te' más de una vez carece de importancia, pues la segunda vez no va precedido de forma continua desde el comienzo, como podría ser en la palabra ficticia 'catequiscater'.

Primero un sencillo ejemplo donde hay una única ocurrencia.

Ahora un ejemplo más interesante

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.

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

Genéricamente puede despreciarse el tiempo de cálculo de la tabla de fallos del patrón, salvo que su tamaño sea excesivamente grande. También en los casos en que el mismo patrón se buscará en muchos diferentes textos y que es la razón por la que conviene precalcular la tabla de fallos del patrón de forma independiente de la función de búsqueda.

La capacidad del algoritmo (para demostrar que no examina caracteres más de dos veces) 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 mayor es el valor en la tabla tanto más grande es el salto resultante (salto debido a que dichos caracteres ya han sido examinados) y cuantos más ceros haya, señala que ha ido avanzando el puntero absoluto de uno en uno.

En la práctica el algoritmo no será mucho mejor que el algoritmo lineal de fuerza bruta, en condicioes normales (texto del lenguaje hablado, por ejemplo), pero mejora sustancialmente, respecto del mismo cuando sale de dichas condiciones normales, en tanto que algoritmo presente no presenta demasiada sobrecarga.

Respecto del patrón, no existe caso mejor ni peor (considerado por sí solo), puede demostrarse que en una tabla de fallos donde son todo ceros (o lo que es lo mismo, el primer carácter del patrón aparece una única vez (por ejemplo P ="ABBBBBBB")), tiene el mismo coste que cuando el patrón se compone de 2 únicos caracteres donde 1 se repite en todo el patrón y el otro aparece al final, (por ejemplo: P= "AAAAAAAB", (obsérvese la tabla F para dicho texto)) y tiene el mismo coste que en cualquier otra situación intermedia entre dichos extremos:

En el caso de que el primer carácter aparezca una única vez (ver tabla aquí debajo), examina la A, si coincide, examina la B, en caso de fallo simplemente salta 1 carácter. Si el patrón existiere finalmente en el texto, será cuando haya oportunidad de examinar el resto de caracteres, antes de alcanzar el final del texto.

Igualmente cuando el primer carácter se repite excepto en el último carácter. Recorrería, hasta el último que genera el fallo, pero igualmente el puntero absoluto del texto, solo avanza 1, con cada fallo.

La diferencia entre uno y otro casos consiste básicamente en donde se localiza el puntero en el patrón y en qué momento se recorre el resto del patrón si al principio o al final del texto.

Para el texto, el mejor caso se da cuando el patrón se localiza en la posición 0. El peor caso se da cuando el patrón se localiza en la última posición. Si el texto no se encuentra, es igual o ligeramente mejor que el peor caso, y es en tal caso dependiente del patrón (ver sección anterior y siguiente).

Considerando conjuntamente el patrón y el texto, el peor caso se puede dar en función de donde y cuantas veces surja la ruptura del patrón. Cada carácter fallido necesita ser comprobado otra vez con aquel con el que se alinea. Esto implica que el peor caso puede llegar a tener un costo de O(n) + O(k*2), si bien en la práctica estos casos son raros, pues no es frecuente que deban realizarse búsqueda con patrones o textos cuyos caracteres tengan una alta frecuencia de reptición (como los que s emuestran de ejemplo a continuación)..

Ejemplos: Patrón (tabla F):Texto = nº de comparaciones precisas (en todos los ejemplos el tamaño del patrón y del texto es igual: 6:30)

AAAAAZ (-1  0  1  2  3  4):AAAAACAAAAACAAAAACAAAAACAAAAAZ = 51

AAAAAZ (-1  0  1  2  3  4):AAAAAAAAAAAAAAAAAAAAAAAAAAAAAZ = 54

ABBBBB (-1  0  0  0  0  0):ABBBBZABBBBZABBBBZABBBBZABBBBB = 35 (coste típico m+n).

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 (para el presente artículo) que tanto en los ejemplos como en el pseudocódigo, los arrays 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 del patrón 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.

Se muestra la tabla F, precalculada para el ejemplo.

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.

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)

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.

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').

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)

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'.

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 (para este ejemplo) realiza 26 comparaciones hasta encontrar la solución, en la posición 15. Es necesario recordar que al estar basado en array el índice es 0 (frente a la habitual forma de contar caracteres desde la posición 1), aunque por otra parte, en las figuras se ve cómo los punteros de 'k' e 'i' empiezan en 0.

---