データ構造とアルゴリズム 第14回 文字列の照合

本日の内容 文字列の照合(p.161) 演習 アンケート

C言語の文字列 文字列とは 文字列 hello はプログラム中では以下のように表現されている 文字型の配列 ナル文字（NULL文字）で終端 char str[6] = { ‘h’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’ }; char str[6] =　“hello”; ←　このようにも書ける 5文字格納するのに、配列の要素は６個必要なことに注意 ナル文字 h e l l o \0

文字列の照合（検索） 文字列中の一部分を部分文字列と呼ぶ 特定のパターンをもった部分文字列がどこにあるかを調べる テキスト：babcabaabaacaabaa パターン：abaa

文字列照合の例 ｎ文字のテキスト（src[0]~src[n-1])から、m文字のパターン（pat[0]~pat[m-1])が最初に現れる位置を検索 src h y p o c h o n d r i a \0 pat c h o \0

力まかせ法 src の０文字目～m-1文字目が、patと一致するか調べる src の1文字目～m文字目が、patと一致するか調べる h o y p c n d a r i \0 pat src の1文字目～m文字目が、patと一致するか調べる src h y p o c h o n d r i a \0 pat c h o \0 すべて一致するまで pat を１ずらしながら調べていく src h y p o c h o n d r i a \0 pat c h o \0

力まかせ法の計算量 テキスト長 ｎ、パターン長 ｍ 計算量 O(mn) テキスト長 ｎ、パターン長　ｍ 計算量 O(mn) 実際には、パターン先頭の数文字で一致判定できる（mはほぼ定数cとみなせる）ので O(cn) = O(n)

BM(Boyer-Moore)法 パターンを、右端の文字から照合していく パターンをずらせる量をあらかじめ計算しておき、可能な限りずらすことにより高速化　⇒ ２つの方法で表をあらかじめ作成 テキストに現れるすべての文字について、それらがパターン中のどこに現れるかを示した表（表d） パターン中のそれぞれの位置について、そこで不一致が発生した場合にパターンをどれだけずらせるかを計算した表（表e）

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) i t g e p k o g e h o g e j (= 6)

BM法のストラテジ１ あらかじめ、すべての文字について、パターン中のどこに現れるかの表 d を作成しておく (教科書 6.22式) a b 同じ文字が複数個ある場合には、もっとも右側の位置 文字がパターン中に存在しない場合には -1 パターンが　kogehoge の場合 p k o g e h o g e a b c d e f g h i j k ・ o -1 7 6 4 5

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

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 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

BM法のストラテジ2(例１） ここで不一致！ 確認済み ? g e k o g e h o g e j (= 5) k o g e h o 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

BM法のストラテジ2 (例2） ここで不一致！ 確認済み ? o g e k o g e h o g e j (= 4) k o g e h 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

いくつかのパターンに対する e(j) の例 j 1 2 3 4 5 6 7 j 1 2 3 a b c d e a b c a b a a 1 2 3 4 5 6 7 j 1 2 3 a b c d e a b c a b a a e(j) 5 5 5 5 5 8 8 1 e(j) 3 3 1 2 j j 1 2 3 4 5 6 7 1 2 3 4 5 6 7 a b c d e c d e a a a a a a a a e(j) e(j) 8 8 8 8 3 8 8 1 1 2 3 4 5 6 7 8

Boyer-Moore法 (まとめ） パターンの右端から照合 不一致がおきたときに、２つの表からパターンをずらす量を決定 s　= max{ j –d(t[i]), e(j)} d(t[i]) は、不一致を起こしたsrc文字の種類によって決まる値 e(j) は、不一致を起こしたパターン中の位置によって決まる値 Boyer-Moore法の計算量 最悪ケース O(n) 平均ケース O(n/m)

期末試験について 日時：8/2(水) 10時30分～12時 場所：特別講義室Ⅱ 教科書，配布資料等の持ち込み不可 学生証を必ず提示すること 日時：8/2(水)　 10時30分～12時 場所：特別講義室Ⅱ 教科書，配布資料等の持ち込み不可 学生証を必ず提示すること 机上に置けるものは，鉛筆またはシャープペン，消しゴム，定規，学生証のみ 座席は当日指定する 不正行為には厳正に対処する

成績評価について 全講義回数の2/3回（９回）以上の出席を満たさない場合は単位を取得できない(履修規定) レポートおよび期末試験を総合評価(比率　3：7) レポートと試験の合計得点を100点満点に換算 優：80点以上 良：70点以上～80点未満 可：60点以上～70点未満