文字列L（ソート済み）のリストと正の整数N（N <= len（L））が与えられた場合、長さNの共通接頭辞によってLを効率的にN以下のグループに分割する方法は？
例：データ構造と機能を次のように定義します。
type PrefixGroup struct {
Prefix string
Count int
}
func partition(L []string, N int, prefix string) []PrefixGroup
リストLに何千もの文字列を含めることができます。
partition(L, 8, "")
出力は次のようになります。
[
{"Prefix":"13", "Count":1000},
{"Prefix":"180": "Count": 10},
{"Prefix":"X": "Count": 2},
... ...
]
つまり、Lには、「13」で始まる1000個のストリング、「180」で始まる10個のストリング、および「X」で始まる2個のストリングがあることを意味します。プレフィックスの長さは固定されていないことに注意してください。このアルゴリズムの重要な要件は、共通のプレフィックスで文字列をパーティション分割して、グループの数をNと同じかそれより多くしないようにすることです。
上記の結果で、次に呼び出しpartition(L, 8, "13")て、「13」で始まるLのサブセットをさらにドリルダウンできます。
[
{"Prefix":"131", "Count": 50},
{"Prefix":"135": "Count": 100},
{"Prefix":"136": "Count": 500},
... ...
]
これは宿題ではありません。私は手元のプロジェクトのためにそのようなアルゴリズムを書く必要があります。私はそれを「力ずく」で書くことができます。証明された時間/空間効率を達成するための古典的/よく知られたデータ構造やアルゴリズムがあるかどうかだけです。
私は考えましたがtrie、それはあまりにも多くのメモリを消費するのではないかと思います...
基数トライを使用する必要があります。トライと基数トライの違いについて読むことができます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加