santamonikancrew

アクセスカウンタ

zoom RSS 課題 6月23日のレポート

<<   作成日時 : 2005/06/25 13:26   >>

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

単純な文字列照合
文字列を検索する一番簡単な方法は、検索対象の文字列の最初から探す文字列(キー文字列)が含まれているか一字づつ探していく事です。例えば、3文字のキー文字列の最初の文字が見つかったら、検索対象文字列のその次の文字がキー文字列の2字めと一致するか調べ、一致したら3字目を調べます。もし3文字目まで一致すれば、3文字のキー文字列がすべて一致したわけで、検索対象文字列のその部分にキー文字列が含まれている事になるでしょう。

引用文献(http://www.sm.rim.or.jp/~shishido/search1.html)

KMP法(Knuth-Morris-Pratt algorithm)
Donald Knuth氏,James Morris氏,Vaughan Pratt氏らが発見した文字列探索アルゴリズムです.
一般に,力任せに単純に文字列探索を行なうと,ある開始位置からパターン文字列のマッチングを開始し,そこで失敗したら,開始位置を1文字ずらしてさらにマッチングを行ないます.したがって,場合によってはマッチングで文字を読み進めても,さらに戻ってマッチングを開始することがあります.
abb???????? ... 対象文字列
abbb ... パターン文字列
abbb
abbb
abbb ←ここまで進めばよい
しかし,KMP法では,そのような逆行が存在しません.例えばパターン文字列がabbbであったとして,3文字目のbまではマッチして,最後の4文字目のbでマッチ失敗したとしましょう.すると,マッチ失敗したのは abb? という文字列であったわけですから,次にabbbをマッチさせるならば,先ほどマッチ失敗した4文字目の位置から試せば十分なのです.
aba???????? ... 対象文字列
abaa ... パターン文字列
abaa
abaa ←ここまで進み,なおかつ,2文字目からマッチ開始すればよい
また,パターン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日のレポート santamonikancrew/BIGLOBEウェブリブログ
文字サイズ:       閉じる