jueves, 21 de febrero de 2013

[IT] Homework 2: Coupling text methods: Boyer-Moore & Knuth-Morris-Pratt

Implementation of Knuth-Morris-Pratt and Boyer-Moore algorithms in Python, written by me:


Execution

This is the code to automate all the execution:


Experiment

My initial conditions was:

  • Word length: from 100 to 1000
  • Pattern length: from 2 to 11
  • Repetitions: 30
I made all the posible conditions between these values, iterating the pattern length through each word length, and also running each combination 30 times.

Results


Knuth-Morris-Pratt
TimeComparisons
Boyer-Moore
TimeComparisons


I wrote these codes after understanding the following examples:

  • http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
  • http://www-igm.univ-mlv.fr/~lecroq/string/node8.html 
  • http://www-igm.univ-mlv.fr/~lecroq/string/node14.html

1 comentario:

  1. Yo hubiera esperado un preprocesamiento explícito en KMP y algunas conclusiones, pero está bien esta vez. 5+5.

    ResponderEliminar