C言語でファイル内の一致検索

質問

やりたい事は、ファイル（テキストに限らず画像等も含めて）をfopen関数で読み込んであらかじめ用意したバッファーに格納されているデータと一致する箇所をすべて検索して検索されたところをすべて列挙することです。
効率の良い（検索速度）方法で行いたいのですが、
fgetc関数を使って検索していくのとfread関数を使って一度すべてをメモリー内に読み込んで検索するのではどちらが効率がよいでしょうか？
他にも良い方法があったら教えてください。
私はFILE * ストリームポインタの仕組みがよくわかっていません。fopenをすると何が内部で行われるのでしょうか？ファイルの内容がメモリーに読み込まれるわけではないですよね？ファイル内にアクセスする時どのようにアクセスしているのかなど教えていただきたいです。そうすればどうするのが良いのかわかる気がするので。

あとこれとは別の話ですが
標準関数にあるmemmoveとstrstr関数ですが、これと同様な機能を持つstrmoveとmemmemといった関数がなかったのですが、この機能を持つ関数は用意されているのでしょうか？一般的に使われないので自分で作れということなのでしょうか？その場合どの様に実装すればよいか時間があれば参考にプログラムを書いていただけないでしょうか？

よろしくお願いします。

回答No.4

goosyu · ベストアンサー

>fgetc関数を使って検索していくのとfread関数を使って一度すべてをメモリー内に読み込んで検索するのではどちらが効率がよいでしょうか？
→一番早い検索は全てメモリに読み込み，ファイルアクセス回数を減らすのが基本です。ファイルアクセスにはOSの処理時間が発生する為です。
　ただ，ファイルが大きすぎてメモリに入りきらない場合もありますので，ファイルの大きさを見てファイルのアクセス方法を変えるしかないと考えます。
　ちなみにパソコンのOS環境下では，fgetc関数を使っても毎回物理的にファイルを読み込んでいるわけではなく，ファイルバッファを読み込む事になりますので思ったほどは効率が悪くなりませんが，高速化を考えた場合はfread関数を使うことをおすすめします。

>私はFILE * ストリームポインタの仕組みがよくわかっていません。fopenをすると何が内部で行われるのでしょうか？
→お使いの環境(OS)によってはfopenの内部動作は変わってくるかもしれませんが。手元の環境での動作についてまとめます。
　・ファイルオープン
　　OSが提供しているファイルオープン関数(createfile関数とか_open関数など)を使いファイルをオープンします。
　・ファイル読み込み用のバッファ構造の提供
　　これはfgetc関数,fread関数,fscanf関数などファイル読み込みをバッファ経由で行いファイル読み込み回数を減らす機能を提供します。
　・FILE型のリソース確保
　　ファイルオープン時にFILE型のリソースを確保し戻り値に確保したアドレスを返します。

>ファイルの内容がメモリーに読み込まれるわけではないですよね？ファイル内にアクセスする時どのようにアクセスしているのかなど教えていただきたいです。そうすればどうするのが良いのかわかる気がするので。
→普通fopen関数ではファイルの読み込みは行われません。fgetc関数なりfread関数がコールされた場合に,バッファが空の時に適当なサイズ分を低水準入出力(_read)関数などを使いバッファへ読み込みを行い,そこから結果を返しています。またバッファにデータがある場合はバッファから直接結果を返しています。

>標準関数にあるmemmoveとstrstr関数ですが、これと同様な機能を持つstrmoveとmemmemといった関数がなかったのですが、この機能を持つ関数は用意されているのでしょうか？一般的に使われないので自分で作れということなのでしょうか？
→必要であれば必要に応じて作るという認識だと思います。

>その場合どの様に実装すればよいか時間があれば参考にプログラムを書いていただけないでしょうか？

#define strmove(A, B) memmove((A), (B), (strlen(B) + 1) * sizeof(char))

// 引数 : strLen pStrのサイズ , pSrc 検索対象の先頭アドレス , searchLen pSearchのサイズ , pSearch 検索するデータの先頭アドレス
char *memmem(int strLen, char *pStr, int searchLen, char *pSearch)
{
// 単純検索 世の中にはBM法とかKMV法など色々と検索するロジックが存在します。高速化をしたいのであればそちら検討して下さい。
int i;
if (strLen < searchLen) return NULL;
for ( i = 0; i < strLen - searchLen + 1; i++) {
if ( memcmp(&pStr[i], pSearch, searchLen) == 0 ) {
return &pStr[i];
}
}
return NULL;
}

お礼

回答ありがとうございます。
やはり一度すべて読み込んだ方が速かったです。
説明を読んで納得できました。
検索アルゴリズムをいままで書いたこと無かったのでネットで検索してBM法とBMH法とquick search法をでそれぞれ作ってみました。
単純検索より速く検索でき驚きました。
memmem関数を自力で作ることができました。助かりました。

回答No.3

jacta

先にfreadで全部読み込む方法の場合、メモリ管理がやや面倒になります。事前にファイルサイズを調べておけばよいのですが、標準の範囲ではいったん最後まで読むしかないので、あまりうれしくありません。

アルゴリズムにもよりますが、ごく単純なものであればfgetcを使って1バイトずつ読み込みながら検索するほうが、作るのも簡単ですし、実行効率もよくなる可能性があります（実行効率に付いては実装方法次第です）。

memmoveというのは、領域の重なり方に応じて、前から後ろに向かってコピーするか、後ろから前に向かってコピーするかを切り替えています。これを実現するには、領域のサイズが分かっていなければなりません。
したがって、strmoveのようなものを作ろうとすると、いったんstrlenで文字列の長さを調べてからmemmoveすることになります。
具体的には、

memmove(s1, s2, strlen(s2));

のような感じです。これだけで済みますので、特別な関数は不要でしょう。

お礼

回答ありがとうございます。
いろいろアルゴリズムを考えようとおもい一度すべてメモリに読み込むことにしました。確かに単純なものならgetcが手っ取り早いです。

回答No.2

salsberry

memmoveの文字列版はstrcpyまたはstrncpyでは足りませんか？

お礼

意外と簡単にmemmoveを作れることを知りました。
ありがとうございました。

回答No.1

Tacosan

可能なら「fread で全部読み込む」方が簡単になる. 「効率の良しあし」以前に「明らかにプログラムが単純化される」のは明白.
ちなみに検索アルゴリズムは何を使うつもりですか?

お礼

回答ありがとうございます。
はじめ単純法で検索することを頭に入れていてfgetcで順に検索していけばできるのではと思っていたのですが、検索アルゴリズムで高速化を考えて一度全てメモリに読み込んで検索することにしました。
うまくできそうです。