カンボ亭

アクセスカウンタ

zoom RSS 6月23日の課題

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

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

・単純な文字列照合
単純な文字列照合とは、照合される文字列を頭から順に照合する文字列と比較して、違ったら1文字ずつ後ろにずらしながら処理を行うことである。

TOKKYOKYOKAKYOKU←照合される文字列
KYOKU           ←照合する文字列
 KYOKU
      ・
      ・
      ・
         KYOKU
          KYOKU←一致した
・KMP法
KMP法とはDonald Knuth氏,James Morris氏,Vaughan Pratt氏らが発見した文字列探索アルゴリズムで、単純な文字列照合と違って左から順に照合するのではなく、照合する文字列を1文字目、2文字目・・・とマッチさせていく方法である。

TOKYOKYOKAKYOKU←照合される文字列
  KYOKU        ←4文字目までマッチする
     KYOKU     ←3文字目までマッチする
         KYOKU←全文字マッチする

・BM法
BM法とは、 KMP法よりもさらに高速な照合法で、n/m 個(nはテキストの長さ、mは照合パターンの長さ)の文字とだけ比較する方法である。これによって、特に照合パターンが長いときに、計算時間の大幅な短縮が期待できる。

・参考文献
検索アルゴリズム
http://www2.starcat.ne.jp/~fussy/algo/algo7-3.htm
KMP法
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82F4B4D50CBA1.html
BM法による文字列照合
http://bal4u.dip.jp/mt/program/archives/2004/09/bmbmmatch.html

月別リンク

ブログ気持玉

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

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

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