大きなバイナリファイルで文字列を検索する

Question

大きなバイナリファイル（1 MB <サイズ< 50 MB）があります。私は文字列を検索し、後続の4バイト（別のファイルの実際のデータの{size、offset}）を抽出する必要があります。検索が最も速くなるようにするための最も効率的な方法は何ですか？

EDIT：インデックスファイル内の文字列は、ソートされた順序になっています。

Answer 1

{string、size、offset}タプルをソート順（文字列）で格納し、その文字列をバイナリ検索します。

ファイルの先頭に文字列の最初の文字ごとにオフセットを格納することもできます。たとえば、 'a'で始まる文字列が120位で始まり、 'b'で始まる文字列が2000位のファイルで始まった場合、120, 2000, ...

Answer 2

エンコードが固定（ASCII）の場合、比較的簡単です。バイナリストリームを開き、バイトのバイトを読み込み、ターゲット文字列の最初の文字とマッチさせます。

別の（UTF-8）エンコーディングを使用している文字列がある場合は、トリッキーになります。

Answer 3

のようにファイルを開始することができます。Boyer–Moore string search algorithmを参照してください。

Answer 4

まず、ファイルのメモリマッピングを使用します。 2つのコピー（プログラム内に1つとファイルキャッシュに1つ）の代わりに1つのコピーしかないので、RAMに読み込むよりもずっと効率的です。

各文字列が固定長である場合、メモリを文字配列の配列として扱うことができるため、バイナリ検索は非常に簡単です。

各文字列が可変長で終了している場合は、文字列リストの途中にジャンプして次の0を検索し、その後の次の文字列をテストするバイナリ検索のバリアントを使用できます。その後、前後にジャンプして、文字列リストの1/4または3/4に戻り、繰り返します。

各文字列がパスカルスタイルの可変長で、先頭がバイトカウントである場合、それはよりトリッキーです。頻繁に行われる検索では、最初から線形検索が遅すぎるわけではありません。正確な文字列の一致を探している場合は、長さが一致しないことを確認するだけでほとんどの文字列をスキップできることを忘れないでください。

リストを頻繁に検索する必要がある場合は、文字列リストへのcharポインタの配列を作成することで、バイナリ検索が簡単になります。このファイルが実際に高速検索用のインデックスファイルである場合、ファイルをロードしている間にデザイナーがcharポインタ配列を作成しようとしていない限り、おそらくどこかにこのファイルがあります。