I have a set of several thousand strings of max length 1024 (containing all visible ASCII chars plus space) I need to store to make it fast to search for an exact match of a key. What is the best algorithm to store the set and to search for a match?
One approach is to use a suffix array (or suffix tree). That allows very fast searching for a match.
Given multiple words, there is a standard way to compute a suffix array (or suffix tree) associated with them: concatenate them, separated by some separator. For instance, if the words are APPLE, CAT, and DOG, you obtain the string APPLE\$CAT\$DOG\$. Then, compute the suffix array/tree of that single long string.
One solution that pops to my mind is to do a hash on the strings, store the hashes in some efficient tree and the hits as a list. A suitable hash algorithm might decrease the number of actual string searches. Additionally given a good hash algorithm you might only need to check a few chars.
On second thought, there are two further things to consider when selecting algorithm.
- What is the balance between searching, adding and deleting? I assumed that searching is a lot more common that adding/deleting.
- Where does the strings differ? If they in average all are about the same length and all start with a few hundred characters the same in the beginning it might influence your choice.