15

C# を使用して、テキスト ファイルのグループで約 13 文字の文字列を検索する必要があります。テキスト ファイルの数は変化しており、100 ~ 1000 の範囲である可能性があります。ファイルのサイズは 1KB から 10MB の範囲です。

各ファイルを開き、行ごとに読み取り、文字列が存在するかどうかを (index.of を使用して) 確認する単純な方法を試しましたが、これは遅すぎます。タイミングを 5 秒改善した Boyer-Moore アルゴリズムも使用してみましたが、それでも遅いように感じます。

検索を高速化する方法について何か考えはありますか?

4

5 に答える 5

9

「検索」を実行する回数に応じて、検索エンジンを使用するかどうかを決定します。何度も検索したい場合は、検索エンジンを使用してください。それ以外の場合は、使用しないでください。ここでは、両方のシナリオを実装する方法について説明します。

検索エンジンを使用する場合:サブストリングを探しているようです。つまり、お気に入りの検索エンジン、できればカスタマイズ可能な検索エンジン(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コンプレッサーは、高速圧縮アルゴリズムの良い例です。

于 2013-02-12T07:57:41.353 に答える
3

コンテンツを使用したオペレーティング システム ファイル検索の使用を検討する必要があります。Microsoft Windows Search 3.x SDKをご覧ください。

または、PLINQ を利用してファイルの配列を検索することもできます。このリンクを参照してください。

Directory.GetFiles と PLINQ を使用したファイル コンテンツとディレクトリ検索

于 2013-02-12T07:17:51.160 に答える
3

次の 2 つのオプションが思い浮かびます。

メモリ内のテキスト ファイルを読み取り、文字列全体を一度に検索します。

それが遅すぎる、またはメモリを大量に消費することが判明した場合は、Apache Lucene などのインデクサーを使用してください。Lucene.net と呼ばれる、.NET で使用できる便利で簡単な SDK があります。

ここに小さな紹介があります: http://www.codeproject.com/Articles/29755/Introducing-Lucene-Net

于 2013-02-12T07:26:22.233 に答える
1

Microsoft のインデックス サービスを使用して、カタログに追加するフォルダ内のドキュメントを検索できます。これは、テキストファイルを検索するために使用できる非常に優れた記事です

于 2013-02-12T09:00:11.010 に答える
1

お使いのコンピューターがそれを処理できる場合は、すべてのテキスト ファイルをメモリにロードしてみてください (ここに示す手法を使用してから、メモリ内のテキストを評価します。

一度にすべてのファイルを処理できない場合は、最小のファイルに対してこれを行います。ここでは、ファイル I/O が最大の出費になるため、できるだけ最小限に抑える必要があります。

于 2013-02-12T07:29:41.887 に答える