文字列を辞書的にグループ化する（Python）

Question

私は、字句解析をM個のバケット（+/- 1文字列）に分割したいN個の文字列を持っています。また、N >> M。

直接的な方法は、すべての文字列をソートし、結果のリストをM個のバケットに分割することです。

代わりに、完全なリストが利用可能になる前に、作成された各文字列をバケットにルーティングすることでこれを近似したいと思います。

文字列をバケットに割り当てる高速かつ分化した方法はありますか？私は本質的に、整数のモジュロ演算子の文字列に相当するものを探しています。おそらく、辞書順を維持するハッシュですか？それも可能ですか？

Answer 1

文字列の最初の2文字、またはこの並べ替えの何かを並べ替えることができます。

のは、あなたがsqrt(M)領域に文字を分割する必要があり、それぞれが別のsqrt(M)地域を指している必要がありますのでM=100は、その後、あなたが得る各文字列のために、あなたが文字列を指示するためにどの領域を決定する最初の文字を比較することができますことを言ってみましょう2番目の文字については、バケットを葉に、比較をノードとして持つツリーのようなものです。

Answer 2

定義によるハッシュは順序を保持しません。

私はこれを行うためのpythonic方法はないと思います。

基本的にハッシュ関数である辞書を作成し、各ラウンドロビンスタイルに文字列を追加することはできますが、順序は保持されません。