演習課題　第7回 文字列探索

7a　探索アルゴリズムの効率性の比較
■ 実験用データ
　テキストデータ:　　 ファイル: textE1.dat
　データ構造: 文字配列(配列の1要素にASCII codeの1文字が格納される)
　　　　　　　テキストの長さ(テキストの文字列長) + 1 ≦ 配列の大きさ

■ パターンの組み合わせ
・学籍番号の最下位桁の値によって、パターンの組み合わせが異なります。
　値　　　パターン長
　　　パターン1、パターン2、パターン3　　　パターン1の実例
　0: 　2　　　　　　　　4　　　　　　　8　　　　　"S]"　　　";f"
　1: 　2　　　　　　　　4　　　　　　12　　　　　"r6"　　　"B/"
　2: 　2　　　　　　　　6　　　　　　12　　　　　"E("　　　"0b"
　3: 　2　　　　　　　　7　　　　　　14　　　　　"S]"　　　"0b"
　4: 　3　　　　　　　　5　　　　　　10
　5: 　3　　　　　　　　5　　　　　　15
　6: 　3　　　　　　　　6　　　　 　　12
　7: 　3　　　　　　　　6　　　　 　　18
　8: 　3　　　　　　　　7　　　　 　　14
　9: 　3　　　　　　　　7　　　　 　　21
70万文字以降に初めて出現する長さ2のパターンは見つけにくいので、上記のように事前に設定しました。

パターン1、パターン2、パターン3はいずれも任意の異なった4つの文字列(合計: 4×3 = 12個)(但し、これらの文字列はいづれも70万文字目以降に初めて出現する文字列であること)。
　これらの合計12(4×3)の異なった文字列(配列中に設定)をパターンとして、上記のテキストデータを対象に、3種類の探索アルゴリズムを用いて探索し、このとき照合回数、および探索処理時間を記録する。
　　　(1) 力まかせ法
　　　(2) KMP法
　　　(3) BM法
　結果として合計36(12×3)の照合回数、および探索処理時間データが得られる。これらのデータを、理論値、その他様々な観点から分析せよ。

変数宣言時での配列(文字列ポインター配列)への格納の方法
実例(4個の文字列を格納する)
char *words[4] = {"S]", "r6", "E(", "S]"};

出力の例:
力任せ法
探索文字列　照合回数　　　探索時間(msec)　出現位置(文字目)
　　　;f　　　　　*******　　****　　　　*******
　　　r6　　　 　*******　　　****　　　　*******
　　　E(　　　 　*******　　　****　　　　*******
　　　B/　　　　*******　　　　****　　　　*******
　　　　　　　　　　　　　　・・・
　　　　　　　　　　　　　　・・・
7b　文字列の出現頻度算出プログラム作成‐探索アルゴリズムの応用
　下記に示すファイルを探索対象のテキストデータとする。
　　　　ファイル名: textE1.dat
次に示す長さの2種類の文字列、合計8組(4×2)の文字列を任意に設定する(但し、これらの文字列はいづれも多頻度で出現する文字列であること)。
　パターン1: 4つの異なった文字列: 　長さ4字
　パターン2: 4つの異なった文字列: 　長さはパターン1の3倍
　テキストで説明した、力まかせ法、KMP法、BM法の3種類の探索アルゴリズムを基にそれぞれ出現頻度を算出するようにプログラムを変更する。
　上述の文字列(配列中に設定)を上記のテキストデータを対象に、変更したプログラムを実行し、出現頻度を出力する。
　結果として合計24((4 + 4) × 3)の出現頻度のデータが得られる。プログラムの変更箇所について説明し、これらのデータを様々な観点から分析せよ。