文字列探索
平成23年12月2日
アルゴリズム論 9回目
文字列探索
• データベース（構造化データ）
キーを指定
→そのキーを持つレコード検索
• テキスト（非構造データ）
検索したい文字の並び(string)：パターン
探査される文字列を含む情報：テキスト
→
腕ずくの方法
ＫＭＰ(Knuth-Morris-Pratt)法
ＢＭ(Boyer-Moore)法
腕ずくの方法
a c a c a c a b a c d a b a c d Patten Text Pattern Text Pattern Text 照合失敗 照合失敗 照合成功 a b a c d腕ずくの方法
①パターンをテキストの先頭に合わせる
②パターンとテキストを照合
一致
→探索の成功
不一致
→パターンを1文字ずらす，②へ
③上記手順を繰り返し，パターンがテキスト
末尾に来れば不一致と判断
→探索の失敗
文字列照合の例
text: M abcabababccbacabcabb ->t[0-19] N ababc pattern: ababc -> p[0-4] oox ababc x ababc x ababc oooox ababc x ababc ooooo -> t[5] 照合に成功したらtext先頭位置を返す
start i=0 j=0 j=j+1 i=i+1 text[i+j]:pattern[j] return=-1 returnを返す return=i 腕ずくの文字列照合フローチャート textからpatternを探索する text, pattern は文字型配列 M:textの文字列長 N :patternの文字列長 出力(戻り値）はpatternが 含まれる場合→textの先頭位置， 含まれない場合→-1 を返す （文字列型配列要素添え字） i：比較しているtext文字型配列要素添え字 j：比較しているpattern文字型配列要素添え字 M N = =/ >= < > <= 探索終了条件 照合成功時は textとpatternを同時に 右へ１シフト 照合失敗時は textのみを右へ１シフト patternはリセットして先頭へ戻す patternの文字列を すべて調べたか？ ｊ：N i:M-N
腕ずくの方法の計算量
テキスト：aaaa….aaa (100文字） パターン：aaaaab(6文字） ①の回数(先頭文字に合わせる回数）？ ②の回数（照合回数）？ よって，文字比較回数は？ テキスト1000文字，10000文字の場合は？ よってオーダーは？ 単純ソートと比較すると？ 100-6+1=95 6 6x95=570腕ずくの方法の計算量
• テキスト：ｎ文字，パターンｍ文字 • 最大計算量 テキスト：aaaaaaaaaaaaaaaaaaaaaaaaab パターン：aaaab ①の回数(先頭文字に合わせる回数）：(n-m+1) ②の回数（照合回数）：m よって，文字比較回数は m(n-m+1) テキスト長n>>パターン長mなので， n-m+1 nearly= nKMP(クヌース，モーリス，プラット）法
• 腕ずくの方法 →照合失敗時に毎回右へ1シフト →失敗状況に合わせてジャンプできる筈 • 失敗関数の導入 パターンu-1番目の文字まで一致， u番目の文字で不一致が発生した時の 移動量（パターンを何文字右へ移動すべきか）を調 べて表にしておくKMP法, 失敗関数の作成
パターン：tartar, テキスト：?????
4文字目で失敗 tartar, tarb???? tartar →パターンを4文字分ずらして，パターンの1文字目から比較 5文字目で失敗 tartar, tart????? →パターンを5文字分ずらして，パターンの1文字目から比較 6文字目で失敗 tartar, tarta??? →パターンを6文字分ずらして，パターンの1文字目から比較KMP法の適用例
text: abcabababccbacabcabb ->t[0-19] pattern: ababc -> p[0-4] 上記をKMP法により照合せよ． ※KMP法は，文字列前半が一致，後半が不一致の場 合に効果が現れるが，実際は，不一致が多く発生し ており効果が小さく，腕ずくの方法より遅いこともあ り，実際にはあまり利用されていない．BM (Boyer-Moore)法
テキスト文字列の最後から照合し不一致文字に注目 →一致ではなく，不一致の状況に合わせて， ずらす量を決める (ケース1：ｄはパターンにないので３ずらす） パターン： abc abc テキスト： abdefgh abdefgh (ケース2：aはパターン1文字目にあるので２ずらす） パターン： abc abc テキスト： abaabcd abaabcdBM法（２）
(ケース３：zはパターンにないので5ずらすと駄目．注目点ｚを５ ずらしてそこを最終文字列とする（３ずらす）） パターン： abcab abcab テキスト： xyzabcabcde xyzabcabcde (ケース4：aは2回目出現のパターン4文字目にあるの で1ずらす） パターン： abcab abcabBM法の改良
テキスト：
xabcxabcx…
xoo
パターン:xbacx
ｂはパターンに含まれるので最右のｂまで1文字
ずらす．でも末尾ｃｘで終わらないから，ｃｘのある
箇所まで3文字ずらす．
例題（１）
TOKKYOKYOKAKYOKU （テキスト） KYOKU (パターン) （Yはパターンに含まれているので、そこまで3文字ずら す。） TOKKYOKYOKAKYOKU KYOKU （Yはパターンに含まれているので、そこまで3文字ずらす。） TOKKYOKYOKAKYOKU KYOKU （Aはパターンに含まれていないので、そこを超えて5文字ずらす。） TOKKYOKYOKAKYOKU KYOKU (照合成功)例題（2）
TOKKYOKYOKAKYOKU （テキスト） KYOKU (パターン) ※移動量（パターンの末尾文字の照合時） K 1 Y 3 O 2 U 0 Others 5 上記の表は不完全。末尾でなければ補正必要 ※末尾から2文字目で不一致が検出されれば （移動量ー１）が移動量となる。バックトラック
• DFSであるパスをそれ以上深く辿れない時，一つ前 の状態に戻って別のパスを辿る →この操作をバックトラック（後戻り）と呼ぶ • ８クィーン問題 チェス盤面で，お互いの利き筋（縦，横，斜め）にの らないように8個のクィーンを配置する問題．92通り の解がある．バックトラックの代表的適用問題． http://web.hc.keio.ac.jp/~fujimura/index.htmlQ
Q
Q Q
Q Q
８クイーンの出力例
Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ (a) Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ (b) 一次元配列 q[0]-q[7]でクィーンの配置を記述する．添え字を列に対応させる． 左図は[0,4,7,5,2,6,1,3]．右図は？ q[0]-q[7]までDFSでサーチする Put-Q(x):クィーンの置ける位置=ｑ［ｘ]の値を決める． 初期値 q[x]=0 増分 1 (q[x]=q[x]+1) 終了条件q[x]<=8○ ○ ○ ○ ○ ○
PUT-Q(0) PUT-Q(1) PUT-Q(2) PUT-Q(3) PUT-Q(4) PUT-Q(5)
× × × 1 2 3 4 5 6 7 q［x］= 0
バックトラッキングの様子
深さ優先探索
0 1 2 3 4 5 6 7 0 Q 1 Q x 2 Q 3 Q x 4 Q 5 6 Q 7 Q x Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ Q ・ ・ ・ ・ ・ ・ ・ (a) １番目の解 q[0]-q[7]までDFSでサーチする Put-Q(x):クィーンの置ける位置=ｑ［ｘ]の値を決める． 初期値 q[x]=0 増分 1 (q[x]=q[x]+1) 終了条件q[x]<=8
変更
• 左から右へ、上から下へ、置ける場所を探す • ある行に置けたら、その右の列の上から置ける場所を探す • ある列のどこにも置けないと判ったら、 ひとつ左の列の置 ける場所を探す作業を継続する • 一番右の列で置ける場所が見つかったら、一丁あがり • さらに他の解も探すのであれば、ひとつ下の行の続きを探 す。一番左の列の置ける位置を全部調べ終わるまで続け る解が見つかったあとの バックトラッキングの様子 強制バックトラックによる全解探査 1 2 3 4 5 6 7 q［x］= 0 PUT-Q(6) PUT-Q(7) ○ ● クイーンの 配置を表示
開始
終了 PUT-Q(0)
戻る (b) PUT-Q(x) q［x］←0 q［x］←q［x］＋1 PRT-Q false true ＝ ≠ ≧ ＜ c ← CHK-Q(x,q［x］) PUT-Q(x＋1) クィーンの置ける位置 =ｑ［ｘ]の値を決める．
クィーンの置ける位置 =ｑ［ｘ]の値を決める． 戻る (b) PUT-Q(x) q［x］←0 q［x］←q［x］＋1 PRT-Q false true ＝ ≠ ≧ ＜ c←CHK-Q(x,q［x］) PUT-Q(x＋1)
c
X:7
q[x]:8利き筋のチェック CHK-Q(x，y) i←0 ＝ ≠ ≧ ＜ i←i＋1 ret←true retを返す ≠ ≠ ret←false ＝ ＝ (a)
利き筋のチェック CHK-Q(x，y) i←0 ＝ ≠ ≧ ＜ i←i＋1
i:x
ret←true retを返す ≠ ≠ ret←false ＝ ＝ (a) q[i]:y利き筋のチェック CHK-Q(x，y) i←0 ＝ ≠ ≧ ＜ i←i＋1 ret←true retを返す ≠ ≠ ret←false ＝ ＝ (a) q[i]:y q[i]:y-x+i q[i]:y+x-i i:x 行＋列が同じ →右上がりチェック 行－列が同じ →右下がりチェック 行が同じ →横チェック
戻る PRT-Q ．を出力 Qを出力 改行を出力 q［j］：i ループA iの初期値0 増分1 i ≧8 ループB jの初期値0 増分1 j ≧8 ループA ループB ≠ ＝ (b) 結果表示の サブルーチン
