miércoles, 20 de febrero de 2013

Métodos de Codificación Tarea 2

Buenas en esta ocasión se realizo una simulación utilizando los métodos de búsqueda para palabras.
Se utilizo el algoritmo de boyer-moore y el algoritmo de knuth-morris-pratt.

Algoritmo boyer-moore

Este algoritmo es considerado como uno de los mas eficientes para búsqueda de palabras (en esta entrada demostraremos esta eficiencia comparando con otro método).  Este algoritmo analiza las cadenas de derecha a izquierda.

Proceso:
Matriz de saltos:

  • Se elimina el ultimo elemento de el patrón de palabras
  • Se invierte el patrón
  • Se inserta todos aquellos elementos que no estén en el patrón referente a la cadena de texto


Algoritmo Principal:

  • Se verifica los caracteres de derecha a izquierda, si el primer elemento a verificar si es errónea se realiza el salto con respecto a la matriz de salto
  • Si pasa correctamente se itera de izquierda a derecha sin tomar en cuenta el ultimo elemento del patrón ya que se tomo en el paso anterior
  • Si se equivoca se mueve la cantidad de veces que se itero
Ejecución:




Aquí el código
El algoritmo que se utilizo para comparar el anterior se llama  knuth-morris-pratt

Primeros e calcula un función de arreglos  para poder realizar los diferentes saltos
Para el algoritmo principal se manejara de izquierda a derecha
  • Se calcula la cantidad de iteraciones asta que encuentre la palabra o falle
  • Para identificar el salto se usa la función anteriormente mencionada restando la cantidad de iteraciones, menos la posición con respecto a la iteración final.
  • Se repite el proceso nuevamente
Ejecución:



Aquí el código

Para comprobar cual de ellos es mejor se puso una variable para calcular cuantas iteraciones se realizaban con la misma cantidad de tamaño n y m por medio de una simulación

Aquí los resultados:

Primer algoritmo


Segundo algoritmo


Esto demuestra que el primer algoritmo es mas eficiente ya que no utiliza tantas iteraciones como el segundo

Para la simulación se utilizo código anterior de esta entrada,  al igual que el awk solo que con unos pequeños cambios

Aquí el código de ambos

Gracias por su atención

referencias:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
http://jaked409.livejournal.com/91681.html






1 comentario:

  1. Código bien, 5 pts. El reporte está algo mal estructurado, incoherente y con problemas de ortografía. Lo de complejidad de tiempo sería bueno hacer en términos de la cantidad de comparaciones y además faltó lo de complejidad de espacio. Van 3 pts por el reporte.

    ResponderEliminar