I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set.
For instance, if my set is:
abracadabra abracado abramu banana bananasplit bananaicecream xylophone zebra zeitgeist zello
I would want the output to be:
banana (len 6, matches 3) abra (len 4, matches 3) xylophone (len 9, matches 1) ze (len 2, matches 3)
Now, this question isn't yet properly specified. That's because I'm ranking my results on two dimensions: maximum matches, and maximum length. My goal is to find prefixes that cover as much as of the set as possible, which are as long as possible and thus less likely to occur in strings that aren't in the set (all other things being equal, of course).
Ideally, I'd like to find a set of very long strings, ranked by how much of the set they cover.
That's my goal. Now I'll present my work, and where I need help.
FIRST Let's specify the problem better. We want a set of prefixes. For each prefix, we compute its length, and the number of matches it has in the set, and order the prefixes by their product. I'm then free to pick the top X prefixes.
I think that's a good specification.
NOW Comes an efficient implementation. Brute force is to check every possible prefix against every string, which is complexity n * n * m (n being number of strings, m being average length of strings).
An efficient algorithm?
Something like this:
- Build a prefix tree of the set
- Each leaf has value 1
- Work up the tree, with each parent equal to sum of its children , plus 1 if it has an entry
- Now we know each prefix and how many matches it has - I believe complexity is n log n
- Walk through the tree, counting length of each string (complexity n * m)
- And collect all the entries, sort them by length * value (complexity n log n)
That algorithm is roughly n log n, which is efficient enough. Will it work? How should it be improved? What's a simple way to implement it?
Finally: Since all the data is in a Postgres relational database, I believe it would be simplest to do the algorithm using relational algebra with aggregate functions. Comments on this?