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í mismo contiene información suficiente para determinar dónde podría comenzar la siguiente coincidencia, evitando así volver a examinar los personajes previamente coincidentes.
El algoritmo fue concebido por James H. Morris y descubierto de forma independiente por Donald Knuth "unas semanas después" a partir de la teoría de los 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 en 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 coincidencia de palabra en cada índice m, es decir, la posición en la cadena buscada que corresponde al carácter S[m]. En cada posición, mel algoritmo primero verifica 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, entonces no hay ninguna coincidencia, en cuyo caso se dice que la búsqueda "falla".
Por lo general, la verificació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 verificación de prueba rechazará la coincidencia en la letra inicial. La probabilidad de que las dos primeras letras coincidan es de 1 entre 26 (1 entre 26^2 posibilidades de que coincidan entre 26 letras posibles). Entonces, si los caracteres son aleatorios, entonces la complejidad esperada de buscar una cadena S[]de longitud n es del orden de n comparaciones u O ( n ). El rendimiento esperado es muy bueno. Si S[]tiene 1 millón de caracteres y W[]1000 caracteres, entonces la búsqueda de cadenas 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, la verificación de una prueba mpuede requerir muchas comparaciones de caracteres. El peor de los casos es si las dos cadenas coinciden en todas las letras excepto en la última. Imagine que la cadena S[]consta de 1 millón de caracteres, todos ellos 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 ahora examinará 1000 caracteres en cada posición de prueba antes de rechazar la coincidencia y avanzar a la posición de prueba. El ejemplo de búsqueda de cadenas simple ahora tomaría aproximadamente 1000 comparaciones de caracteres multiplicadas por 1 millón de posiciones para mil millones de comparaciones de caracteres. Si la longitud de W[]es k , entonces el peor rendimiento 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 usa esa tabla para realizar una búsqueda eficiente de la cadena en O ( n ).
La diferencia es que KMP utiliza información de coincidencias previas que el algoritmo sencillo no utiliza. En el ejemplo anterior, cuando KMP ve que una coincidencia de prueba falla en el carácter número 1000 ( i= 999) debido a S[m+999] ≠ W[999], se 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 discrepancia en el carácter número 1000 (posición 999). Avanzar la posición de coincidencia de prueba men uno descarta la primera A , por lo que KMP sabe que hay 998 caracteres A que coinciden W[]y no los vuelve a probar; es decir, KMP se establece ien 998. KMP mantiene su conocimiento en la tabla precalculada y en dos variables de estado. Cuando KMP descubre una discrepancia, 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 un momento dado, el algoritmo se encuentra en un estado determinado por dos números enteros:
m, que denota la posición dentro Sde donde comienza la posible coincidencia W,i, que denota el índice del carácter actualmente considerado en W.En cada paso, el algoritmo compara S[m+i]e W[i]incrementa isi son iguales. Esto se representa, al comienzo de la carrera, como
1 2 m: 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 incrementándolo isi coinciden. Sin embargo, en el cuarto paso S[3] = ' 'no coincide W[3] = 'D'. En lugar de comenzar a buscar nuevamente en S[1], observamos que no 'A'ocurre entre las posiciones 1 y 2 en S; por lo tanto, habiendo verificado todos esos caracteres previamente (y sabiendo que coincidieron 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 m: 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 m: 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 discrepancia en W[6]y S[10]. Sin embargo, justo antes del final de la coincidencia parcial actual, existí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 verificar esos caracteres; el algoritmo establece m = 8(el inicio del prefijo inicial) y i = 2(señala que los dos primeros caracteres coinciden) y continúa haciendo coincidir. Por lo tanto, el algoritmo no solo omite los caracteres previamente coincidentes de S(el "AB"), sino también los caracteres previamente coincidentes de W(el prefijo "AB").
1 2 m: 01234567890123456789012S : ABC ABCD AB ABCDABCDABDE W: ABC 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 la primera prueba, 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 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456
La coincidencia m=10falla inmediatamente, por lo que el algoritmo intenta a continuación m = 11y i = 0.
1 2 m: 01234567890123456789012S: ABC ABCDAB ABCDAB C DABDE W: ABCDAB D i: 012345 6
Una vez más, el algoritmo coincide "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 = 2y continúa haciendo coincidir desde la posición actual.
1 2 m: 01234567890123456789012S: ABC ABCDAB ABCD ABCDABD E W: ABCDABD i: 0123456
Esta vez la partida está completa y el primer personaje de la partida es S[15].
El ejemplo anterior contiene todos los elementos del algoritmo. Por el momento, asumimos la existencia de una tabla de "coincidencias parciales" T, que se describe 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 S[m]que comienza en y 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 falta de coincidencia). Esto tiene dos implicaciones: primero, T[0] = -1que indica que si W[0]no coincide, no podemos retroceder y simplemente debemos verificar el siguiente carácter; y segundo, aunque la siguiente coincidencia posible comenzará en index m + i - T[i], como en el ejemplo anterior, no necesitamos verificar ninguno de los T[i]caracteres después de eso, de modo que continuamos buscando desde W[T[i]]. A continuación se muestra un ejemplo de implementación de pseudocódigo del algoritmo de búsqueda KMP.
algoritmo kmp_search : entrada : una matriz de caracteres, S (el texto a buscar) una serie 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 número entero, nP (número de posiciones) definir variables : un número entero, j ← 0 (la posición del carácter actual en S) un número entero, k ← 0 (la posición del carácter actual en W) una matriz de números enteros, T (la tabla, calculada en otro lugar) sea nP ← 0 mientras j < longitud(S) haga si W[k] = S[j] entonces sea j ← j + 1 sea k ← k + 1 si k = longitud(W) entonces (ocurrencia encontrada, si solo se necesita la primera aparición, aquí se puede devolver m ← j - k) sea P[nP] ← j - k, nP ← nP + 1 sea k ← T[k] (T[longitud(W)] no puede ser -1) en caso 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 Knuth-Morris-Pratt tiene complejidad O ( n ) , donde n es la longitud de Sy O es la notación O grande . Excepto por los gastos generales fijos incurridos 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 manera que si una coincidencia que comenzó 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 se puede ejecutar como máximo 2 n veces, ya que en cada iteración ejecuta una de las dos ramas del bucle. La primera rama invariablemente aumenta iy no cambia , de modo que aumenta mel índice m + idel carácter actualmente examinado . SLa segunda rama suma i - T[i]y m, como hemos visto, este es siempre un número positivo. De este modo se incrementa la ubicación mdel inicio del posible emparejamiento actual. Al mismo tiempo, la segunda rama se deja m + isin cambios, se le magrega i - T[i]for e inmediatamente después T[i]se 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 ciclo termina si m + i= n ; por lo tanto, cada rama del bucle se puede alcanzar como máximo n veces, ya que aumentan respectivamente m + io my m ≤ m + i: si m= n , entonces ciertamente m + i≥ n , de modo que como aumenta en incrementos unitarios como máximo, debemos haber tenido m + i= n en algún momento del pasado y, por lo tanto, de cualquier manera estaríamos acabados.
Por lo tanto, el bucle se ejecuta como máximo 2 n veces, lo que muestra 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 comenzamos a hacer coincidir Wy Sen la posición iy p. Si Wexiste como una subcadena de Sat p, entonces W[0..m] = S[p..p+m]. Si tiene éxito, es decir, la palabra y el texto coinciden en las posiciones ( W[i] = S[p+i]), aumentamos ien 1. Si falla, 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 la palabra retrocede una cierta cantidad ( i = T[i], donde Testá la tabla de salto), e intentamos hacer coincidir W[T[i]]con S[p+i]. El número máximo de reversiones iestá limitado por i, es decir, para cualquier falla, solo podemos retroceder tanto como hayamos progresado hasta la falla. 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 comparar algún segmento de la cadena principal con un segmento inicial del patrón, sabemos exactamente en qué lugares se encuentra una nueva coincidencia potencial que podría continuar con la búsqueda actual. La posición podría comenzar antes de la posición actual. En otras palabras, "buscamos previamente" el patrón en sí y compilamos una lista de todas las posiciones alternativas posibles que omiten un máximo de caracteres desesperados 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 que Wconduce a (pero sin incluir) esa posición, aparte del segmento completo que comienza en W[0]el que simplemente no coincidió; Hasta aquí tenemos que retroceder para encontrar el próximo partido. Por lo tanto T[i], es exactamente la longitud del segmento inicial propioW más largo posible, del cual 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), configuramos T[0] = -1, como se explica a continuación.
Consideremos el ejemplo del W = "ABCDABD"primero. Veremos que sigue prácticamente el mismo patrón que la búsqueda principal y es eficiente por motivos similares. Establecimos T[0] = -1. Para encontrarlo T[1], debemos descubrir un sufijo adecuado del "A"cual también es un prefijo de patrón W. Pero no hay sufijos adecuados para "A", por lo que los configuramos T[1] = 0. Para encontrarlo 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, fijamos T[2] = 0.
Continuando con T[3], primero comprobamos el sufijo adecuado de longitud 1 y, como en el caso anterior, falla. ¿Deberíamos comprobar también los sufijos más largos? No, ahora observamos que existe un atajo para verificar todos los sufijos: digamos que descubrimos un sufijo adecuado que es un prefijo adecuado (un prefijo adecuado de una cadena no es igual a la cadena misma) y que termina en W[2]una longitud de 2 (el máximo 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], lo que ya determinamos que no ocurrió como T[2] = 0y no T[2] = 1. Por lo tanto, en cada etapa, la regla de atajo es que uno necesita considerar verificar los 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] = my no debe molestarse en verificar m+2, m+3, etc
Por lo tanto, ni siquiera necesitamos preocuparnos por las subcadenas que tienen longitud 2 y, como en el caso anterior, la única que tiene longitud 1 falla, por lo que T[3] = 0.
Pasamos al siguiente W[4], 'A'. La misma lógica muestra que la subcadena más larga que debemos considerar tiene longitud 1 y, como en el caso anterior, falla ya que "D" no es un prefijo de W. Pero en lugar de configurar T[4] = 0, podemos hacerlo mejor si observamos que W[4] = W[0], y también que una búsqueda de T[4]implica el Scarácter correspondiente, S[m+4]no coincidía y, por lo tanto S[m+4] ≠ 'A', . Por tanto, no tiene sentido reiniciar la búsqueda en S[m+4]; deberíamos comenzar en 1 posición más adelante. Esto significa que podemos cambiar el patrón Wsegún la longitud de la coincidencia más un carácter, por lo que T[4] = -1.
Considerando ahora el siguiente carácter, W[5]que es 'B': aunque tras una inspección la subcadena más larga parecería ser 'A', todavía configuramos T[5] = 0. El razonamiento es similar al por qué T[4] = -1. W[5]en sí mismo extiende la coincidencia de prefijo que comenzó con W[4], y podemos asumir 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 serlo '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 este también es W[5]. Además, el mismo argumento anterior muestra que no necesitamos buscar antes W[4]para encontrar un segmento para W[6], de modo que sea éste, y tomamos T[6] = 2.
Por ello, elaboramos la siguiente tabla:
Otro ejemplo:
Otro ejemplo (ligeramente modificado con respecto al ejemplo anterior):
Otro ejemplo más complicado:
El ejemplo anterior ilustra la técnica general para montar la mesa con un mínimo de complicaciones. El principio es el de la búsqueda global: la mayor parte del trabajo ya se ha hecho para llegar al puesto actual, por lo que queda muy poco por hacer para abandonarlo. 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 algún código de inicialización.
algoritmo kmp_table : entrada : una serie de caracteres, W (la palabra a analizar) producción : una matriz de números enteros, T (la tabla a completar) definir variables : un número entero, pos ← 1 (la posición actual que estamos calculando en T) un número entero, cnd ← 0 (el índice de base cero en W del siguiente carácter de la subcadena candidata actual) sea T[0] ← -1 mientras pos < longitud (W) hazlo si W[pos] = W[cnd] entonces deja que T[pos] ← T[cnd] en caso contrario deja que T[pos] ← cnd mientras cnd ≥ 0 y W[pos] ≠ W[cnd ] sea cnd ← T[cnd] sea pos ← pos + 1, cnd ← cnd + 1 let T[pos] ← cnd (solo es necesario cuando se buscan todas las apariciones de palabras)
La complejidad temporal (y espacial) del algoritmo de la tabla es , donde es la longitud de .W
posse inicializa en 1, la condición del bucle es pos < ky posaumenta en 1 en cada iteración del bucle. Por tanto, el bucle requerirá iteraciones.
cndse inicializa 0y aumenta como máximo en 1 en cada iteración del bucle externo. T[cnd]siempre es menor que cnd, por lo que cndse reduce en al menos 1 en cada iteración del bucle interno; la condición del bucle interno es cnd ≥ 0. Esto significa que el bucle interno se puede ejecutar como máximo tantas veces en total como se ha ejecutado el bucle externo; cada disminución de cnd1 en el bucle interno debe tener un aumento correspondiente de 1 en el bucle externo. Dado que el bucle exterior requiere iteraciones, el bucle interior no puede soportar más de iteraciones en total.Combinados, los bucles exterior e interior toman como máximo iteraciones. Esto corresponde a la complejidad del tiempo usando la notación O grande .
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 falla separada 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 para conocer el índice en el patrón en el que se produjo la discrepancia. Esto devolverá la longitud de la subcadena más larga que termina coincidiendo 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 verificar 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 necesaria ] . 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 lexicográficamente mínima . La función de falla se calcula progresivamente a medida que se gira la cuerda.
En 2012 supe que Yuri Matiyasevich había anticipado los algoritmos de coincidencia de patrones en tiempo lineal y de preprocesamiento de patrones 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 un sistema bidimensional. memoria de trabajo.
