whizzihwな気分で行こう

アクセスカウンタ

zoom RSS 6月23日の課題について

<<   作成日時 : 2005/06/25 14:57   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

単純な文字列照合
一番単純な文字列照合の方法は、先頭から順番に一文字ずつ照合していく方法である。
参考文献
http://www.pc-view.net/Solution/040120/page72.html

KMP法(Knuth-Morris-Pratt algorithm)
Donald Knuth氏,James Morris氏,Vaughan Pratt氏らが発見した文字列探索アルゴリズムです.
一般に,力任せに単純に文字列探索を行なうと,ある開始位置からパターン文字列のマッチングを開始し,そこで失敗したら,開始位置を1文字ずらしてさらにマッチングを行ないます.したがって,場合によってはマッチングで文字を読み進めても,さらに戻ってマッチングを開始することがあります.
しかし,KMP法では,そのような逆行が存在しません.例えばパターン文字列がabbbであったとして,3文字目のbまではマッチして,最後の4文字目のbでマッチ失敗したとしましょう.すると,マッチ失敗したのは abb? という文字列であったわけですから,次にabbbをマッチさせるならば,先ほどマッチ失敗した4文字目の位置から試せば十分なのです.
また,パターンabaaに対して,最後のaで失敗したとすれば,今度は3文字目からマッチを開始しますが,既に最初のaがマッチすることは明らかですので,3文字目からのマッチ開始で,なおかつ3文字目は既にマッチ成功とみなして4文字目からマッチ開始をすればよいのです.いずれにしても,既に読んだ文字列を逆行することはありません.
一般に,パターン中でマッチ失敗したときに,次に何文字ずらせばよいかはパターンのみから決定されます.これをnext表という形でパターンのそれぞれの位置に対して保持しておきます.そして,この表を用いてマッチを進めていくのがKMP法です.
引用文献(http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82F4B4D50CBA1.html

BM法(BMH法)
文字列からあるパターンを探索するとき、パターンを後ろから比較することで比較回数を減らそうってアルゴリズムです。
引用文献(http://d.hatena.ne.jp/Sampo/200407



月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
6月23日の課題について whizzihwな気分で行こう/BIGLOBEウェブリブログ
文字サイズ:       閉じる