Assignment 2: Experiment for KMP & BM

For homework in the subject Information Theory, we need to do un experiment to check how is the performance between different algorithms that can search in a text, different patterns.

For do this experiment I made both algorithms in Python, then I put a sub procedure that repeat 30 times, change the value for how long are the pattern, the text and the amount of letters that we use to choose for have different prospective about how the algorithm works, it is important to know that for do the patters I use a function that do string random and also create a pattern randomly.

First at all, the following image you can see a map color where we can find 3 different values plotted, how long is the pattern, how long is the text that we check with the pattern and, finally I put a variable that checks the time that the computer wait for do the search, then when the algorithm finish I return this value and I used for have an estimation with the time.

In this image, you can see that if we have a pattern that are just for 1 to 4 letters, we have an algorithm that can do the search and in a time (that is plot in color) and there is a point that have the color almost red, which means that we have problems with the time to do the search of the pattern, but is just in some search, because in the following map of the next algorithm BM, we have more stress but down for the medium.

In this other map, we have that there is not stress as the another algorithm, because we do not have points where the time are up of the medium, but we have more points in purple, which means that we have a lot stress and up for medium.

This is another test, when we can see that BM algorithm is more purple, so, takes more time to search the words.

This is the code:

Plot in gnuplot