変更されない大きな静的バイナリ (10 GB) があります。
小さな文字列 (それぞれ 15 バイト以下) を入力として取り、どの文字列が最も頻度が低いかを判断できるようにしたいと考えています。
バイナリ全体を実際に検索しないと、これを正確に判断できないことを理解しているので、近似値になることはわかっています。
ALOT である約 256^15 バイトが必要になるため、ツリー/ハッシュ テーブルの構築は実行できません。
このタスク専用の約 100GB のディスク容量と 8GB の RAM がありますが、実際にファイルを調べずにこのタスクを達成する方法を見つけることができないようです。
大きなバイナリを準備するのに十分な時間があります。その後、最も頻度の低い文字列を何度も決定する必要があります。
何か案は？
ありがとう！ダニエル。
（ところで：それが問題であれば、私はPythonを使用しています）
ストレージを確保できる限り多くの n タプルのカウントを含むハッシュテーブルを構築することはできますか? 見えなくなった木は剪定できます。私はそれを「近似」とは呼びませんが、表示されない文字列を確実に検出できる「上限」である可能性があります。
したがって、すべての 4 タプルを構築できるとします。
次に、「ABCDEF」の出現回数をカウントするには、count(ABCD)、count(BCDE)、count(CDEF) の最小値が必要です。それらのいずれかがゼロの場合、文字列は表示されないことが保証されます。1 つの場合、多くても 1 回しか表示されません (まったく表示されない場合もあります)。
変更されない大きな静的文字列があるため、この文字列を前処理する 1 回限りの作業と、クエリに応答する作業を繰り返す必要がないことを区別できます。より強力なマシンで 1 回限りの作業を行うと便利な場合があります。
桁違いまたはそれ以上の内部ストレージを持つマシンを見つけることができれば、サフィックス配列を構築できます。これは、オフセットから始まるサフィックスのソート順でストリームにオフセットの配列です。これをクエリ用の外部ストレージに保存し、これをバイナリ検索で使用して、クエリ文字列が表示されるソート順の最初と最後の位置を見つけることができます。明らかに、2 つの間の距離から出現回数がわかります。バイナリ検索では、16G バイトが 2^34 バイトであると仮定すると、16G バイトを実行するために約 34 のバイナリ チョップが必要になるため、各クエリには約 68 のディスク シークが必要です。
その量の内部ストレージを見つけることを期待するのは合理的ではないかもしれませんが、私は 1TB の USB ハードドライブを約 50 ポンドで購入したので、1 回の作業で外部ストレージを増やすことができると思います. 外部メモリに接尾辞配列を構築するためのアルゴリズムがありますが、クエリ文字列は 15 バイトに制限されているため、それほど複雑なものは必要ありません。すべてのオフセットで見つかった 15 バイトの文字列とそれに続く 5 バイトのオフセット番号を書き出すことで 200GB のデータを作成し、これらの 20 バイトのレコードを外部ソートでソートします。これにより、クエリに応答するために外部ストレージに配置できるように、ソートされた順序で文字列に 50G バイトのインデックスが提供されます。