データ構造

Transcription

1 アルゴリズム及び実習 9 馬青 1

2 文字列の探索 文字列探索 (string searching) は文字列照合 (string pattern matching) ともいう テキストと呼ばれる文字列の中に パターンと呼ばれる文字列に一致する部分があるかどうかを調べる問題である そのような部分が見つかった場合には その場所を答えとする テキストエディターにおける探索コマンドやテキストデータベースにおける検索などに使われる 使用頻度の高い操作である 2

3 C 言語の復習 文字の入出力 標準入力からの入力は ch=getchar(); or scanf( %c, &ch); /* int で宣言の場合 warning message が出る処理系がある char で宣言すると warning message が出ない */ 標準出力への出力 putchar(ch); or printf( %c, ch); 3

4 C 言語の復習 文字列 文字列変数の宣言 char s[64]; 数字 64 は配列の大きさだが 最後に必ずヌル文字 0 を入れないといけないので 格納できる半角文字の最大個数は 64-1=63 となる 文字列変数を初期化しながら宣言 char s[]= Ryukoku Uni. ; 文字列の付与 : strcpy(s, Ryukoku Uni. ); この配列は計算機上実際に以下のように表現される s[0] s[1] s[2] s[3] s[4] s[5] s[6] s[7] s[8] s[9] s[10] s[11] s[12] R y u k o k u U n i. 0 つまり 文字列を上記のように宣言し 実際の値を付与すると 1 文字ごとに配列に格納され最後にヌル文字 0 が自動的に付加される 4

5 C 言語の復習 文字列 文字列をキーボードから丸ごとに読み込む #define Length 5 char line[length]; fgets(line, sizeof(line), stdin); できれば大きめな数字 (256 など ) 改行までか最大 Length-1 個の文字を読み込むことができる 123 を入力した場合 line[0]= 1, line[1]= 2, line[2]= 3, line[3]= n, line[4]= を入力した場合 line[0]= 1, line[1]= 2, line[2]= 3, line[3]= 4, line[4]= 0 になる 5

6 C 言語の復習 文字列 char s[64]; scanf( %s, s); で文字列を読み込むこともできる ただし たとえば ab cd という一行を入力する場合 fgets(s, sizeof(s), stdin) なら s に ab cd がそのまま入る つまり 空白やタブまで読み込む scanf( %s, s) なら s に ab のみが入る すなわち s[0]= a, s[1]= b, s[2]= 0 6

7 C 言語の復習 文字列 fgets() で 1 行を文字列変数 s に読み込んだ場合 s の中身は以下となる s[0] s[1] s[2] s[3] s[4] s[5] s[6] s[7] s[8] s[9] s[10] s[11] s[12] R y u k o k u U n i n 0 s[strlen(s)-1]= 0 ; で s は以下になる s[0] s[1] s[2] s[3] s[4] s[5] s[6] s[7] s[8] s[9] s[10] s[11] s[12] R y u k o k u U n i 0 0 つまり s の中から改行記号 n が取り除かれることとなる 7

8 C 言語の復習 ファイルの入出力 ファイルの読み込みは./a.out<filenameというやり方もある ただ これはキーボードからの入力がないときのみ使える方法 たとえば文字列探索の場合 テキストをファイルから 探索パターンをキーボード ( 標準入力 ) から入力したいので これまでの方法では対応困難である このような場合 ファイルの入出力関数を利用することで解決できる FILE *fp; // ファイルポインター変数 fp=fopen( filename, r ); // ファイルを読み込むためにオープン fp=fopen( filename, w ); // ファイルを書き出すためにオープン fgets(line, sizeof(line), fp); //stdinの代わりにfpを fclose(fp); // ファイルを使い終わったらクローズこのような場合 実行は./a.outのみとなる ちなみに scanf(...) fscanf(fp,...) ch=getchar() ch=fgetc(fp) printf(...) fprintf(fp,...) puts(...) fputs(..., fp) 8

9 演習問題 1 以下のようなファイル text.dat があったとする このファイルからデータを読み込み 改行も含めてまったく同じ形式でこのデータをファイル textcopy.dat に書き出すプログラムを書きなさい ただし ファイルの入出力は前のページのやり方を用いる text.dat string searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. 9

10 演習問題 2 関数 int CSearch(char t[], int ch) を作成しなさい ただし 文字変数 ch を文字列変数 t の一つ一つの文字と比較していき 一致すれば その配列の要素番号を 一致するものがなければ -1 を返す つまり たとえば 文字列変数 t に Ryukoku University が入っている場合 文字変数 ch に u が入っていれば 2 が返される x が入っていれば -1 が返される 10

11 演習問題 3 以下のファイルから文字列を読み込み 演習問題 2 で作成した関数を利用して キーボードから読み込んだ文字と比較しその比較結果を出力するプログラムを作成しなさい ただし 以下のファイルは途中に改行が一切なく 一行として読み込むことができるものとする text.dat string searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. 改行なし!! 11

12 文字列の探索 方法 : テキストとパターンを照合する方法で最も単純なものは パターンをテキスト上で1 文字ずつ移動させながら力まかせに比較していく方法で 力まかせアルゴリズムと呼ばれる テキストへのポインタの後戻りをなくしたKMP(Knuth-Morris-Pratt) 法 パターンを1 文字ずつでなく可能な限りテキスト上を移動させるように工夫したBM(Boyer-Moore) 法がある 12

13 力任せ法 パターンをテキスト上で1 文字ずつ移動させながら照合し 不一致が出た時点でテキストの位置を照合の開始位置の直後の位置に戻し 再び1 文字ずつ移動させながら照合していく方法である たとえば テキスト ABCBABACB の中から 下線部分の文字列パターン を探索する場合 気をつけなければならないのは 最初にABCAまで照合が成功しその次のBで照合が失敗した場合 テキストの次の探索位置としてそのB( つまり5 文字目のB) からスタートしてはいけなくて 2 文字目の位置 (B) まで戻してスタートしなければならないことである 13

14 力任せ法 テキスト : パターン : ABCBB テキスト : パターン : ABCBB 14

15 アルゴリズム 1 入力 : テキストの文字列配列 t, パターンの文字列 p 出力 : 探索成功ならテキスト上パターンが出現する最初の位置を posに付与する 探索が失敗なら-1をposに付与する 補助 :i: テキストの位置, j: パターンの位置? 1. { 初期設定 }i=0, j=0とおく 2. iがテキストの最後に達されたか jがパターンの最後に達されるまで 次の操作を繰り返す 2-1 t[i] と p[j] が比較し 一致すれば? そうでなければ? ABCABCBCBABACB i ABCBC j 3. もしjがパターンの最後に達されていれば pos=i-j そうでなければ pos=-1 ( 最悪 ) 計算量 :O(mn) m: パターンの長さ n: テキストの長さ 15

16 パターンが複数存在する場合 そのす テキスト : パターン : べてを探索したい ABCBB これで終わりではなく テキスト : パターン : ABCBB 一箇所目 二箇所目 16

17 アルゴリズム 2 アルゴリズム 1 から変更のポイント パターンのテキスト上の位置変数 pos を配列変数に パターンの出現回数を数えるための変数を用意する パターン探索が成功なら パターンのテキスト上の位置を求め 位置の配列変数に格納することに加え パターンの出現回数を 1 つ足す テキストの位置変数 i を次に探索開始の位置に設定し パターンの位置変数 j をパターンの最初の位置に戻す テキストの最後に達するまで 処理を繰り返す 17

18 アルゴリズム 2 入力 : テキストの文字列配列 t, パターンの文字列 p 出力 : 探索成功ならパターンの出現回数を変数 cnt に 位置を配列 pos[] に格納 探索失敗なら cnt が 0 のまま 補助 :i: テキストの位置, j: パターンの位置 1. { 初期設定 }i=0, j=0, cnt=0 とおく 2. i がテキストの最後に達されていなければ 以下を繰り返す 2-1 t[i] と p[j] が比較し 一致すれば? そうでなければ? 2-2 もし j がパターンの最後に達されていれば pos[cnt]=?, i=?, j=0, cnt++ 18

19 第 9 回実習課題 1. 文字列探索アルゴリズム 1 を実現する関数 int StrSearch1(char t[], char p[]) を作成し その動作を確認できるプログラム (ex09- ssearch1.c) を作成しなさい ただし t[], p[] はそれぞれテキストとパターンを格納する文字列変数で パターンの位置が戻り値である ( 見つからないときは -1) また 動作確認の際 テキストは Web からダウンロードした ex09.dat を ファイル入出力関数を利用して 用いること ただし ファイル ex09.dat は途中に改行が一切なく 一行として読み込むことができるものとする 2. 文字列探索アルゴリズム2を実現する関数 int StrSearch2(char t[], char p[], int pos[]) を作成し その動作を確認できるプログラム (ex09-ssearch2.c) を作成しなさい ただし t[], p[] はそれぞれテキストとパターンを格納する文字列変数 pos[] はパターンの位置を格納する配列で 戻り値はパターンの出現回数である また 動作確認の際 テキストは課題 1と同じファイルex09.dat を ファイル入出力関数を利用して 用いること ( 発展課題 ) 19

20 課題 1 の実行例./a.out the pattern to find: searching algorithm position: 7 the pattern to find: algorithm position: 17 the pattern to find: Ctrl-D 課題 2 の実行例./a.out the pattern to find: searching algorithm cnt: 1, position: 7 the pattern to find: algorithm cnt: 3, position: the pattern to find: string cnt: 5, position: the pattern to find: Ctrl-D 20