文字列探索 2011/5/30 • 探索する文字列を「パターン」 • 探索する対象分を「テキスト」と呼ぶ テキスト中で指定されたパターンが出現する 場所を見つける操作 力任せのアルゴリズム 力任せ法の計算量 テキストをｍ字、パターンをｎ字とすると （ｍ－ｎ＋１）ｘｎ • 計算量 Ｏ（ｍｎ） • 実質的計算量 Ｏ（ｎ） ＫＭＰ法 • 1970年、Cookが理論的に示唆 計算量Ｏ(m+n） D.E.KnuthとV.R.Pratt,Morrisが開発 計算量Ｏ（ｎ） ＫＭＰ法の動き（１） ＫＭＰ法の動き（２） ＫＭＰ法の動き（３） ＫＭＰ法における前準備 • ずらし表の作成 パターン “tartar” 「パターンの i 文字目で失敗した時に、何文字 ずらして再開するか」 • NEXT(0)=1 • NEXT(1)=1 • NEXT(2)=2 NEXT(3)=3 NEXT(4)=3 NEXT(5)=3 KMP法の能力 • Ｏ（ｎ） • しかしながら、実際的に力任せ法と大して変 わらない。 ＢＭ法 • 1977年にR.S.BoyerとJ.S.Moore • 計算量 • 最悪の場合でも O(n)， • 平均的な場合(文字の種類が多く，パター ン があまり長くない）にはO (n/m) • 効率的 ＢＭ法 ＢＭ法 ＢＭ法 ＢＭ法 bad-character-shift Bad-character-shift ANPANMANに対するbad character shift の計算 • • • • • N 0 A 1 M 2 P 5 他のあらゆる文字 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 ↓i ＡＮＭＫＯＤＳＡＺＡＮＰＡＮＭＯＰＯＰ ＡＮＰＡＮＭＡＮ • good-suffix shift の場合 shift=3 i=+2 ↓ ＡＮＭＫＯＤＳＡＺＡＮＰＡＮＭＯＰＯＰ ＡＮＰＡＮＭＡＮ bad-character-shiftとgood-suffix-shift ↓i ＡＮＭＫＯＤＳＡＺＡＮＰＡＮＭＯＰＯＰ ＡＮＰＡＮＭＡＮ • bad-character-shiftの場合 shift=6 i=+8 ↓ ＡＮＭＫＯＤＳＡＺＡＮＰＡＮＭＯＰＯＰ ＡＮＰＡＮＭＡＮ 参考文献 • Wikipedia /english • http://www-igm.univmlv.fr/~lecroq/string/node14.html
© Copyright 2024 ExpyDoc
