Efficient most common suffix algorithm?
- by taw
I have a few GBs worth of strings, and for every prefix I want to find 10 most common suffixes. Is there an efficient algorithm for that?
An obvious solution would be:
Store sorted list of <string, count> pairs.
Identify by binary search extent for prefix we're searching.
Find 10 highest counts in this extent.
Possibly precompute it for all short prefixes, so it doesn't ever need to look at large portion of data.
I'm not sure if that would actually be efficient at all. Is there a better way I overlooked?
Answers must be real time, but it can take as much preprocessing as necessary.