What is the fastest substring search algorithm?

by

Build up a test library of likely needles and haystacks. Profile the tests on several search algorithms, including brute force. Pick the one that performs best with your data.

Boyer-Moore uses a bad character table with a good suffix table.

Boyer-Moore-Horspool uses a bad character table.

Knuth-Morris-Pratt uses a partial match table.

Rabin-Karp uses running hashes.

They all trade overhead for reduced comparisons to a different degree, so the real world performance will depend on the average lengths of both the needle and haystack. The more initial overhead, the better with longer inputs. With very short needles, brute force may win.

Edit:

A different algorithm might be best for finding base pairs, english phrases, or single words. If there were one best algorithm for all inputs, it would have been publicized.

Think about the following little table. Each question mark might have a different best search algorithm.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

This should really be a graph, with a range of shorter to longer inputs on each axis. If you plotted each algorithm on such a graph, each would have a different signature. Some algorithms suffer with a lot of repetition in the pattern, which might affect uses like searching for genes. Some other factors that affect overall performance are searching for the same pattern more than once and searching for different patterns at the same time.

If I needed a sample set, I think I would scrape a site like google or wikipedia, then strip the html from all the result pages. For a search site, type in a word then use one of the suggested search phrases. Choose a few different languages, if applicable. Using web pages, all the texts would be short to medium, so merge enough pages to get longer texts. You can also find public domain books, legal records, and other large bodies of text. Or just generate random content by picking words from a dictionary. But the point of profiling is to test against the type of content you will be searching, so use real world samples if possible.

I left short and long vague. For the needle, I think of short as under 8 characters, medium as under 64 characters, and long as under 1k. For the haystack, I think of short as under 2^10, medium as under a 2^20, and long as up to a 2^30 characters.

More Related Contents:

  1. Fast way to tokenize a string in c
  2. C++ string::find complexity
  3. Print all the permutations of a string in C
  4. Does C have any tools for doing string addition?
  5. A possible algorithm for determining whether two strings are anagrams of one another? [closed]
  6. Recursive and non-recursive traversal of three degree tree
  7. ‘ ‘, ‘\n’ , scanf() and output screen
  8. What is the difference between palindrome permutation and permutation? [closed]
  9. how to show time performance for merge sort? [closed]
  10. How do I concatenate const/literal strings in C?
  11. How to convert a string to integer in C?
  12. How do I trim leading/trailing whitespace in a standard way?
  13. Using the equality operator == to compare two strings for equality in C [duplicate]
  14. How to reverse a singly linked list using only two pointers?
  15. Reading string from input with space character? [duplicate]
  16. Unique random number generation in an integer array [duplicate]
  17. Calculating factorial of large numbers in C
  18. How to convert integer to string in C? [duplicate]
  19. How can I compare strings in C using a `switch` statement?
  20. Power by squaring for negative exponents
  21. Remove text in-between delimiters in a string (using a regex?)
  22. C – Difference between “char var[]” and “char *var”?
  23. Why does strchr take an int for the char to be found?
  24. How to extract numbers from string in c?
  25. How to check if a string is a number?
  26. How to format strings using printf() to get equal length in the output
  27. Literal string initializer for a character array
  28. How does strcmp() work?
  29. Why do strings in C need to be null terminated?
  30. Counting words in a string – c programming

Leave a Comment