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