ファイル検索機能の効率的なアプローチ

Question

私は非常に大きなテキスト文書を持っています。私はファイル内の指定された文字列の出現を見つけ、その位置を表示するために "検索"機能を実装しています。単なる単語検索ではなく、単語/センテンス/段落の一部を持つことができます。私は、このプロセスの効率的なデータ構造について検討中です。それが単語検索全体なら、私は試し/ハッシュテーブルを使用することができます。私は、ファイルサイズが非常に大きいので、接尾辞配列/接尾辞ツリーを使用することはできません。並べ替えもそれほど効率的ではありません。他の単純なオプションは、フレームワークの文字列検索/正規表現機能を使用することです。これは線形時間を要します。このようなオペレーションのためのより良い知られたアプローチはありますか？最初は文字列検索であり、後でメタキャラクターで検索する予定です。

Answer 1

Lucene.NETは、インデックスとテキストのスキャンを行い、検索エンジンライブラリです： http://incubator.apache.org/lucene.net/

Answer 2

トライと接尾辞木/配列は良いオプションですが、あなたがそれらを好きではない場合、私は別の解決策を持っている：ハッシュを作成します表：

• は...長さ1、2、3、のすべての文字列のハッシュテーブルを作成します。N Nは、あなたが好きな番号です複雑さO（Nの*のsize_of_text）検索したい場合は

• 文字列には2つのオプションがあります：

  文字列のサイズがNより小さい場合、ハッシュテーブル〜O（1）で検索し、o（size_of_string）でhash_keyを作成します。
  サイズがNより大きい場合は、サイズNのチャンクを作成し、これを行う：チャンクを検索し、すべての位置を覚えている。次のチャンクで同じことをして、連続している数字があるかどうかを確認するよりも（たとえば、最初にi、j、2回目にk、i + N、iよりもi + Nが良い組み合わせ）連続したペア（私は、私はあなただけの私はNを+維持、N + 1）の最後の番号を保存して、あなたのスタック内の番号を持っていないか、あなたは
  はそれが助けを願って単語を終了するまで継続します。