1

膨大な量のランダム データ内でランダムな文字列を見つけるための非常に効率的な検索アルゴリズム、方法、および手法のオプションを調査するには、「出発点」が必要です。私はこのことについて学んでいるので、誰かがこれについて経験していますか？最適化したい条件は次のとおりです。

  1. 最初のアイデアは、検索インデックスなどの点でファイル サイズを最小化することです。つまり、可能な限り小さいインデックス、またはさらに良いことに、その場で検索します。
  2. 検索するデータは大量の完全にランダムなデータです。たとえば、知覚可能なパターンのないランダムなバイナリ 0 と 1 です。ギガバイト単位のもの。
  3. 0111010100000101010101 など、同じようにランダムな検索文字列が提示された場合、ランダム データの山の中で同じ文字列を見つける最も効率的な方法は何ですか? パフォーマンスなどのトレードオフは何ですか?
  4. その検索文字列のすべてのインスタンスを見つける必要があるため、実装するソリューションの種類を制限する重要な条件のように思えます。

ヒント、手がかり、テクニック、ウィキの記事などは大歓迎です! 私はちょうど今これを勉強しています、そしてそれは面白そうです。ありがとう。

4

1 に答える 1

2

これを行う簡単な方法は、検索可能なデータの可能なすべての N バイト部分文字列 (N = 4 または 8 など) にインデックスを作成することです。インデックスは、小さなチャンクから、そのチャンクが発生するすべての場所にマップされます。

値を検索する場合は、最初の N バイトを取得し、それらを使用してすべての可能な場所を見つけます。もちろん、すべての場所を確認する必要があります。

N の値が大きいほど、検出される誤検知が少なくなるため、インデックス スペースの使用量が増え、ルックアップが高速になります。

このようなインデックスは、基本データのサイズの小さな倍数である可能性があります。

2 番目の方法は、検索可能なデータを N バイト (N = 64 程度) の連続した重複しないチャンクに分割することです。各チャンクをより小さいサイズ M (M = 4 または 8 程度) にハッシュします。

重複するすべてのチャンクが必要ないため、これにより多くのインデックス スペースが節約されます。

値を検索する場合、検索対象の文字列の連続する重複部分文字列をすべて検索することで、一致する候補を見つけることができます。これは、検出される文字列のサイズが少なくとも N * 2 バイトであることを前提としています。

于 2012-09-26T20:27:14.517 に答える