1

C++ または C を使用して大きな (> 500 MB) テキスト ファイルで検索したい値がいくつかあります。一致する可能性のある値は各行の先頭にのみ存在し、その長さはちょうど 10 文字であることがわかっています。さて、substr() を使用して値を検索するか、regexp を使用して、ファイル全体を行ごとに読み取ることができますが、それは少し見苦しく、非常に遅いです。埋め込みデータベース (Berkeley DB など) の使用を検討していますが、検索対象のファイルが非常に動的であり、毎回データベースに取り込むのに問題があります。メモリの制限により、ファイル全体を一度にメモリにロードすることはできません。よろしくお願いします。

4

5 に答える 5

3

これは C/C++ にはあまり適していないようです。この問題は、テキストの行全体を解析し、最初の 10 文字でパターン マッチングを実行する必要があると定義されているため、python や perl などの解釈されたものの方が単純に見えます。

どうですか：

import os
pattern ='0123456789'   # <-- replace with pattern

with open('myfile.txt') as f:
    for line in f:
        if line.startswith(pattern):
            print "Eureka!'
于 2012-04-05T19:08:56.810 に答える
2

strchrstdio ライブラリを使用し、各行を順番にバッファに読み込み、 、strcmp、strncmpまたはそのようなものを使用するよりも速くこれを行う方法がわかりません。問題の説明を考えると、それはすでにかなり最適です。ファイルを 1 行ずつ調べてパターンを探す必要をなくす魔法はありません。

とは言っても、行頭がちょうど 10 文字の固定パターンを扱っている場合、ここでは正規表現はほぼ確実に必要ありません。

本当に最後の数マイクロ秒を打ち破る必要があり、パターンが文字通り一定で、行の先頭にある場合は、memchr「\nパターン」またはいくつかを探して、読み取りバッファで実行できる場合があります。そのような（つまり、検索に改行文字を含める）が、パターンが正確に一定ではないように聞こえます。正確に一定でないと仮定すると、最も明白な方法 (最初の段落を参照) が最も明白です。

于 2012-04-05T19:05:47.273 に答える
1

探している値が多数ある場合は、Aho-Corasickを使用します。このアルゴリズムを使用すると、セット内の任意の文字列のすべてのオカレンスを同時に検索できる単一の有限状態マシンを作成できます。これは、ファイルを 1 回検索して、探しているすべての値のすべての一致を見つけることができることを意味します。上記のウィキペディアのリンクには、Aho-Corasick の C 実装へのリンクがあります。私が書いた Go の実装を見たい場合は、こちらをご覧ください。

単一または非常に少数の値を探している場合は、Boyer-Mooreを使用することをお勧めします。この場合、grep を使用することもできますが、これはおそらく、このアプリケーション用に作成したものと同じくらい高速です。

于 2012-04-05T19:43:50.850 に答える
0

はい、これは高速に実行できます。行ったことがある。それをしました。ただし、バグを導入するのは簡単です。

秘訣は、データでいっぱいのバッファーを読み取り、そのバッファーを検索してから次のバッファーに進むため、バッファーの終わりを管理することです。パターンは2つのバッファー間の境界にまたがる可能性があるため、その場合をカバーするためにほとんどのコードを記述することになります。

とにかく、境界の場合の外側では、次のようなループがあります。

unsigned short *p = buffer;
while( (p < EOB) && ( patterns[*p] ) ) ++p;

これは、EOBが適切に初期化されており、patterns []が65536値の配列であり、パターンの先頭に配置できない場合は0、可能な場合は1であることを前提としています。

CR / LFおよびバイト順序の規則に応じて、1に設定するパターンには、\nxまたは\rxが含まれる場合があります。ここで、xは10文字のパターンの最初の文字です。または、他のバイトオーダーの場合はx\nまたはx\r。また、バイトの順序や規則がわからない場合は、4つすべてを含めることができます。

候補の場所（EOLの後に最初のバイトが続く）が決まったら、残りの9バイトをチェックする作業を行います。パターン配列の構築は、事前にオフラインで行われます。2バイトのパターンは十分に小さい配列に収まるため、インデックス作成時にメモリのスラッシングはあまり発生しませんが、1バイトの場合の2倍の速度でデータを圧縮できます。

これに追加できるクレイジーな最適化が1つあります。それは、バッファーの最後に番兵を書き込み、それをパターン配列に配置することです。しかし、その歩哨は、他の方法ではファイルに表示できないものでなければなりません。ただし、ループは1つのテスト、1つのルックアップ、および1つの増分になります。

于 2012-04-05T19:28:01.843 に答える
0

検索の前にメモリマップファイルを使用するのはどうですか?

http://beej.us/guide/bgipc/output/html/multipage/mmap.html

1 つの方法として、メモリ内の最初の 64 MB をロードして検索し、これをアンロードしてから次の 64 MB をロードするという方法があります (4 KB の倍数で、ブロック境界で分割される可能性のあるテキストを見落とさないようにします)。

Boyer Moore 文字列検索も表示

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

于 2012-04-05T19:14:32.433 に答える