文字列探索 2011/5/30
テキスト中で指定されたパターンが出現する 探索する文字列を「パターン」 探索する対象分を「テキスト」と呼ぶ テキスト中で指定されたパターンが出現する 場所を見つける操作
力任せのアルゴリズム
力任せ法の計算量 テキストをm字、パターンをn字とすると (m-n+1)xn 計算量 O(mn) 実質的計算量 O(n)
KMP法 1970年、Cookが理論的に示唆 計算量O(m+n) D.E.KnuthとV.R.Pratt,Morrisが開発 計算量O(n)
KMP法の動き(1)
KMP法の動き(2)
KMP法の動き(3)
KMP法における前準備 ずらし表の作成 パターン “tartar” 「パターンの i 文字目で失敗した時に、何文字ずらして再開するか」 NEXT(0)=1 NEXT(3)=3 NEXT(1)=1 NEXT(4)=3 NEXT(2)=2 NEXT(5)=3
KMP法の能力 O(n) しかしながら、実際的に力任せ法と大して変わらない。
BM法 1977年にR.S.BoyerとJ.S.Moore 計算量 最悪の場合でも O(n), 平均的な場合(文字の種類が多く,パター ンがあまり長くない)にはO (n/m) 効率的
BM法
BM法
BM法
BM法
bad-character-shift
Bad-character-shift ANPANMANに対するbad character shift の計算 N 0 A 1 M 2 他のあらゆる文字 8
good-suffix-shift
good-suffix-shift ANPANMAN n 1 aN 8 mAN 3 nMAN 6 aNMAN 6 pANMAN 6 nPANMAN 6 aNPANMAN 6
bad-character-shiftとgood-suffix-shift ANMKODSAZANPANMOPOP ANPANMAN good-suffix shift の場合 shift=3 i=+2 ↓
bad-character-shiftとgood-suffix-shift ANMKODSAZANPANMOPOP ANPANMAN bad-character-shiftの場合 shift=6 i=+8 ↓ ANPANMAN
参考文献 Wikipedia /english http://www-igm.univ-mlv.fr/~lecroq/string/node14.html