# Algorithm for determining minimal set of covering prefixes

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

• And, I should ask: Are there any standard algorithms or approaches to this problem? Is this equivalent or similar to any classical problem? – S. Robert James Jan 10 '13 at 13:35
• One more thing: This is similar to minimal set cover, except a) it's prefix cover, not set cover and b) want long prefixes which cover lots but not all of the set – S. Robert James Jan 10 '13 at 13:37

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