ハロー

アクセスカウンタ

zoom RSS 課題

<<   作成日時 : 2005/06/25 09:24   >>

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

イ 単純な文字列照合
 文字列の照合は、文字列の探索ともいう。「テキスト」と呼ばれる文字列の中に、「パターン」と呼ばれる文字列に一致する部分があるかどうかを調べ、そのような部分が見つかった場合には、さらにその場所を答える。テキスト・エディタにおける探索コマンドやデータベースにおける検索などに使われ、使用頻度の多い操作です。いまの時代になって、WWWページの全文検索にも利用されます。

ロ KMP法
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法です.

ハ BM法(BMH法)
BoyerとMoore、また両者とは別にGosperが考案したBoyer-Moore(BM)法の最大の特徴は、パターンを末尾側から逆方向に比較するということです。
テキストとパターンの先頭をそろえた後、今までのアルゴリズムではパターン先頭とテキスト先頭を比較するのですが、BM法ではパターン末尾(先頭からm文字目)の文字と、テキストのm文字目の文字を比較します。もし一致していたら注目文字を1つ前にずらし、末尾側から逆方向に比較していきます。もし不一致が検出されたら、不一致を引き起こしたテキスト側の文字に注目して、もしその文字がパターン中に含まれていたら、両者が重なる位置までパターンを右にずらします。そうしないと、同じ場所で再び不一致を検出してしまうからです。また同じ理由により、不一致を引き起こしたテキスト上の文字がパターン中に含まれていない場合、パターン先頭を不一致を起こしたテキスト上の文字より次の位置にまでずらすことができます。
文字列の照合は、文字列の探索ともいう。「テキスト」と呼ばれる文字列の中に、「パターン」と呼ばれる文字列に一致する部分があるかどうかを調べる問題。そのような部分が見つかった場合には、さらにその場所を答えるのがBM法です。

参考文献
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82F4B4D50CBA1.html
http://www2.starcat.ne.jp/~fussy/algo/algo7-4.htm
http://bal4u.dip.jp/mt/program/archives/2004/09/fpnaivematch.html

月別リンク

ブログ気持玉

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

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
課題 ハロー/BIGLOBEウェブリブログ
文字サイズ:       閉じる