0
$\begingroup$

Suppose I have a very long list of strings (millions of them), ordered by importance. For example:

...
barracudas
oftwalj
velasp
offso
skenep
vitriolic
offscre
...

What is an appropriate data structure for storing this data to make it efficient to obtain all matches of any prefix? For example, I may want to search for the prefix of, which should return oftwalj, offso, offscre, etc. in the order of importance.

Things I have used in the past to solve this problem:

  • Linear search - eventually became too slow as the list became very large.
  • Storing the data in a simple hash table, where the key is the prefix, and the value is the list of words matching the prefix together with their "importance score" - this works, but the space requirement is high.
$\endgroup$
2
$\begingroup$

For a fixed-length prefix, store them in a hash table. For a variable-length prefix, use a trie.

If you have a static list and don't need to support insertions or deletions into the list, storing them in sorted order by lexicographic order also works, as you can use binary search to find the matches (they will all be consecutive).

$\endgroup$
  • $\begingroup$ I cannot sort by lexicological order, because the results need to be returned according to the "importance". $\endgroup$ – Flux Aug 31 at 11:04
  • 2
    $\begingroup$ @Flux, you can store the importance with each string, then once you find all matches, sort them by importance. There are many possibilities. In any case, this does not appear to be a research-level question. $\endgroup$ – D.W. Aug 31 at 11:05
  • $\begingroup$ @Flux You may find this excellent video and relevant notes useful: ocw.mit.edu/courses/electrical-engineering-and-computer-science/… $\endgroup$ – Avi Tal Aug 31 at 13:45

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