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.
Descripción del algoritmo KMP
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:
- Mientras existan coincidencias el puntero de avance de 'P', se va incrementando (apunta al siguiente par de caracteres a comparar entre el patrón y la sección actual en el array 'T') y si alcanza el final del patrón se devuelve la posición actual del puntero absoluto del array 'T'.
- Si se da un fallo, la sección del array 'T' (el puntero absoluto de avance) se actualiza, sumando el valor del puntero de 'P' + el valor que contiene la tabla 'F' en el mismo índice que 'P'. Además de actualizar la sección bajo examen, debe igualmente alinearse el patrón bajo dicha sección, para coincidir 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 (comienzo del patrón y de la siguiente sección).
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 (patrón) que se busca) Salida: un entero (que expresa la posición en T en la cual se encontró P) Variables en juego: un entero, k ← 0 (posición absoluta de la sección bajo examen en el array T) un entero, i ← 0 (posición absoluta del carácter bajo examen en el array P) un entero, m ← size(T) (Cantidad de caracteres en el array T) un entero, n ← size(P) (cantidad de caracteres en el array P) un array de enteros, F (la tabla de fallo, calculada previamente o a continuación) Código: Si (m => n) F = TablaKMP(P) (calcula la tabla de fallos) En Bucle Mientras ((i < n) y ((k + i) < m) ) Si P[i] = T[k + i] Asignar i ← (i + 1) Si no Asignar k ← (k + i - F[i]) Si (i > 0) Asignar i ← F[i] Fin si Repetir Fin si Si (i = n) Devolver k si no Devolver m (o devolver -1, si se usa un entero con signo) Fin si
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 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'.
Ejemplos de un patrón y la creación de su tabla de fallo
Primero un sencillo ejemplo donde hay una única 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/patrón/texto que va a ser analizada) Salida: un array de enteros, F (la tabla de fallos a rellenar) del mismo tamaño que P. Variables en juego: 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 candidato actuala) un entero, n ← Size(p) (cantidad de caracteres en el patrón) Código: (algunos valores se fijan con determinado valor) Asignar F[0] ← -1, F[1] ← 0 (ver explicación más arriba, en el apartado de la descripción) En Bucle Mientras (pos => n) Si P[pos - 1] = P[cnd] (caso 1º: siguiente candidato coincidente en la cadena) Asignar cnd ← (cnd + 1), F[pos] ← cnd, pos ← (pos + 1) Pero si (cnd > 0) (caso 2º: con fallo de coincidencias consecutivas, se asigna un valor ya conocido) Asignar cnd ← F[cnd] Y si no (caso 3º: no se halló candidatos coincidentes (otra vez)) Asignar F[pos] ← 0, pos ← (pos + 1) Fin si Repetir Devolver F (si no se recibió por referencia)
Eficiencia del algoritmo
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.
Casos peor y mejor para el patrón
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:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
P[i] | A | A | A | A | A | A | A | B |
F[i] | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
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.
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
P[i] | A | B | B | B | B | B | B | B |
F[i] | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
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.
Casos peor y mejor para el 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).
Casos peor y mejor en la búsqueda
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).
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 (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.
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 (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.
Véase también
Referencias
- Algorithms, de R. Sedgewick, Editorial Addison-Wesley Publishing Company, USA, 1983, página: 242. ISBN 0-201-06672-6.
- Algorithms, R.Sedgewick - Ed. Addison-Wesley, 1983, página: 244 y siguientes, ISBN:0-201-06672-6
- Data Structures & their Algorithms, H.R. Lewis y L. Deneberg - Ed.Harper Collins, 1991, página: 157 y siguientes, ISBN:0-673-39736-X