String matching

Programa

• "Program: Implement both BM and KMP in Python"

He implementado dos algoritmos en Python para poder encontrar un patron de caracteres en una cadena.
El primero que hice es el de KMP, para comenzar a hacer este algoritmo lo primero que hay que hacer es una tabla de fallos, esta tabla consiste en no permitir que se examine T (el texto) más de una vez. Esto se puede hacer si se compara un fragmento de la cadena donde se busca con un fragmento de la cadena que se busca, y esto nos da un sitio potencial para que haya una nueva coincidencia.
Ejemplos de Textos y su tabla de fallo:

La palabra a buscar es ANA
La tabla de fallos es [-1, 0, 0]

La palabra a buscar es BCABCBABCABC
La tabla de fallos es [-1, 0, 0, 0, 1, 2, 1, 0, 1, 2, 3, 4]

Después en el algoritmo de KMP teniendo esta tabla cada ves que se examinan las cadenas entre si se usa la tabla de fallos para hacer saltos cuando se localiza un fallo.
Este es el algoritmo que implementé:


Algunas ejecuciones:

Después implemente el algoritmo de Boyer-Moore que el objetivo es el mismo pero lo hace de manera distinta primero procesa la cadena objetivo que esta siendo buscada, generalmente este algoritmo es más rápido mientras la cadena sea más grande.
El código con comentarios:


Este es un ejemplo:

• Design, document, and analyze an experiment to determine the worst-case time complexities of the two.
  

Para esta parte he creado palabras y textos de diferentes tamaños en python para poder analizar como se comporta el algoritmo, genero dos archivos uno que se llama bm.dat y otro que se llama kmp.dat, cada uno tiene en la primera columna la longitud del texto, el la segunda columna la longitud del patron y por último el tiempo de ejecución, este es el código:

Podemos ver que el algoritmo Boyer-Moore tiene un mejor tiempo cuando las cadenas son más largas, Boyer-Moore es más rápido ya que compara las palabras de derecha a izquierda, y tan pronto como se encuentra una carta en el texto que no está presente en el patrón de búsqueda se mueve, lugares m adelante, por lo que para archivos de gran tamaño, es de esperar que muchos de estos movimientos estarían allí por lo que una gran cantidad de caracteres de texto no será accesible ni una sola vez a diferencia de KMP donde se accede a cada letra al menos una vez.

Y en número de comparaciones se ve algo así:

Podemos notar que el Boyer-Moore es más eficiente que el KMP ya que hace mucho menor número de comparaciones. El promedio del KMP es de O(n+m). El algoritmo Boyer-More cuenta con un promedio de tiempo de ejecución de O(nlog(m/n)) (en el mejor caso), en el peor caso es de O(m*n).

Para los experimientos se hicieron 30 repeticiones.

Referencias

KMP
BM