Algoritmo Knuth–Morris–Pratt

El algoritmo para búsqueda de cadenas Knuth–Morris–Pratt (KMP) busca la aparición de una palabra P dentro de una “cadena de texto” principal C, empleando la simple observación de que cuando no sucede una coincidencia, la palabra misma contiene suficiente información para determinar cuando puede ocurrir la siguiente coincidencia, reexaminando caracteres previamente coincidentes.

El algoritmo fue inventado por Knuth y Pratt e independientemente por J. H. Morris en 1977, pero los tres lo publicaron en conjunto.

 

El algoritmo KMP

El objetivo de la tabla es no permitir al algoritmo hacer coincidir ningún carácter de S más de una vez. La observación clave acerca de la naturaleza de la búsqueda lineal que permite que esto suceda esta dada en tener algunos segmentos de la secuencia principal chequeados con un segmento inicial del patrón. Con esto sabemos exactamente en que lugares una nueva coincidencia potencial que podría continuar desde la posición actual podría comenzar previamente a la posición presente. En otras palabras, realizamos una “pre-búsqueda” del patrón mismo y compilamos una lista de todas las posibles posiciones a las que deberíamos retornar, eludiendo al máximo los caracteres inútiles mientras no sacrificamos ninguna coincidencia potencial por eso.

Queremos ser capaces de encontrar, para cada posición de W, la longitud del segmento inicial más largo posible de W, llegando a (pero no incluyendo) esa posición, otro aparte del segmento que comienza en W[0] que no coincidió; esto es cuan lejos debemos volver en la búsqueda de la siguiente coincidencia. Por lo tanto T[i] es exactamente la longitud del segmento inicial apropiado más largo de W, el cual es también un segmento de la subcadena que termina en W[i-1].

Las entradas de T son construidas de tal manera que si una coincidencia que comienza en S[m] falla cuando comparamos S[m+i] con W[i], entonces la siguiente posible coincidencia comenzará en el índice m + i – T[i] en S (esto es, T[i] es la cantidad de “retorno” que debemos hacer luego de una discrepancia). Esto tiene dos consecuencias: primero, T[0] = -1, lo que indica que si W[0] es una discrepancia, no podemos volver y debemos chequear el siguiente carácter; y segundo, si bien la siguiente posible coincidencia comenzará en el índice m + i – T[i], como en el ejemplo anterior, no necesitamos chequear realmente ninguno de los caracteres de T[i] después de eso, entonces continuamos buscando desde W[T[i]]. El siguiente es el pseudocódigo de muestra del algoritmo de búsqueda KMP:

 

algoritmo busqueda_kmp:

entrada:

una matriz de caracteres, S (el texto en el que se debe buscar)

una matriz de caracteres, W (la palabra buscada)

salida:

un entero (la posición de S en la cual W es encontrada)

 

define variables:

un entero, m ← 0 (el principio de la coincidencia actual en S)

un entero, i ← 0 (la posición del caracter actual en W)

un matriz de enteros, T (la tabla, computada en otro sitio)

 

while m + i es menor que la longitud de S, haz:

if W[i] = S[m + i],

let i ← i + 1

if i es igual a la longitud de W,

return m

otherwise,

let m ← m + i – T[i],

if i > 0,

let i ← T[i]

 

(Si llegamos aquí, hemos buscado todo S sin éxito)

return la longitud de S

 

algoritmo tabla_kmp:

input:

una matriz de caracteres, W (la palabra a ser analizada)

una matriz de enteros, T (la tabla a ser llenada)

output:

nada (pero durante la operación llena la tabla)

 

define variables:

un entero, i ← 2 (la posición actual que estamos procesando en T)

un entero, j ← 0 (el índice en W del siguiente caracter de la actual subcadena candidata)

let T[0] ← -1, T[1] ← 0

 

while i es menor que la longitud de W, haz:

(primer caso: la subcadena continúa)

if W[i – 1] = W[j], let T[i] ← j + 1, i ← i + 1, j ← j + 1

(segundo caso: no lo hace, pero podemos recurrir a ella)

otherwise, if j > 0, let j ← T[j]

(tercer caso: hemos agotado los candidatos. Note que j = 0)

otherwise, let T[i] ← 0, i ← i + 1

 

 

Comentarios