テラバイトのファイルまたは文字列で最も頻繁に使用される単語を10個見つける必要があるという問題に遭遇しました。
私が考えることができた1つの解決策は、最大ヒープとともにハッシュテーブル（単語、カウント）を使用することでした。ただし、単語が一意である場合にすべての単語を適合させると、問題が発生する可能性があります。異なるノードでチャンクを分割することにより、Map-Reduceを使用する別の解決策を考えました。別の解決策は、すべての単語のTrieを作成し、ファイルまたは文字列をスキャンするときに各単語の数を更新することです。
上記のどれがより良い解決策でしょうか？最初の解決策はかなり素朴だと思います。
使用可能なメモリを2つに分割します。1つを4ビットのカウントブルームフィルターとして使用し、残りの半分をカウント付きの固定サイズのハッシュテーブルとして使用します。ブルームフィルターのカウントの役割は、まれにしか発生しない単語を高いメモリ効率でフィルターで除外することです。
最初に空だったブルームフィルターに対して1TBの単語を確認します。単語がすでに入っていて、すべてのバケットが最大値の15に設定されている場合（これは部分的または全体的に誤検知である可能性があります）、それを通過させます。そうでない場合は、追加します。
通過した単語はカウントされます。大多数の言葉では、これは毎回ですが、最初の15回はそれらを目にします。わずかなパーセンテージがさらに早くカウントされ始め、単語ごとに最大15回の出現が結果に含まれる可能性があります。これがブルームフィルターの制限です。
最初のパスが終了したら、必要に応じて2番目のパスで不正確さを修正できます。ブルームフィルターの割り当てを解除し、10番目に頻度の高い単語の15回以内にないすべてのカウントも割り当て解除します。もう一度入力を確認します。今回は（別のハッシュテーブルを使用して）単語を正確にカウントしますが、最初のパスからおおよその勝者として保持されていない単語は無視します。
ノート
最初のパスで使用されるハッシュテーブルは、理論的には、入力の特定の統計的分布（たとえば、各単語を正確に16回）または非常に制限されたRAMでオーバーフローする可能性があります。これが現実的に起こり得るかどうかを計算または試すのはあなた次第です。
バケット幅（上記の説明では4ビット）は構造の単なるパラメーターであることに注意してください。カウントされないブルームフィルター（バケット幅1）は、最もユニークな単語を適切にフィルターで除外しますが、他の非常にまれにしか発生しない単語をフィルターで除外することはありません。バケットサイズが広いと、ワード間のクロストークが発生しやすくなり（バケットが少なくなるため）、最初のパス後の保証精度レベルも低下します（4ビットの場合は15回発生）。しかし、これらの欠点は、ある時点までは量的に重要ではありませんが、非反復的な自然言語データを使用してハッシュテーブルをサブギガバイトサイズに維持するためには、より積極的なフィルタリング効果が完全に重要であると想像しています。
ブルームフィルター自体の桁違いのメモリニーズについては、これらの人々は、100 MBをはるかに下回り、はるかに困難なアプリケーション（しきい値の1グラム統計ではなく「完全な」nグラム統計）を使用して作業しています。
mergesort を使用して、テラバイト ファイルをアルファベット順に並べ替えます。最初のパスでは、使用可能なすべての物理 RAM を使用してクイック ソートを使用し、長い一連の単語を事前にソートします。
その際、同一の単語が連続する場合は、そのような単語 1 つと数だけで表します。(つまり、マージ中にカウントを追加しています。)
次に、ファイルを再ソートします。ここでも、クイックソートの事前ソートでマージソートを使用しますが、今回はアルファベット順ではなくカウントでソートします。
これは遅いですが、私の他の答えよりも実装が簡単です。
私が考えることができる最高：
Nで最も頻繁に使用される単語を取得すると、N * partsNumber単語が取得されます。常に正しい答えが得られるとは限りませんが、固定メモリと線形時間で機能します。