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
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.