En informática , el algoritmo Knuth–Morris–Pratt (o algoritmo KMP ) es un algoritmo de búsqueda de cadenas que busca apariciones de una "palabra" Wdentro de una "cadena de texto" principal Sempleando la observación de que cuando ocurre una falta de coincidencia, la palabra en sí misma contiene suficiente información para determinar dónde podría comenzar la siguiente coincidencia, evitando así el reexamen de caracteres coincidentes previamente.
El algoritmo fue concebido por James H. Morris y descubierto independientemente por Donald Knuth "unas semanas después" a partir de la teoría de autómatas . [1] [2] Morris y Vaughan Pratt publicaron un informe técnico en 1970. [3] Los tres también publicaron el algoritmo conjuntamente en 1977. [1] Independientemente, en 1969, Matiyasevich [4] [5] descubrió un algoritmo similar, codificado por una máquina de Turing bidimensional, mientras estudiaba un problema de reconocimiento de coincidencia de patrones de cadenas sobre un alfabeto binario. Este fue el primer algoritmo de tiempo lineal para la coincidencia de cadenas. [6]
Un algoritmo de coincidencia de cadenas quiere encontrar el índice inicial men la cadena S[]que coincide con la palabra de búsqueda W[].
El algoritmo más sencillo, conocido como algoritmo de " fuerza bruta " o "ingenuo", consiste en buscar una palabra que coincida en cada índice m, es decir, la posición en la cadena que se busca que corresponde al carácter S[m]. En cada posición, mel algoritmo primero comprueba la igualdad del primer carácter de la palabra que se busca, es decir S[m] =? W[0]. Si se encuentra una coincidencia, el algoritmo prueba los demás caracteres de la palabra que se busca comprobando los valores sucesivos del índice de posición de la palabra, i. El algoritmo recupera el carácter W[i]de la palabra que se busca y comprueba la igualdad de la expresión S[m+i] =? W[i]. Si todos los caracteres sucesivos coinciden en Wla posición m, se encuentra una coincidencia en esa posición en la cadena de búsqueda. Si el índice mllega al final de la cadena, no hay ninguna coincidencia, en cuyo caso se dice que la búsqueda "falla".
Por lo general, la comprobación de prueba rechazará rápidamente la coincidencia de prueba. Si las cadenas son letras aleatorias distribuidas uniformemente, entonces la probabilidad de que los caracteres coincidan es de 1 en 26. En la mayoría de los casos, la comprobación de prueba rechazará la coincidencia en la letra inicial. La probabilidad de que las dos primeras letras coincidan es de 1 en 26 (1 en 26^2 probabilidades de una coincidencia en 26 letras posibles). Entonces, si los caracteres son aleatorios, entonces la complejidad esperada de la búsqueda de una cadena S[]de longitud n es del orden de n comparaciones o Θ ( n ). El rendimiento esperado es muy bueno. Si S[]es 1 millón de caracteres y W[]es 1000 caracteres, entonces la búsqueda de cadena debería completarse después de aproximadamente 1,04 millones de comparaciones de caracteres.
Ese rendimiento esperado no está garantizado. Si las cadenas no son aleatorias, entonces la comprobación de un ensayo mpuede requerir muchas comparaciones de caracteres. El peor caso es si las dos cadenas coinciden en todo menos en la última letra. Imagine que la cadena S[]consta de 1 millón de caracteres que son todos A , y que la palabra W[]tiene 999 caracteres A que terminan en un carácter B final . El algoritmo simple de coincidencia de cadenas examinará ahora 1000 caracteres en cada posición de prueba antes de rechazar la coincidencia y avanzar la posición de prueba. El ejemplo simple de búsqueda de cadenas requeriría ahora aproximadamente 1000 comparaciones de caracteres multiplicadas por 1 millón de posiciones para 1000 millones de comparaciones de caracteres. Si la longitud de W[]es k , entonces el rendimiento en el peor caso es O ( k ⋅ n ).
El algoritmo KMP tiene un mejor rendimiento en el peor de los casos que el algoritmo sencillo. KMP dedica un poco de tiempo a precalcular una tabla (del orden del tamaño de W[]O ( k ) ), y luego utiliza esa tabla para realizar una búsqueda eficiente de la cadena en O ( n ).
La diferencia es que KMP hace uso de información de coincidencias previas que el algoritmo sencillo no hace. En el ejemplo anterior, cuando KMP ve que una coincidencia de prueba falla en el carácter 1000 ( i= 999) porque S[m+999] ≠ W[999], incrementará men 1, pero sabrá que los primeros 998 caracteres en la nueva posición ya coinciden. KMP coincidió con 999 caracteres A antes de descubrir una falta de coincidencia en el carácter 1000 (posición 999). Avanzar la posición de coincidencia de prueba men uno descarta el primer A , por lo que KMP sabe que hay 998 caracteres AW[] que coinciden y no los vuelve a probar; es decir, KMP establece ien 998. KMP mantiene su conocimiento en la tabla precalculada y dos variables de estado. Cuando KMP descubre una falta de coincidencia, la tabla determina cuánto aumentará KMP (variable m) y dónde reanudará las pruebas (variable i).
Para ilustrar los detalles del algoritmo, considere una ejecución (relativamente artificial) del algoritmo, donde W= "ABCDABD" y S= "ABC ABCDAB ABCDABCDABDE". En cualquier momento dado, el algoritmo se encuentra en un estado determinado por dos números enteros:
m, que denota la posición en Sla que comienza el posible partido W,i, que denota el índice del carácter actualmente considerado en W.En cada paso, el algoritmo compara S[m+i]y W[i]aumenta isi son iguales. Esto se representa, al comienzo de la ejecución, como
1 2 Teléfono: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: ABC D ABD i: 012 3 456
El algoritmo compara caracteres sucesivos de Wcon caracteres "paralelos" de S, pasando de uno al siguiente incrementando isi coinciden. Sin embargo, en el cuarto paso S[3] = ' 'no coincide W[3] = 'D'. En lugar de comenzar a buscar de nuevo en S[1], notamos que no 'A'ocurre entre las posiciones 1 y 2 en S; por lo tanto, habiendo verificado todos esos caracteres previamente (y sabiendo que coincidían con los caracteres correspondientes en W), no hay posibilidad de encontrar el comienzo de una coincidencia. Por lo tanto, el algoritmo establece m = 3y i = 0.
1 2 Teléfono: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456
Esta coincidencia falla en el carácter inicial, por lo que el algoritmo establece m = 4yi = 0
1 2 Teléfono: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: ABCDAB D i: 012345 6
Aquí, ise incrementa a través de una coincidencia casi completa "ABCDAB"hasta i = 6dar una falta de coincidencia en W[6]y S[10]. Sin embargo, justo antes del final de la coincidencia parcial actual, había esa subcadena "AB"que podría ser el comienzo de una nueva coincidencia, por lo que el algoritmo debe tener esto en cuenta. Como estos caracteres coinciden con los dos caracteres anteriores a la posición actual, no es necesario volver a comprobar esos caracteres; el algoritmo establece m = 8(el inicio del prefijo inicial) y i = 2(lo que indica que coinciden los dos primeros caracteres) y continúa la coincidencia. Por lo tanto, el algoritmo no solo omite los caracteres coincidentes previamente de S(el "AB"), sino también los caracteres coincidentes previamente de W(el prefijo "AB").
1 2 Teléfono: 01234567890123456789012S: ABC ABCD AB ABCDABCDABDE W: AB C DABD i: 01 2 3456
Esta búsqueda en la nueva posición falla inmediatamente porque W[2](a 'C') no coincide con S[10](a ' '). Como en el primer intento, la falta de coincidencia hace que el algoritmo regrese al principio de Wy comience a buscar en la posición del carácter no coincidente de S: m = 10, reset i = 0.
1 2 Teléfono: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456
La coincidencia m=10falla inmediatamente, por lo que el algoritmo vuelve a intentar m = 11y i = 0.
1 2 Teléfono: 01234567890123456789012S: ABC ABCDAB ABCDAB C DABDE W: ABCDAB D i: 012345 6
Una vez más, el algoritmo coincide con "ABCDAB", pero el siguiente carácter, 'C', no coincide con el carácter final 'D'de la palabra W. Razonando como antes, el algoritmo establece m = 15, para comenzar en la cadena de dos caracteres "AB"que conduce a la posición actual, establece i = 2, y continúa la coincidencia desde la posición actual.
1 2 Teléfono: 01234567890123456789012S: ABC ABCDAB ABCD ABCDABD E W: ABCDABD i: 0123456
Esta vez el partido está completo y el primer personaje del partido es S[15].
El ejemplo anterior contiene todos los elementos del algoritmo. Por el momento, suponemos la existencia de una tabla de "coincidencia parcial" T, descrita a continuación, que indica dónde debemos buscar el inicio de una nueva coincidencia cuando se encuentra una discrepancia. Las entradas de Testán construidas de modo que si tenemos una coincidencia que comienza en S[m]que falla al comparar S[m + i]con W[i], entonces la siguiente coincidencia posible comenzará en el índice m + i - T[i]en S(es decir, T[i]es la cantidad de "retroceso" que debemos hacer después de una discrepancia). Esto tiene dos implicaciones: primero, T[0] = -1, que indica que si W[0]es una discrepancia, no podemos retroceder y simplemente debemos verificar el siguiente carácter; y segundo, aunque la siguiente coincidencia posible comenzará en el índice m + i - T[i], como en el ejemplo anterior, no necesitamos verificar ninguno de los T[i]caracteres posteriores a ese, de modo que continuamos buscando desde . Lo siguiente es una implementación de pseudocódigoW[T[i]] de muestra del algoritmo de búsqueda KMP.
algoritmo kmp_search : entrada : una matriz de caracteres, S (el texto que se va a buscar) una matriz de caracteres, W (la palabra buscada) producción : una matriz de números enteros, P (posiciones en S en las que se encuentra W) un entero, nP (número de posiciones) definir variables : un entero, j ← 0 (la posición del carácter actual en S) un entero, k ← 0 (la posición del carácter actual en W) una matriz de números enteros, T (la tabla, calculada en otra parte) sea nP ← 0 mientras j < longitud(S) hacer si W[k] = S[j] entonces sea j ← j + 1 sea k ← k + 1 si k = longitud(W) entonces (se encontró ocurrencia, si solo se necesita la primera ocurrencia, m ← j - k se puede devolver aquí) sea P[nP] ← j - k, nP ← nP + 1 sea k ← T[k] (T[length(W)] no puede ser -1) de lo contrario sea k ← T[k] si k < 0 entonces sea j ← j + 1 sea k ← k + 1
Suponiendo la existencia previa de la tabla T, la parte de búsqueda del algoritmo de Knuth–Morris–Pratt tiene una complejidad O ( n ) , donde n es la longitud de Sy O es la notación big-O . A excepción de la sobrecarga fija incurrida al entrar y salir de la función, todos los cálculos se realizan en el whilebucle. Para limitar el número de iteraciones de este bucle, observe que Testá construido de modo que si una coincidencia que había comenzado en S[m]falla al comparar S[m + i]con W[i], entonces la siguiente coincidencia posible debe comenzar en S[m + (i - T[i])]. En particular, la siguiente coincidencia posible debe ocurrir en un índice mayor que m, de modo que T[i] < i.
Este hecho implica que el bucle puede ejecutarse como máximo 2 n veces, ya que en cada iteración ejecuta una de las dos ramas del bucle. La primera rama aumenta invariablemente iy no cambia m, de modo que el índice m + idel carácter actualmente examinado de Saumenta. La segunda rama suma i - T[i], my como hemos visto, este es siempre un número positivo. Por lo tanto, la ubicación mdel comienzo de la coincidencia potencial actual aumenta. Al mismo tiempo, la segunda rama deja m + isin cambios, mse le i - T[i]suma for e inmediatamente después T[i]se le asigna como el nuevo valor de i, por lo tanto new_m + new_i = old_m + old_i - T[old_i] + T[old_i] = old_m + old_i. Ahora, el bucle termina si m + i= n ; por lo tanto, se puede llegar a cada rama del bucle como máximo n veces, ya que aumentan respectivamente m + io m, y m ≤ m + i: si m= n , entonces ciertamente m + i≥ n , de modo que, dado que aumenta en incrementos unitarios como máximo, debemos haber tenido m + i= n en algún momento en el pasado y, por lo tanto, de cualquier manera, habríamos terminado.
Por lo tanto, el bucle se ejecuta como máximo 2 n veces, lo que demuestra que la complejidad temporal del algoritmo de búsqueda es O ( n ).
Aquí hay otra forma de pensar en el tiempo de ejecución: digamos que empezamos a hacer coincidir Wy Sen la posición iy p. Si Wexiste como una subcadena de Sen p, entonces W[0..m] = S[p..p+m]. En caso de éxito, es decir, la palabra y el texto coinciden en las posiciones ( W[i] = S[p+i]), aumentamos ien 1. En caso de error, es decir, la palabra y el texto no coinciden en las posiciones ( W[i] ≠ S[p+i]), el puntero de texto se mantiene quieto, mientras que el puntero de palabra retrocede una cierta cantidad ( i = T[i], donde Tes la tabla de saltos), e intentamos hacer coincidir W[T[i]]con S[p+i]. El número máximo de retrocesos de iestá limitado por i, es decir, para cualquier error, solo podemos retroceder tanto como hayamos progresado hasta el error. Entonces está claro que el tiempo de ejecución es 2 n .
El objetivo de la tabla es permitir que el algoritmo no coincida con ningún carácter Smás de una vez. La observación clave sobre la naturaleza de una búsqueda lineal que permite que esto suceda es que, al haber comprobado algún segmento de la cadena principal con un segmento inicial del patrón, sabemos exactamente en qué lugares podría comenzar una nueva coincidencia potencial que podría continuar hasta la posición actual antes de la posición actual. En otras palabras, realizamos una "búsqueda previa" del patrón en sí y compilamos una lista de todas las posibles posiciones de reserva que pasan por alto un máximo de caracteres sin esperanza sin sacrificar ninguna coincidencia potencial al hacerlo.
Queremos poder buscar, para cada posición en W, la longitud del segmento inicial más largo posible de que Wconduce a (pero no incluye) esa posición, aparte del segmento completo que comienza en W[0]que simplemente no coincidió; esta es la distancia que tenemos que retroceder para encontrar la siguiente coincidencia. Por lo tanto, T[i]es exactamente la longitud del segmento inicial adecuadoW más largo posible de que también es un segmento de la subcadena que termina en W[i - 1]. Usamos la convención de que la cadena vacía tiene longitud 0. Dado que una falta de coincidencia al comienzo del patrón es un caso especial (no hay posibilidad de retroceder), establecemos T[0] = -1, como se analiza a continuación.
Consideremos el ejemplo de W = "ABCDABD"primero. Veremos que sigue en gran medida el mismo patrón que la búsqueda principal y es eficiente por razones similares. Establecemos T[0] = -1. Para encontrar T[1], debemos descubrir un sufijo adecuado de "A"que también sea un prefijo del patrón W. Pero no hay sufijos adecuados de "A", por lo que establecemos T[1] = 0. Para encontrar T[2], vemos que la subcadena W[0]- W[1]( "AB") tiene un sufijo adecuado "B". Sin embargo, "B" no es un prefijo del patrón W. Por lo tanto, establecemos T[2] = 0.
Continuando con T[3], primero verificamos el sufijo apropiado de longitud 1, y como en el caso anterior falla. ¿Deberíamos verificar también sufijos más largos? No, ahora notamos que hay un atajo para verificar todos los sufijos: digamos que descubrimos un sufijo apropiado que es un prefijo apropiado (un prefijo apropiado de una cadena no es igual a la cadena misma) y termina en W[2]con longitud 2 (la máxima posible); entonces su primer carácter también es un prefijo propio de W, por lo tanto un prefijo propio en sí mismo, y termina en W[1], que ya determinamos que no ocurrió como T[2] = 0y no T[2] = 1. Por lo tanto, en cada etapa, la regla del atajo es que uno necesita considerar verificar sufijos de un tamaño dado m+1 solo si se encontró un sufijo válido de tamaño m en la etapa anterior (es decir T[x] = m) y no debería molestarse en verificar m+2, m+3, etc.
Por lo tanto, ni siquiera necesitamos preocuparnos por subcadenas que tengan una longitud de 2, y como en el caso anterior, la única con longitud de 1 falla, entonces T[3] = 0.
Pasamos a la siguiente W[4], 'A'. La misma lógica muestra que la subcadena más larga que necesitamos considerar tiene longitud 1, y como en el caso anterior falla ya que "D" no es un prefijo de W. Pero en lugar de establecer T[4] = 0, podemos hacerlo mejor notando que W[4] = W[0], y también que una búsqueda de implica que el carácter T[4]correspondiente , , no coincidía y por lo tanto . Por lo tanto, no tiene sentido reiniciar la búsqueda en ; deberíamos comenzar en 1 posición por delante. Esto significa que podemos cambiar el patrón por la longitud de coincidencia más un carácter, por lo que .SS[m+4]S[m+4] ≠ 'A'S[m+4]WT[4] = -1
Si consideramos ahora el siguiente carácter, W[5], que es 'B': aunque por inspección la subcadena más larga parecería ser 'A', aún así establecemos T[5] = 0. El razonamiento es similar a por qué T[4] = -1. W[5]en sí mismo extiende la coincidencia de prefijo iniciada con W[4], y podemos suponer que el carácter correspondiente en S, S[m+5] ≠ 'B'. Por lo tanto, retroceder antes W[5]no tiene sentido, pero S[m+5]puede ser 'A', por lo tanto T[5] = 0.
Finalmente, vemos que el siguiente carácter en el segmento en curso que comienza en W[4] = 'A'sería 'B', y de hecho también es W[5]. Además, el mismo argumento que el anterior muestra que no necesitamos buscar antes W[4]para encontrar un segmento para W[6], de modo que este es el indicado, y tomamos T[6] = 2.
Por lo tanto, elaboramos la siguiente tabla:
Otro ejemplo:
Otro ejemplo (ligeramente modificado respecto al ejemplo anterior):
Otro ejemplo más complicado:
El ejemplo anterior ilustra la técnica general para ensamblar la tabla con un mínimo de complicaciones. El principio es el de la búsqueda general: la mayor parte del trabajo ya se realizó para llegar a la posición actual, por lo que es muy poco lo que se necesita hacer para salir de ella. La única complicación menor es que la lógica que es correcta al final de la cadena proporciona erróneamente subcadenas no adecuadas al principio. Esto requiere un código de inicialización.
algoritmo kmp_table : entrada : una matriz de caracteres, W (la palabra a analizar) producción : una matriz de números enteros, T (la tabla que se va a rellenar) definir variables : un entero, pos ← 1 (la posición actual que estamos calculando en T) un entero, cnd ← 0 (el índice basado en cero en W del siguiente carácter de la subcadena candidata actual) sea T[0] ← -1 mientras pos < length(W) hacer si W[pos] = W[cnd] entonces sea T[pos] ← T[cnd] de lo contrario sea T[pos] ← cnd mientras cnd ≥ 0 y W[pos] ≠ W[cnd] hacer sea cnd ← T[cnd] sea pos ← pos + 1, cnd ← cnd + 1 deje que T[pos] ← cnd (solo es necesario cuando se buscan todas las ocurrencias de palabras)
La complejidad temporal (y espacial) del algoritmo de tabla es , donde es la longitud de .W
posse inicializa en 1, la condición del bucle es pos < k, y posse incrementa en 1 en cada iteración del bucle. Por lo tanto, el bucle tardará iteraciones.
cndse inicializa con 0y se incrementa en, como máximo, 1 en cada iteración del bucle externo. T[cnd]siempre es menor que cnd, por lo que cndse reduce en, como mínimo, 1 en cada iteración del bucle interno; la condición del bucle interno es cnd ≥ 0. Esto significa que el bucle interno puede ejecutarse, como máximo, tantas veces en total como el bucle externo se haya ejecutado; cada reducción de cnden 1 en el bucle interno debe tener un aumento correspondiente en 1 en el bucle externo. Dado que el bucle externo requiere iteraciones, el bucle interno no puede requerir más de iteraciones en total.Combinados, los bucles externo e interno requieren como máximo iteraciones. Esto corresponde a la complejidad temporal utilizando la notación Big O.
Dado que las dos partes del algoritmo tienen, respectivamente, complejidades de O(k)y O(n), la complejidad del algoritmo general es O(n + k).
Estas complejidades son las mismas, sin importar cuántos patrones repetitivos haya en Wo S.
Se puede implementar una versión en tiempo real de KMP utilizando una tabla de funciones de error independiente para cada carácter del alfabeto. Si se produce una discrepancia en un carácter del texto, se consulta la tabla de funciones de error para el carácter en el índice del patrón en el que se produjo la discrepancia. Esto devolverá la longitud de la subcadena más larga que termina en que coincide con un prefijo del patrón, con la condición adicional de que el carácter después del prefijo sea . Con esta restricción, no es necesario volver a comprobar los caracteres del texto en la siguiente fase, por lo que solo se ejecuta un número constante de operaciones entre el procesamiento de cada índice del texto [ cita requerida ] . Esto satisface la restricción de computación en tiempo real.
El algoritmo de Booth utiliza una versión modificada de la función de preprocesamiento KMP para encontrar la rotación de cadena mínima desde el punto de vista lexicográfico . La función de falla se calcula progresivamente a medida que se rota la cadena.
En 2012 me enteré de que Yuri Matiyasevich había anticipado los algoritmos de preprocesamiento y comparación de patrones en tiempo lineal de este artículo, en el caso especial de un alfabeto binario, ya en 1969. Los presentó como construcciones para una máquina de Turing con una memoria de trabajo bidimensional.
