1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ According to the link you provided, a suffix array is used to find a substring of a single string. Are you suggesting I consider the set of several thousand longish strings as a single string and compute all suffixes on the set? $\endgroup$ – Dave S. Mar 31 at 21:08
  • $\begingroup$ @DaveS., see edited answer. $\endgroup$ – D.W. Mar 31 at 23:01
0
$\begingroup$

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.

  1. What is the balance between searching, adding and deleting? I assumed that searching is a lot more common that adding/deleting.
  2. 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.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.