Comparison of search algorithms within text strings

12

I'm trying to implement the following algorithms for searching expressions within Java text strings: Knuth-Morris-Pratt (KMP), Brute Force, Boyer-Moore, and Levenshtein

How could you show the similarity obtained to perform a comparison between the algorithms, and see which one offers the best performance?

    
asked by anonymous 07.08.2015 / 04:49

2 answers

1

You can use a prophylactor to test the runtime of the algorithms developed, or you can test the time total execution time.

long start = System.currentTimeMillis();  
//SEU CÓDIGO... pode ser a instância de um objeto também  
long delay = System.currentTimeMillis() - start;  
System.out.println("O tempo de execução foi de: " + delay + " milissegundos");  
    
24.08.2015 / 19:56
1

To compare them, they have to do the same thing, you mentioned "text comparison", but the term is very generic, maybe you want to be editing distance: that is, what is the number minimum addition, removal, and editing operations that are required to exit from the first string to the second string.

That said, if that's your problem, and the algorithms you mentioned solve it. You can compare the algorithms like this: 1) for each pair of algorithms that gave the best answer (in case of a tie), check which one is more efficient, in time and memory; 2) in case of different answers, which gave less number of operations in response (remembering, it must be correct).

Time comparison can be done informally, as suggested by @Maicon Herverton, or more formally using asymptotic analysis.

Memory consumption is a direct result of the size of the data structures you are using in each algorithm.

    
10.12.2015 / 21:04