Efficient algorithm for grouping array of strings by prefixes

Question

I wonder what is the best way to group an array of strings according to a list of prefixes (of arbitrary length). For example, if we have this:

prefixes = ['GENERAL', 'COMMON', 'HY-PHE-NATED', 'UNDERSCORED_']

Then

tasks = ['COMMONA', 'COMMONB', 'GENERALA', 'HY-PHE-NATEDA', 'UNDERESCORED_A', 'HY-PHE-NATEDB']

Should be grouped this way:

[['GENERALA'], ['COMMONA', 'COMMONB'], ['HY-PHE-NATEDA', 'HY-PHE-NATEDB'], ['UNDERESCORED_A'] ]

The naïve approach is to loop through all the tasks and inner loop through prefixes (or vice versa, whatever) and test each task for each prefix.

Can one give me a hint how to make this in a more efficient way?

Maybe a LINQ 'group by' is what you're after: richardbushnell.net/2008/02/08/… — lcryder
– lcryder, Commented May 13, 2014 at 17:04
@lcryder LINQ is a definitely a thing you should use in such cases if your are coding in a language where such thing like LINQ exists. But this is not an algorithm after all ))) — shabunc
– shabunc, Commented May 13, 2014 at 17:05

Chris Taylor · Accepted Answer · 2014-05-14 02:40:16Z

2

There are a few options, but you might be interested in looking into the trie data structure. http://en.wikipedia.org/wiki/Trie

The trie data structure is easy to understand and implement and works well for this type of problem. If you find that this works for your situation you can also look at Patricia Tries which achieve the similar performance characteristics but typically have better memory utilization. They are a little more involved to implement but not overly complex.

edited May 14, 2014 at 2:40

answered May 13, 2014 at 17:06

Chris Taylor

53.8k10 gold badges81 silver badges92 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nico Schertler Over a year ago

To complete the answer: You could build a trie for the prefixes and then for each word traverse the trie. If you find a complete word on the way, that's your prefix. You could put a hash set for the words at the leaf node of the trie.

shabunc Over a year ago

@NicoSchertler, oh, OK, I give it a trie )))

M Oehm · Accepted Answer · 2014-05-13 17:29:41Z

1

It depends a bit on the size of your problem, of course, but your naive approach should be okay if you sort both your prefixes and your tasks and then build your sub-arrays by traversing both sorted lists only forwards.

answered May 13, 2014 at 17:29

M Oehm

29.2k3 gold badges36 silver badges44 bronze badges

Collectives™ on Stack Overflow

Efficient algorithm for grouping array of strings by prefixes

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related