Comparison of search algorithms within text strings

Asked

Viewed 322 times

12

I am 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 show the similarity obtained to perform a comparison between the algorithms, and see which offers better performance?

string algorithm
  • 2

    I didn’t understand the brute force to compare text. Furthermore, you can create a list of strings and plot the 'similarity' value of each method for each pair of strings in the list. Maybe compare the running time. If I were to do it, perhaps to begin with I would do each analysis (of each pair) for each method, and I would grade each one according to the standard deviation of the results.

  • The algorithms referred to are not text comparison but rather expression search within a text string. I have already edited.

2 answers

1

To compare them it is necessary that they are willing to do the same thing, you quoted "text comparison", but the term is very generic, maybe what you want is editing distance: ie, what is the minimum number of addition operations, removal and editing that are required to exit the first string to the second.

That said, if that’s your problem, and the algorithms you mentioned solve it. You can compare the algorithms like: 1) for each pair of algorithms that gave the best answer (in case of a tie), check which of it is most efficient, in time and memory; 2) in case of different answers, which gave fewer operations as a response (remembering, it has to be right).

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.

1

You can use a profiler to test the running time of the algorithms developed, or you can test the total running 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");

Browser other questions tagged string algorithm

You are not signed in. Login or sign up in order to post.