大きなファイルを検索する最良の方法は何ですか?

Question

KMP (または同様の) 検索を大きなファイル (> 4GB) に適用しようとしています。

ただし、これによって問題が発生すると予想しています。十分なスペースがないため、すべてをメモリにコピーできません。

私の質問は、この検索を行う最善の方法は何でしょうか?単純に FILE* を作成してファイル内で直接検索を実行する必要がありますか、ブロック (たとえば 4k) をメモリにコピーしてそれらを検索する必要がありますか、それとも完全に別のものを実行する必要がありますか?

Answer 1

mmap() をサポートするプラットフォームを使用している場合は、 mmap() を使用できます。ファイルのページネーションも可能ですが、IO オーバーヘッドを減らすためにバッファをできるだけ大きく保つことと、2 つのページの境界間に注意することを忘れないでください (文字列は一致しているが、ページ境界によって分割されているとします)。

あるいは、何らかのインデックスを構築し、そのインデックスを使用して検索を制限することをお勧めします。KMP 検索は特に効率的ではありません。もちろん、これはファイルの性質、作成方法、 等

Answer 2

ファイルアクセスには、データコピーを回避するためにメモリマップファイルを使用することをお勧めします。 UNIXマシンでは簡単です。 1つのブロックに割り当てることができない場合は、ファイルマッピングを小さなブロックに分割する必要があります。興味のある方は、いくつかのコードを提供できます。

検索には、 Boyer More検索アルゴリズムの使用をお勧めします。

Answer 3

ファイルを直接検索すると非常に遅くなり、バッファリングを使用するとパフォーマンスが大幅に向上します。ただし、バッファは検索するサイズ（ SearchLength ）よりも大きくなければならないことに注意してください。また、 SearchLength バイトが終了する前にバッファを更新する必要があります。

Answer 4

最良のアプローチは、ブロック単位で読み取り、それを検索することです。ブロックサイズをパラメーターにして、最高のパフォーマンスが得られるものを試すことができます。

ただし、通常は、ファイル全体を直線的に検索する必要がないように、何らかの方法でファイルのインデックスを作成する方が効率的です。たとえば、KMPは文字列検索アルゴリズムです-単語のオカレンスを探しているだけですか？次に、単語とそのファイル内の場所のハッシュテーブル（ディスク上）を作成し、非常に効率的な検索を実行できます。