18 DE NOVIEMBRE DE 2015

KNUTH-MORRIS-PRATT
3CV2

RAMIREZ AGUILAR ABIGAIL ADORAIM
RODRIGUEZ TORRES GERARDO
NAVA MARTINEZ DANIEL
GUZMÁN MUÑOZ MIGUEL ANGEL
Prof: Daniel Cruz García

Contenido
¿Qué es? ........................................................................................................................................ 2
¿Para qué sirve?............................................................................................................................. 2
¿Cómo se utiliza? ........................................................................................................................... 2
Teoría del algoritmo....................................................................................................................... 4
Definición formal e informal....................................................................................................... 4
Variantes del algoritmo .............................................................................................................. 5
Complejidad del algoritmo ......................................................................................................... 7
Aplicaciones del algoritmo ............................................................................................................. 8
Implementación del algoritmo ....................................................................................................... 9
Código: ...................................................................................................................................... 9
Pantalla de Ejecución ................................................................................................................... 13
Conclusiones................................................................................................................................ 13
Bibliografía .................................................................................................................................. 14

¿Qué es?
El algoritmo Knurris-Morris-Patt es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. El algoritmo originalmente fue elaborado por Donald Knuth y Vaughan Pratt y de modo independiente por
James H. Morris en 1977, pero lo publicaron juntos los tres.
Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella se precalcula una tabla de valores), para 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.
El algoritmo KMP, trata de localizar la posición de comienzo de una cadena, dentro de otra. Antes que nada con la cadena a localizar se precalcula una tabla de saltos (conocida como tabla de fallos) que después al examinar entre si las cadenas se utiliza para hacer saltos cuando se localiza un fallo. [1]

¿Para qué sirve?
El algoritmo de Knutt-Morris-Patt nos sirve principalmente para:
•

Buscar la existencia de una subcadena dentro de una cadena.

•

Búsqueda de Patrones.

•

Búsqueda de un patrón dentro de una cadena de caracteres. [2]

¿Cómo se utiliza?
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. t ={CTCACTGCCTGCCTAG} y un patrón p = {CTGCCTAG}, y el patrón p se encuentra dentro de t a partir de noveno símbolo. Entonces, como antes, podemos decir que el patrón se encuentra en t con un desplazamiento s = 8.
En el KMP, primero de todo se calcula la next table para el patrón. Para el patrón p = {CTGCCTAG} sería la siguiente:

A la hora de construir la next table, se asigna un valor de -1 a la posición 0 del vector de la next table y un 0 a la posición 1. El valor -1 en la posición 0 es una señal cualquiera que nos sirve para comenzar la comparación con el siguiente nucleótido de la secuencia en caso que se produzca un mismatch entre la posición 0 del vector patrón y un símbolo de la secuencia. En la posición 1 del vector de la next table se tendría que comparar el prefijo de la posición 1, formado exclusivamente por la posición 0, con el patrón antes de la posición 1. Como el prefijo, aunque es coincidente, siempre será máximo, asignaremos directamente el valor 0 a la posición 1.
Continuamos con la posición 2 del vector patrón, donde se mira el número máximo de nucleótidos coincidentes con el patrón antes de esa posición. En este caso es sencillo, ya que sólo hemos de mirar si la posición 1 (T) es igual que la posición 0 (C) del vector patrón.
Como no son iguales, el valor del vector de la next table para la posición 2 será 0. Si pasamos a la posición 3, hemos de comparar si el prefijo formado por las posiciones 1 y 2 o el formado únicamente por la 2 coinciden con el patrón des de su inicio, es decir, si el prefijo constituido por las posiciones 1 y 2 es igual a las posiciones 0 y 1 o si la posición 2 es igual que la posición 0 del patrón. En este caso, no se produce ninguna coincidencia, de manera que el valor de la next table para la posición 3 es 0. Si miramos la posición 4, tendremos que comparar los prefijos formados por las posiciones 1, 2 y 3, por las posiciones 2 y 3 o por la posición 3 con el patrón que les precede. Aquí vemos que la posición 3 es igual a la posición 0 del vector patrón, así que el valor del vector de la next table para la posición 4 es igual a 1 (el prefijo mayor en la posición 4 que coincide con el patrón está formado por un nucleótido).
Si ahora nos centramos en la posición 5, ocurre lo mismo que con la posición 4, y el prefijo mayor que coincide con el patrón es de un nucleótido, de manera que el valor de la next table para la posición 5 es 1. Cuando miramos la posición 6, tenemos diferentes prefijos: los formados por las posiciones 1, 2, 3, 4 y 5, por 2, 3, 4 y 5, por 3, 4 y 5, por 4 y 5 y por 5. En este caso, el prefijo formado por las posiciones 4 y 5 coinciden con las posiciones 0 y 1 del vector patrón, y pondremos un 2 (2 nucleótidos coincidentes) en la posición 6 del vector de la next table. Para finalizar con la next table de este patrón, miramos la última posición, la 7. Ninguno de los prefijos para esta posición coincide con el patrón. Así pues, el vector de la next table tendrá un valor de 0 en la posición 7. [3]

Teoría del algoritmo
Definición formal e informal
Dada una cadena P y un texto T se puede aprender de los errores en la secuencia para realizar menos ciclos de comparación.
Por ejemplo:
Buscando “nano” en el texto “banananobano” de la manera tradicional, donde se buscan coincidencias a partir de cada índice en T[ ].

0 1 2 3 4 5 6 7 8 9 10 11
T: b a n a n a n o b a n o i=0: X i=1: i=2: i=3: i=4: i=5: i=6: i=7: i=8: i=9: i=10:

X n a
X

n

X

n

a
X

n

o

n

X
X
X n X
X

Definiendo un traslape, para poder “aprender de los errores” y utilizarlos.
0 1 2 3 4 5 6 7 8 9 10 11
T: b a n a n a n o b a n o i=0: X i=1: i=2: i=4: i=7: i=8: i=9: i=10: X n a

n n X a n

o
X
X n X
X

Variantes del algoritmo
KMP, version 1: i=0; o=0; while (i 0 && patron[i] != patron[traslape[i + 1] - 1]) traslape[i + 1] = traslape[traslape[i + 1] - 1] + 1;
}
return traslape;

Complejidad del algoritmo
Tomando como referencia el siguiente ejecución
Operaciones basicas void preKmp(char *x, int m, int kmpNext[]) { int i, j; i = 0; j = kmpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = kmpNext[j]; i++; j++; if (x[i] == x[j]) kmpNext[i] = kmpNext[j]; else kmpNext[i] = j;
}
} void KMP(char *x, int m, char *y, int n) { int i, j, kmpNext[XSIZE];
/* Preprocessing */ preKmp(x, m, kmpNext);
/* Searching */ i = j = 0; while (j < n) { while (i > -1 && x[i] != y[j]) i = kmpNext[i]; i++; j++; if (i >= m) {
OUTPUT(j - i); i = kmpNext[i];
}
}
}

Note que el número total de veces que el ciclo interior es ejecutado es menor o igual al número de veces que se puede decrementar j, dado que f(j) Patron a buscar tabla -> tabla Fucion fallo
*/

/************************* Tabla KMP **************************/

void tabla_kmp(char W[] , signed int tabla[])
{
signed int pos = 2 ; // posicion actual donde esta tabla de fallo int cnd = 0 ; // indice del patron

tabla[0] = -1 ; tabla[1] = 0 ; //comienzo del analisis

while( pos 0 ) //se hace la verificacion que el indice sea mayor a 0
{
cnd = cnd + tabla[cnd] ; // se aumenta el indice con el numero que esta en la tabla
}

cout