0

Cプログラムでは、通常のファイルで正確な文字列を検索する必要があります（Linuxを使用しています）。検索するにはどうすればよいですか？

私の最初の仮定は、ファイルの各行を（fgets（）を介して）RAMに移動し、移動するたびに、その行が正しい文字列であるかどうかを確認することでした。そうでない場合、ループはfgets（）を再呼び出しし、EOFまで文字列をチェックします。

しかし、1億5000万行のファイルはどうなるのでしょうか。この種の順次検索はまったく効果がないように思われることがあります。

しかし、プログラムがファイルに追加する行を並べ替えるために挿入ソートを使用する一種のバイナリ検索について考えていました（その行がに表示されないことを確認した直後に、3秒ごとに1行追加されます文字列ファイル）。しかし、その後、順次検索に使用したのと同じ時間を使用して、最初に行をRAMに移動する必要があったため、あきらめました。したがって、私は順次検索を選択しました。

この仮定は正しいですか？それとももっと良い方法はありますか？私は本当にそう願っています。

4

4 に答える 4

2

mmapファイル全体をメモリにマップしてから、strnstr検索を実行するために使用できます。

#include <sys/mman.h>

const char *fileName = "~/test.txt";
long fileLength;

// open file and get it's length
FILE *fptr = fopen(fileName, "r");

if (fptr == NULL || ferror(fptr))
{
    perror("could not open file");
    fclose(fptr);
    return 0;
}

fseek(fptr, 0, SEEK_END);
fileLength = ftell(fptr);
// return to the start of the file
fseek(fptr, 0, SEEK_SET);

// map the file
char *fileData = mmap(NULL, fileLength, PROT_READ, MAP_FILE | MAP_SHARED, fileno(fptr), 0);

if (fileData == MAP_FAILED)
    perror("could not map file");

// scan the file
char stringToSearchFor[] = "this is my string!";
if (strnstr(fileData, stringToSearchFor, fileLength) != NULL)
{
    printf("file contains the string!");
}
else {
    printf("file doesn't contain the string");
}

// clean up our code
munmap(fileData, fileLength);
fclose(fptr);
于 2012-05-15T16:00:39.747 に答える
0

を使用mmapしてファイルをメモリにマップしてから、標準のmemmem検索を実行します。お使いのOSが必要に応じてファイルの読み取りを処理します。

于 2012-05-15T15:46:07.130 に答える
0

詳細を教えてください。通常のファイルとはどういう意味ですか？続行する必要があるファイルの最大サイズはどれくらいですか？

大きなファイルになり、高速検索を実行する必要がある場合は、アルゴリズムの次のプロトタイプに従います。

  • あなたのファイルのインデックスを作成します
  • インデックスで検索を実行します
  • 新しい情報がファイルに追加された後、インデックス作成プロセスを開始します。（デルタインデックスが作成されます）
  • 現在のインデックスでデルタインデックスを追加する注意：パフォーマンスを向上させるには、新しい情報をキャッシュする必要があります。

検索アルゴリズムは、使用するインデックスタイプによって異なります（おそらく千枚通しの木、二分木など）

詳細については、インデックス作成、インデックス検索、存在するオープンソース検索システムについて読む必要があります。たとえば、apacheluceneとsphinxです。

UPD：役​​立つリンクになります： テキストファイルコンテンツのインデックスの実装

https://superuser.com/questions/233665/efficient-way-to-index-text-files

于 2012-05-15T15:56:40.973 に答える
0

大きなデータで文字列を照合しようとしているときに、プロセスを高速化するための秘訣は、ショートカットフィルターを作成することかもしれません。この手法は、Firefox拡張機能AdBlock Plusによって実際に使用され、着信ページリクエストをチェックし、それらを多数のフィルターリストと照合します。次に、一致したフィルター（広告）をブロックします。しかし、私は逸脱します。

文字列をたとえばn個のリテラルと照合する場合、最良のシナリオではアルゴリズム的にO（n）時間がかかります。 文字列の照合にかかる時間を短縮する秘訣は、サイズnを縮小することです。ショートカットフィルターの概念は、問題の文字列に含まれる短いパターンを作成することです。このように、各文字列の正確さをチェックするために費やす時間が少なくなります。フィルタが文字列と一致する場合は、文字列全体をチェックします。

基本的に、3つの文字列があるとしましょう。

1）ABCDABCD 2）DCBABCDA 3）ABDEFGHI

パターン「ABC」があるとします。反復中、1番目と2番目の文字列は一致を返します。3番目の文字列は拒否されます。次に、パターンに一致する文字列のみをチェックして、正しい文字列を探します。一方で。パターン「EFG」は1と2を（より短い時間で）拒否し、3に一致します。

サブストリングのマッチングは、ハッシュテーブルを使用することでさらに改善される可能性があります。ここでは、上記のように部分文字列のサイズを3と言うように修正できます。次に、文字列ごとに、長さ3のすべてのサブ文字列のハッシュを計算します。このようにして、どのパターンが文字列に一致するかを（O（1）時間で）すばやく判断できます。

于 2012-05-15T16:00:47.623 に答える