「検索」を実行する回数に応じて、検索エンジンを使用するかどうかを決定します。何度も検索したい場合は、検索エンジンを使用してください。それ以外の場合は、使用しないでください。ここでは、両方のシナリオを実装する方法について説明します。
検索エンジンを使用する場合:サブストリングを探しているようです。つまり、お気に入りの検索エンジン、できればカスタマイズ可能な検索エンジン(lucene、terrierなど)を使用して、ファイルにインデックスを付ける必要があります。ここで必要な手法は、トリグラムにインデックスを付けることです。つまり、すべての3文字の組み合わせにインデックスを付ける必要があります。F.ex .:'foobar'は、'foo'、'oob'、'oba'、および'bar'を生成します。検索するときは、クエリで同じことを行い、これらすべてのトリグラムのANDを使用して検索エンジンクエリを発行します。(これにより、ドキュメントの投稿リストでマージ結合が実行され、IDまたは投稿リストに入力したものが返されます)。
または、接尾辞配列を実装して、ファイルに1回インデックスを付けることもできます。これにより、短い(1〜2文字)サブストリングを検索する場合にもう少し柔軟性が得られますが、インデックスに関しては保守が困難です。(CWI / Amsterdamには、高速インデックス付けの接尾辞配列に関するいくつかの研究があります)
数回だけ検索する場合、使用するアルゴリズムは、Boyer-Moore([Graham A. Stephen、String Search]で説明されているように通常Boyer-moore-sundayを使用します)またはコンパイルされたDFA(それらを構築できます)のいずれかです。作成が簡単なNFAから)。ただし、ディスクIOがおそらくボトルネックであり、とにかくデコードする必要のあるバイトの束を比較するのは非常に高速であるという単純な理由から、速度はわずかに向上します。
実行できる最大の改善点は、ファイルを1行ずつ読み取るのではなく、ブロック単位で読み取ることです。可能であれば、64 KBのブロックサイズを使用するようにNTFSを構成し、64KBの倍数でファイルを読み取る必要があります。1回の読み取りで4MB以上と考えてください。非同期IOを使用して、読み取りと処理(以前のデータの読み取り)を同時に行えるようにすることもお勧めします。あなたがそれを正しく行うならば、それはあなたにほとんどの最新のハードウェアで10MBのためのほんの一瞬の実装をすでに与えるはずです。
最後になりましたが、情報検索全体で使用される巧妙なトリックは、高速圧縮アルゴリズムを使用してデータを圧縮することでもあります。ディスクIOはメモリ/CPU操作よりも遅いので、これもおそらく役立つでしょう。GoogleのSnappyコンプレッサーは、高速圧縮アルゴリズムの良い例です。