Algorithm for determining minimal set of covering prefixes

Question

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:

1. Build a prefix tree of the set
2. Each leaf has value 1
3. Work up the tree, with each parent equal to sum of its children , plus 1 if it has an entry
4. Now we know each prefix and how many matches it has - I believe complexity is n log n
5. Walk through the tree, counting length of each string (complexity n * m)
6. 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?

Answer 1

Your algorithm will work. The information you will be looking for can be found in the prefix tree (trie) will hold the information you are looking for.

Despite similarity in names, the set cover and this problem are not similar. The first is NP-Hard. This one is not.

However (in relation to Point 3 of your algorithm), a tree node that is not a leaf may be the end of a word $w$ contained in other words (e.g. "be" contained in "bee" "behavior" etc .. ). You should take into consideration when counting.

Point 4: Now we know each prefix and how many matches it has - I believe complexity is $n \log n$ .. why ? I dont think so. It is $O(n m)$.

Point 6: I dont know though why you want to sort. You can find the max (which is $O(n)$).

If you are going to present the tree in a relational database, then make sure you present it in a good way. For instance, try to make the whole tree in a single page, or close nodes in the tree in the same page. This is to minimize the I/O cost. How to do that ? I honestly don't know. For me, I would just put it the prefix tree in a single binary file. Or a seriazable data structure.