データ構造とアルゴリズム第14回文字列の照合 1 本日の内容    文字列の照合(p.161) 演習アンケート 2 C言語の文字列  文字列とは    文字型の配列ナル文字（NULL文字）で終端文字列 hello はプログラム中では以下のように表現されている  char str[6] = { ‘h’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’ }; h e l l o \0  char str[6] = “hello”; ← このようにも書ける  5文字格納するのに、配列の要素は６個必要なことに注意ナル文字 3 文字列の照合（検索）   文字列中の一部分を部分文字列と呼ぶ特定のパターンをもった部分文字列がどこにあるかを調べるテキスト：babcabaabaacaabaa パターン：abaa 4 文字列照合の例  ｎ文字のテキスト（src[0]~src[n-1])から、m文字のパターン（pat[0]~pat[m-1])が最初に現れる位置を検索 src h y p pat c h o \0 o c h o n d r i a \0 5 力まかせ法   src の０文字目～m-1文字目が、patと一致するか調べる src h y p o c h o n d r pat c h o \0 a \0 src の1文字目～m文字目が、patと一致するか調べる src pat  i h y p o c h o n d r i a \0 c h o \0 すべて一致するまで pat を１ずらしながら調べていく src pat h y p o c h o n d r i a \0 c h o \0 6 力まかせ法の計算量  テキスト長ｎ、パターン長ｍ   計算量 O(mn) 実際には、パターン先頭の数文字で一致判定できる（mはほぼ定数cとみなせる）ので O(cn) = O(n) 7 BM(Boyer-Moore)法   パターンを、右端の文字から照合していくパターンをずらせる量をあらかじめ計算しておき、可能な限りずらすことにより高速化 ⇒ ２つの方法で表をあらかじめ作成   テキストに現れるすべての文字について、それらがパターン中のどこに現れるかを示した表（表d）パターン中のそれぞれの位置について、そこで不一致が発生した場合にパターンをどれだけずらせるかを計算した表（表e） 8 BM法の文字照合  パターンpの右はしの文字から、文字列と一致するか調べる  p[j] に対して j = m-1, m-2 の順に比較 (mはpの文字数） i t e p k o g e h o g e j (= 7) t i g e p k o g e h o g e j (= 6) 9 BM法のストラテジ１  あらかじめ、すべての文字について、パターン中のどこに現れるかの表 d を作成しておく (教科書 6.22式)  同じ文字が複数個ある場合には、もっとも右側の位置文字がパターン中に存在しない場合には -1  パターンが kogehoge の場合  p a b c k o g e h o g e d e -1 -1 -1 -1 7 f g h i -1 6 4 -1 j k 0 ・ o ・ 5 10 BM法のストラテジ１  照合文字に応じて、max{1, j-d(ｔ[i])} だけスキップ  d(‘a’) = -1 (パターンに’a’は含まれない） s = max{1, 5 – (-1)} = 6 t a g e p k o g e h o g e j (= 5) t a g e p k o g e h o g e 11 BM法のストラテジ2   e( j ) = min{ s | p[l] = p[l – s], l = m–1, m–2,..., max{ j+1, s }, さらに j – s ≧ 0 の場合は p[j] ≠ p[j – s] } となる表を作成しておく（教科書 6.23式） e(j)とは、後方から照合していって、この位置で不一致が起きた場合、これだけずらさないと一致しない！という値 j 0 1 2 3 4 5 6 7 p k o g e h o g e e(j) 8 8 8 8 4 8 8 1 12 BM法のストラテジ2(例１）確認済みここで不一致！ ? g e k o g e h o g e j (= 5) k o g e h o g e j 0 1 2 3 4 5 6 7 p k o g e h o g e e(j) 8 8 8 8 4 8 8 1 13 BM法のストラテジ2 (例2）確認済みここで不一致！ ? o g e k o g e h o g e j (= 4) k o g e h o g e j 0 1 2 3 4 5 6 7 p k o g e h o g e e(j) 8 8 8 8 4 8 8 1 14 いくつかのパターンに対する e(j) の例 j 0 1 2 3 4 5 6 7 j a b c d e a b c a b a a e(j) 5 5 5 5 5 8 8 1 e(j) j 0 1 2 3 4 5 6 7 j 8 8 8 8 3 8 8 1 3 3 1 2 0 1 2 3 4 5 6 7 a a a a a a a a a b c d e c d e e(j) 0 1 2 3 e(j) 1 2 3 4 5 6 7 8 15 Boyer-Moore法   パターンの右端から照合不一致がおきたときに、２つの表からパターンをずらす量を決定     (まとめ） s = max{ j –d(t[i]), e(j)} d(t[i]) は、不一致を起こしたsrc文字の種類によって決まる値 e(j) は、不一致を起こしたパターン中の位置によって決まる値 Boyer-Moore法の計算量   最悪ケース O(n) 平均ケース O(n/m) 16 期末試験について        日時：7/25(水) 10時30分～12時場所：特別講義室Ⅱ 教科書，配布資料等の持ち込み不可学生証を必ず提示すること机上に置けるものは，鉛筆またはシャープペン，消しゴム，定規，学生証のみ座席は当日指定する不正行為には厳正に対処する 17 成績評価について    全講義回数の2/3回（９回）以上の出席を満たさない場合は単位を取得できない(履修規定) レポートおよび期末試験を総合評価(比率 3：7) レポートと試験の合計得点を100点満点に換算  優：80点以上  良：70点以上～80点未満  可：60点以上～70点未満 18