文字列探索 2011/5/30.

Presentation on theme: "文字列探索 2011/5/30."— Presentation transcript:

1 文字列探索 2011/5/30

2 テキスト中で指定されたパターンが出現する
探索する文字列を「パターン」 探索する対象分を「テキスト」と呼ぶ テキスト中で指定されたパターンが出現する 場所を見つける操作

3 力任せのアルゴリズム

4 力任せ法の計算量 テキストをｍ字、パターンをｎ字とすると 　　　　　（ｍ－ｎ＋１）ｘｎ 計算量　　Ｏ（ｍｎ） 実質的計算量　Ｏ（ｎ）

5 ＫＭＰ法 1970年、Cookが理論的に示唆 　　計算量Ｏ(m+n） D.E.KnuthとV.R.Pratt,Morrisが開発 　計算量Ｏ（ｎ）

6 ＫＭＰ法の動き（１）

7 ＫＭＰ法の動き（２）

8 ＫＭＰ法の動き（３）

9 ＫＭＰ法における前準備 ずらし表の作成 パターン “tartar” 「パターンの i 文字目で失敗した時に、何文字ずらして再開するか」
NEXT(0)= NEXT(3)=3 NEXT(1)= NEXT(4)=3 NEXT(2)= NEXT(5)=3

10 KMP法の能力 Ｏ（ｎ） しかしながら、実際的に力任せ法と大して変わらない。

11 ＢＭ法 1977年にR.S.BoyerとJ.S.Moore 計算量 最悪の場合でも O(n)，
平均的な場合(文字の種類が多く，パター ンがあまり長くない）にはO (n/m) 効率的

12 ＢＭ法

13 ＢＭ法

14 ＢＭ法

15 ＢＭ法

16 bad-character-shift

17 Bad-character-shift ANPANMANに対するbad character shift の計算 N 0 A 1 M 2
他のあらゆる文字 8

18 good-suffix-shift

19 good-suffix-shift ANPANMAN n 1 aN 8 mAN 3 nMAN 6 aNMAN 6 pANMAN 6 nPANMAN 6 aNPANMAN 6

20 bad-character-shiftとgood-suffix-shift
ＡＮＭＫＯＤＳＡＺＡＮＰＡＮＭＯＰＯＰ 　 　ＡＮＰＡＮＭＡＮ good-suffix shift の場合 shift=3 i=+2 ↓

21 bad-character-shiftとgood-suffix-shift
ＡＮＭＫＯＤＳＡＺＡＮＰＡＮＭＯＰＯＰ 　 　ＡＮＰＡＮＭＡＮ bad-character-shiftの場合 shift=6 i=+8 　　　　　　　　　　　　　　　　　　 ↓　　　　　 　 ＡＮＰＡＮＭＡＮ

22 参考文献 Wikipedia /english