サイコ

アクセスカウンタ

zoom RSS 6月23日の課題

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

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

3.文字列照合(string pattern matching)アルゴリズム
(1)単純な文字列照合 
文字列照合はデータ処理、文書編集、項書き換え、字句解析、情報検索、
さらには多くのテキストエディタやプログラミング言語に利用されています。
先頭から順番に一文字ずつ照合していく方法であり、頭から照合していき
違っていたら、1文字ずつ後ろへずれながら処理を繰り返す。

(2)Knuth-Morris-Pratt法(KMP法)
一般に、力任せに単純に文字列探索を行なうと、
ある開始位置からパターン文字列のマッチングを開始し、
そこで失敗したら、開始位置を1文字ずらしてさらにマッチングを行ないます。
したがって、場合によってはマッチングで文字を読み進めても、
さらに戻ってマッチングを開始することがあります。

(3)Boyer-Moore法(BM法)
文字列検索で最高速といわれるBM法。
BM法は、検索する文字列の末尾から比較するのが特徴で、
一致しないパターン分だけ後ろに移動できるので、比較の回数が少なくてすむ。
しかし、検索する文字列に同じ文字がある場合の処理のため、最初に配列を作る。

「KMP法とBM法を比較してわかったこと」
KMP法では照合が前から始めるのにたいして、BM法では後ろから始めること。

「参考文献」
http://www.mz.cs.it-chiba.ac.jp/95/nishi.html
http://www.pc-view.net/Solution/040120/page72.html
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82F4B4D50CBA1.html
http://homepage3.nifty.com/kenjiroom/prog/


 

月別リンク

ブログ気持玉

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

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
6月23日の課題 サイコ/BIGLOBEウェブリブログ
文字サイズ:       閉じる