algorithm to partition strings by prefix

Question

Given a list of strings L (sorted), and a positive integer N (N <= len(L)), how to efficiently partition L into no more than N groups by common prefix of length N?

Example: define data structure and function as below:

type PrefixGroup struct {
    Prefix string 
    Count  int
}
func partition(L []string, N int, prefix string) []PrefixGroup

The list L may contains thousands of strings, when called with

partition(L, 8, "")

the output may be:

[
    {"Prefix":"13", "Count":1000},
    {"Prefix":"180": "Count": 10},
    {"Prefix":"X": "Count": 2},
    ... ...
]

which means in L, there are 1000 strings start with "13", 10 start with "180" and 2 start with "X". Note that the length of prefix is not fixed. The key requirement of this algorithm is to partition strings with common prefix so that the number of groups is as close as but not exceeding N.

With the result above, I can then call partition(L, 8, "13") to further drill down subset of L that start with "13":

[
    {"Prefix":"131", "Count": 50},
    {"Prefix":"135": "Count": 100},
    {"Prefix":"136": "Count": 500},
    ... ...
]

This is not a homework question. I need to write such an algorithm for a project at hand. I can write it "brute-force"-ly, just wonder if there are any classic/well-known data structure and/or algorithm to achieve proven time/space efficiency.

I have considered trie, but wonder if it may consume too much memory...

It would help if you can specify your space/time requirement and data scale. At a scale of len(L)~1e3, there is no need to write any extra code. — leaf bebop
– leaf bebop, Commented Jan 10, 2018 at 5:11
do you mean "common prefix of length at most N" in the first sentence? — Petar Petrovic
– Petar Petrovic, Commented Jan 10, 2018 at 7:04
@Petar Petrovic, the "at most N" means at most N groups, not the prefix length. — xrfang
– xrfang, Commented Jan 10, 2018 at 7:27
@leaf bebop I will try brute force method first, and do some research on the answers provided here. — xrfang
– xrfang, Commented Jan 10, 2018 at 7:28
@xrfang so "groups by common prefix of length N" means each prefix must have length N? Then why do you have this requirement "the number of groups is as close as but not exceeding N" ? if the length of prefix is fixed, shouldn't number of groups is also fixed? — Petar Petrovic
– Petar Petrovic, Commented Jan 10, 2018 at 7:45

Pavel Nikolov · Accepted Answer · 2018-01-10 05:11:03Z

1

You need to use a Radix trie. You can read about the difference between a trie and a Radix trie.

answered Jan 10, 2018 at 5:11

Pavel Nikolov

9,5715 gold badges46 silver badges55 bronze badges

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

Comments

Remario · Accepted Answer · 2018-01-10 02:06:38Z

Well there are a few algorithms, but prefix tree is to way to go.

A prefix tree, or trie (often pronounced "try"), is a tree whose nodes don't hold keys, but rather, hold partial keys. For example, if you have a prefix tree that stores strings, then each node would be a character of a string. If you have a prefix tree that stores arrays, each node would be an element of that array. The elements are ordered from the root. So if you had a prefix tree with the word "hello" in it, then the root node would have a child "h," and the "h" node would have a child, "e," and the "e" node would have a child node "l," etc. The deepest node of a key would have some sort of boolean flag on it indicating that it is the terminal node of some key. (This is important because the last node of a key isn't always a leaf node... consider a prefix tree with "dog" and "doggy" in it). Prefix trees are good for looking up keys with a particular prefix.

Collectives™ on Stack Overflow

algorithm to partition strings by prefix

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related