12 The Knuth Morris Pratt Algorithm(ok).doc 5a5s3z

Facultad de Producción y Servicios

ESCUELA PROFESIONAL DE INGENIERIA DE SISTEMAS TEMA 09 (32.4)

“The Knuth-Morris-Pratt algorithm” DOCENTE: Mg. Carlo Corrales Delgado

ALUMNOS: -CONDORI HUARCA ANDRES -QUISPE SOTO DARWIN -TICONA PINTO ARTURO

A

UNS

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN

AREQUIPA – PERÚ 2017

1

Algoritmo Knuth-Morris-Pratt 1.- Introducción Al igual que fuerza bruta este algoritmo busca una subcadena dentro de una cadena principal. 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. En el siguiente trabajo se explicará el funcionamiento, implementación del algoritmo utilizando el lenguaje Java y su análisis de costo computacional. Finalmente, se tendrá una comparación de este algoritmo frente a otros conocidos mediante gráficas para poder visualizar la eficiencia de este algoritmo para la búsqueda de patrones.

2.- Descripción Este algoritmo busca sub cadenas dentro de una cadena. Éste se apoya en una tabla llamada "Tabla de fallos", en la cual se guarda información de la cadena a buscar con el objetivo de que cada carácter en el texto sea comparado sólo una vez. La mejora que muestra este algoritmo respecto al de fuerza bruta (comparar cada elemento del patrón a buscar con cada elemento del texto), es que aprovecha información que tiene la cadena que será buscada dentro de sí misma. Cuando ocurre un fallo en la comparación entre ésta y el texto, se da una cierta cantidad de saltos para que ningún elemento de él sea analizado más de una vez. Partiendo del texto a buscar, elaboramos una lista con todas las posiciones, de salto atrás que señalen cuánto se retrocede desde la posición actual del texto a buscar. Ejemplo de Funcionamiento a grandes rasgos KMP

3.- Desarrollo 2

El algoritmo KMP consta de dos partes una tabla de fallos y la función KMP que compara el texto con el patrón. 3.1 Función de Fallo Crea el arreglo que será utilizado como tabla de fallos. A medida que se recorre el patrón, el algoritmo va buscando ocurrencias de algún prefijo del mismo y guardando en el arreglo la longitud de la ocurrencia más larga hasta la posición anterior. Así, al acceder a la tabla se sabe la cantidad de caracteres que se pueden reutilizar, además de la posición en el patrón desde donde debe continuar la búsqueda. 3.1.1 Tabla de Fallos (conocida como 'función de fallo') El objetivo de la tabla (pre calculada) 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. Por tanto, esta tabla se confecciona con la distancia que existe desde un punto en la palabra a la última ocurrencia distinta de la primera vez que aparece, y mientras sigan coincidiendo, se marca la distancia, cuando haya una ruptura de coincidencia se marca 0 o un valor previo ya calculado anteriormente, y así sucesivamente hasta terminar con el texto. 3.2 función KMP (String pattern) Realiza una búsqueda del patrón dado siguiendo el algoritmo explicado en la descripción. Al encontrar un match, se incrementa el contador de ocurrencias (no nos interesa cuales son en nuestro análisis) y se continua tal como si hubiera ocurrido un error (es decir, moviendo los punteros del texto y el patrón según la tabla de fallos), lo que permite reutilizar un sufijo del patrón como prefijo de una nueva posible ocurrencia, si el patrón lo permite.

3.3 METODO 1 3.3.1 Casos para conseguir la función de fallo Caso 1: Sin patrón y la letra de fallo del patrón es la misma que la inicial Ejemplo P= abca S= a b c Z ? ? P= a b c A a b

? c

Situar el inicio del patrón tras el carácter de fallo. Se representa con -1 en la tabla de fallos Caso 2: Sin patrón y letra de fallo del patrón es distinta al valor inicial. Ejemplo 3

a

P= abcd S= P=

a a

b b

c c

? ? ? ? d a b c d El ultimo termino no es una d, pero puede ser una a. Situar el inicio del patrón en el carácter de fallo y volver a comprobar desde ese nuevo inicio. Se representa con 0 en la tabla de fallos.

Caso 3: Hay patrón y la letra siguiente al patrón de la izquierda es diferente al carácter de fallo Ejemplo P = XYXYY S= X Y X Y ? ? ? P= X Y X Y Y X Y X Y Situar el inicio del patrón m posiciones a la izquierda del carácter del fallo, donde m es el tamaño del patrón. Se representa con el tamaño m en la tabla de fallos. Caso 4: Hay patrón y la letra siguiente al patrón de la izquierda es igual al carácter de fallo S= X Y X Y ? ? ? P= X Y X Y X X Y X Y No tiene sentido este movimiento porque sabemos que este movimiento va a fallar. Entonces se hace los siguiente S= X Y X Y ? ? ? P= X Y X Y X X Y X

Y

Se sitúa el inicio del patrón donde lo situaría la letra siguiente al patrón de la izquierda. Se representa con el valor del siguiente carácter a la izquierda del patrón. 3.3.2 Explicación del Funcionamiento. Para la Tabla de Fallos Se P el patrón = ABCABCACAB Siempre buscar el patrón más largo talque el patrón de la izquierda debe empezar en la posición 0 y el patrón de la derecha debe acabar posición n-1(anterior) al carácter de fallo. Posición Patrón siguiente

0 A

1 B

2 C

3 A

4 B

5 C

6 A

7 C

8 A

9 B

Posición 0 El primer carácter siempre lleva el valor -1, pues si falla solo se recorre una posición para probar el valor inicial. Posición 0 1 2 3 4 5 6 7 8 9 4

Patrón siguiente

A -1

B

C

A

B

C

A

C

A

B

Posición 1 No hay patrón, el carácter de fallo es distinto a valor inicial, entonces estamos en el caso 2. Entonces procedemos a colocar el valor 0. Posición 0 1 2 3 4 5 6 7 8 9 Patrón A B C A B C A C A B siguiente -1 0 Posición 2 No hay patrón, el valor de fallo es diferente del valor inicial (C ≠ A o P[2] ≠ P[0]), Caso 2 Posición 0 1 2 3 4 5 6 7 8 9 Patrón A B C A B C A C A B siguiente -1 0 0 Posición 3 No hay patrón, el valor de fallo es igual al valor inicial (A = A o P[3] = P[0]), Caso 1 Posición 0 1 2 3 4 5 6 7 8 9 Patrón A B C A B C A C A B siguiente -1 0 0 -1 Posición 4 Hay Patrón de tamaño m=1, el siguiente valor al patrón es igual al valor de fallo (B = B o P[1] = P[4]). Caso 4 Posición 0 1 2 3 4 5 6 7 8 9 Patrón A B C A B C A C A B siguiente -1 0 0 -1 0

Posición 5 Hay patrón de tamaño m=2, el siguiente valor al patrón es igual al valor de fallo (C=C o P[2]=P[5]), Caso 4 Posición 0 1 2 3 4 5 6 7 8 9 Patrón A B C A B C A C A B siguiente -1 0 0 -1 0 0 Posición 6 Hay patrón de tamaño m=3, el siguiente valor al patrón es igual al valor de fallo (A=A o P[3]=P[6]), Caso 4 Posición Patrón siguiente

0 A -1

1 B 0

2 C 0

3 A -1

4 B 0

5 C 0 5

6 A -1

7 C

8 A

9 B

Posición 7 Hay patrón de tamaño m=4, el siguiente valor al patrón es diferente al valor de fallo (P[4]≠P[7]), Caso 3 Posición 0 1 2 3 4 5 6 7 8 9 Patrón A B C A B C A C A B siguiente -1 0 0 -1 0 0 -1 4 Posición 8 No hay patrón, el valor inicial es igual al valor de fallo (P[0]=P[8]) caso 1 Posición 0 1 2 3 4 5 6 7 Patrón A B C A B C A C siguiente -1 0 0 -1 0 0 -1 4

8 A -1

9 B

Posición 9 Hay patrón de tamaño m=1, el siguiente valor al patrón es igual al valor de fallo (P[1] = P[9]), Caso 4 Posición 0 1 2 3 4 5 6 7 8 9 Patrón A B C A B C A C A B siguiente -1 0 0 -1 0 0 -1 4 -1 0 3.3.3 Buscar el Patrón con la Cadena C= ABCABCAAABABCABABCABCACAB Tabla de Fallos Posición 0 1 2 3 4 Patrón A B C A B siguiente -1 0 0 -1 0

5 C 0

6 A -1

7 C 4

8 A -1

9 B 0

Empezamos a comparar i

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 C A B C A B C A A A B A B C A B A B C A B C A C A B P A B C A B C A C En la posición 7 no hay coincidencia, entonces en la posición 7 del patrón verificamos que valor acumula. En este caso es 7 por lo tanto la cadena retrocede 7(posición en el fallo) – 4(valor en la tabla de fallo) = 3, entonces de la posición 3 empieza a comparar nuevamente.

i

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 C A B C A B C A A A B A B C A B A B C A B C A C A B P A B C A B 6

Ahora nuevamente se da un fallo en la posición 7, ahora verificamos que valor contiene esa letra en la que fallos y es la posición 4 de la tabla de fallos y contiene 0, entonces toda la cadena recorre a la posición donde ocurrió el fallo, para empezar a comparar nuevamente. i

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 C A B C A B C A A A B A B C A B A B C A B C A C A B P A B Ahora se da un fallo en la posición 8, pero para el patrón es la posición 1 que contiene a B, y contiene un valor de 0 en la tabla de fallo, entonces todo el patrón ce mueve hacia la posición 8. y nuevamente comparamos. i 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 C A B C A B C A A A B A B C A B A B C A B C A C A B P A B C Un nuevo fallo en la posición 10, y para el patrón es la posición 2 y en su tabla de fallos contiene un 0, por lo tanto, nuevamente recorreos todo el patrón hacia la posición 10 para empezar a comparar. i 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 C A B C A B C A A A B A B C A B A B C A B C A C A B P A B C A B C Ahora el fallo se da en la posición 15, y para el patrón es la posición 5 y en su tabla de fallos contiene un 0, por lo tanto, todo el patrón se mueve hacia la posición 15 para empezar a comparar. i

0

1

2

3

4

5

6

7

8

9

1 0

1 1

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

2 0

2 1

2 2

2 3

2 4

C A B C A B C A A A B A B C A B A B C A B C A C A B P A B C A B C A C A B Encontró el patrón en la cadena y ahí finaliza y para este ejemplo ahí Finaliza.

3.4 METODO 2 3.4.1 Explicación del Funcionamiento. Para la Tabla de Fallos Otro método para hallar la matriz de fallos es inicializando al primer elemento de la matriz en 0. Y hallando el resto comparando el contenido de la posición siguiente con la anterior. 7

 Por ejemplo el siguiente patrón: ABCDABD se calculara de la siguiente forma: j

0



1

2

3

4

5

6

p[j]

A



B

C

D

A

B

D

f[j]

0



 Luego se comparara el siguiente valor con el anterior si son iguales el valor de la matriz de fallo en esa posición será igual al de la posición j aumentado en 1 y si no lo son j tomara el valor anterior almacenado en la matriz j=f[j-1] y volverá a comparar el contenido con la siguiente posición. j

0



1

2

3

4

5

6

p[j]

A



B

C

D

A

B

D

f[j]

0



j

0



1

2

3

4

5

6

p[j]

A



B

C

D

A

B

D

f[j]

0



j

0



1

2

3

4

5

6

p[j]

A



B

C

D

A

B

D

f[j]

0



j

0



1

2

3

4

5

p[j]

A



B

C

D

A

B

f[j]

0



j

0



1

2

3

4

5

p[j]

A



B

C

D

A

B

f[j]

0



0

0

0

0

0

0

0

0

0

0

8

(j=0)=>(j+1)=1

1

j+1=2

j

0



1

2

3

4

5

6

p[j]

A



B

C

D

A

B

D

f[j]

0



0

0

0

1

2

 Si al momento de comparar los contenidos estos no son iguales y j>0 (en este caso j=2= c) entonces j será igual al valor de su posición -1 es decir j=f[j-1] => j= f[0] y nuevamente compara. j

0



1

2

3

4

5

6

p[j]

A



B

C

D

A

B

D

f[j]

0



0

0

0

1

2

0

 Si nuevamente no son iguales pero j=0 entonces la matriz en esa posición (D) tomara el valor de 0. 3.4.2 Buscar el Patrón con la Cadena con la matriz de fallo i recorrerá la cadena principal mientras que j el patrón a buscar ambos inicializan en 0 i

0

1

2

3

4

5

6

7

8

9

10 11

Cad A B C A B C D A B Pat A B C D A B D

A

12 13 14 15 16 17 18 19 20 21 22 B

C

D

A

B

C

D

A

B

D

E

 Matriz de fallos i 0 P[i] A F[i] 0 i

0

1

2

3

4

5

6

7

8

1 B 0

2 C 0

3 D 0

9

10 11

Cad A B C A B C D A B Pat A B C D A B D

A

4 A 1

5 B 2

6 D 0

12 13 14 15 16 17 18 19 20 21 22 B

C

D

A

B

C

D

A

B

D

E

En caso de error j tomara el valor de la matriz de fallos en j= F[j-1] => j=0 i quedara igual. i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Cad A B C A B C D A B Pat A B C D A B D

A

B

C

D

A

B

 En caso de que haya error y j =0 entonces solo i avanza y j se mantiene en 9

C

D

A

B

D

E

i

0

1

2

3

Cad A B C Pat

4

5

6

7

8

9

10 11

A B C D A B A B C D A B D

A

12 13 14 15 16 17 18 19 20 21 22 B

 Nuevamente j tomara el valor de la matriz en j=f[j-1] comparar desde esa posición. i

0

1

2

3

Cad A B C Pat

4

5

6

7

8

9

10 11

A B C D A B A B C

A D

C

D

A

B

C

D

A

B

D

E

j=2; y empezara nuevamente a

12 13 14 15 16 17 18 19 20 21 22 B A

C B

D D

A

B

C

D

A

B

D

E

 j tomara la el valor de la matriz nuevamente siendo este j=0, i

0

1

2

3

Cad A B C Pat

4

5

6

7

8

9

10 11

A B C D A B A

A B

12 13 14 15 16 17 18 19 20 21 22 B C

C D

D A

A B

B D

C

D

A

B

D

E

 i avanza y j se mantiene en 0 i

0

1

2

3

Cad A B C Pat

4

5

6

7

8

9

10 11

A B C D A B

A A

12 13 14 15 16 17 18 19 20 21 22 B B

C C

D D

A A

B B

C D

D

A

B

D

E

j=2 y compara desde esa posición: i

0

1

2

Cad A B C Pat

3

4

5

6

7

8

9

10 11

A B C D A B

A

12 13 14 15 16 17 18 19 20 21 22 B

C

D

A A

B B

C C

D D

A A

 Al ser j igual al tamaño de patrón disminuido en 1 el algoritmo acaba dando como resultado la posición de donde fue encontrado el patrón es decir i-j. (21-6= 15) 3.5 Pseudocódigo General Del libro Introduction to Algorithms 3.5.1 Pseudocodigo Función-Fallo

10

B B

D D

E

3.5.2 Pseudocodigo Función KMP

3.6 Algoritmo Implementado para el Método 1

11

3.7 Algoritmo implementado para el Método 2

12

13

4 Análisis del algoritmo (Código del método 1 – implementación del pseudocódigo del libro Cormen) Los procedimientos FUNCION-FALLO y KMP tienen mucho en común, ya que ambos coinciden con una cadena contra el patrón P, KMP coincide con el texto T contra P, y FUNCION-FALLO con P contra sí mismo. 4.1 Análisis del tiempo de Ejecución FUNCION-FALLO El tiempo de ejecución de FUNCION-FALLO es Ѳ (m), que se muestra utilizando el método agregado de análisis amortizado La única parte difícil es mostrar que el bucle while de las líneas 6-7 ejecuta O(m) veces en total. Mostraremos que hace como máximo m - 1 iteraciones. Comenzamos haciendo algunas observaciones sobre k. En primer lugar, la línea 4 comienza k = 0, y la única forma en que k aumenta es mediante la operación de incremento en la línea 9, que se ejecuta como máximo una vez por iteración del bucle for de las líneas 5-10. Por lo tanto, el incremento total en k es como máximo m -1. En segundo lugar, puesto que k < q al entrar en el bucle for y en cada iteración de los incrementos de bucle q, siempre tenemos k < q. Por lo tanto, las asignaciones en las líneas 3 y 10 aseguran que π|q| < q para todo q = [1, 2,3, . . ., m] lo que significa que cada iteración del bucle while disminuye k. Tercero, k nunca llega a ser negativo. Haciendo estos hechos juntos, vemos que la disminución total en k del bucle while está limitada desde arriba por el incremento total en k sobre todas las iteraciones del bucle for, que es m - 1. Por lo tanto, el bucle while itera como máximo m - 1 veces en total, y COMPUTE-PREFIXFUNCTION se ejecuta en el tiempo Ѳ (m). 4.2 Análisis del tiempo de Ejecución FUNCION KMP El análisis de ejecución de la función KMP es similar a la de la función de fallo. Iniciamos evaluando que q inicia en 0 linea 4, su única forma de aumentar es mediante el la condiciona IF que esta en el bucle FOR (línea 5-12). Por lo tanto el máximo valor de q es n-1 (tamaño de la cadena o texto). En segundo lugar, puesto que q < i al entrar en el bucle for y en cada iteración de los incrementos de bucle q, siempre tenemos k < q. Por lo tanto, las asignaciones en las líneas 5 y 12 aseguran que π|q| < i para todo q = [1, 2,3, . . .,n] lo que significa que cada iteración del bucle while disminuye q. q nunca llega a ser negativo, Haciendo estos hechos juntos, vemos que la disminución total en q del bucle while está limitada desde arriba por el incremento total en q sobre todas las iteraciones del bucle for, que es n - 1. Entonces el llamado a la función de fallo (línea 3) tiene un peso m y la propia función KMP tiene un peso n, esto da un costo m+n => Ѳ( n+ m).

5 Análisis de graficas 14

A continuación se verá la rapidez del algoritmo KMP con respecto a otros dos algoritmos bastante conocidos como los son el de fuerza bruta el BMH  Para el resultado de las gráficas se toma como prueba la ejecución de los algoritmos en 3 distintos casos de aplicación en alfabetos: binario, leguaje inglés y en una simulación de prueba de ADN. 5.1.1 Alfabeto Binario Para el caso del alfabeto Binario la cantidad de caracteres que posee es bastante reducida, ya que solo son 2, lo cual hace que la probabilidad de repetición de estos sea bastante elevada con respecto a los otros dos lenguajes. Sin embargo aun así el tiempo del KMP es mucho mejor.

5.1.2 ADN En el caso del ADN se puede ver que el tiempo tomado es bastante similar entre el caso real y sintético, pero este último tiende a ser mayor. Esto puede deberse a la forma en que se construye el ADN, con secuencias definidas que en ocasiones tienen posiciones determinadas en una cadena (como un marcador de inicio o fin), lo que hace poco probable que en una cadena real hayan 15

segmentos que puedan ser “reutilizados” para formar otra posible ocurrencia, produciéndose así fallos más frecuentes y saltos más largos.

5.1.3 Lenguaje Ingles

6

Conclusiones 16

1. El tiempo de ejecución del algoritmo KMP es óptimo (O (m + n)), que es muy rápido. 2.

El algoritmo nunca necesita moverse hacia atrás en el texto de entrada T. Hace que el algoritmo sea bueno para procesar archivos muy grandes.

3. el lenguaje real las palabras se escriben usando letras de forma particular, con vocales cada

cierta frecuencia, silabas comunes, lo que hace que la búsqueda pueda llegar a dar saltos mas grandes, a diferencia en cadenas de ADN, números binarios. 4. Imprescindible en gran número de aplicaciones:  Procesadores de textos,  utilidades como el grep de unix,  programas de recuperación de información textual,  programas de búsqueda en catálogos de bibliotecas,  buscadores de internet,  lectores de news en internet,  bibliotecas digitales,  revistas electrónicas,  directorios telefónicos,  enciclopedias electrónicas,  búsquedas en bases de datos de secuencias de ADN o ARN.

1

6 Referencias 17

[1] Introducction to Algorithms 3 edition. Thomas H. Cormen, Charles E. Leiserson. Ronald L. Rivest, Clifford Stein [2] Knuth.Morris-Pratt Algorithm: An analisis, Mireille Regnier [3] Algoritmos in Bioinformatics [4]Análisis de algoritmos de Busqueda de un solo patrón, Sergio Talens-Ollag [5]Búsqueda en Texto, Moreno Edward y Rubilar Felipe [6] https://www.youtube.com/watch?v=Kglp2Sy5dr0: : Algoritmia- Tema 3: Algoritmos de Búsqueda KMP, Muños Ortega Andrés UCAM - Universidad Católica de Murcia

18