九州アイランド

アクセスカウンタ

zoom RSS 6月23日の課題

<<   作成日時 : 2005/06/25 01:00   >>

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

(1)Boyer, Moore法(BM法)
BMアルゴリズムの特徴
Boyer, MooreによるBMアルゴリズムは,パターンの右端から文字比較を行うアイデアによって,多くの場合,テキストの文字のいくつかを読み飛ばすことができ,最も高速なアルゴリズムとして知られています.しかし、検索する文字列に同じ文字がある場合の処理のため、最初に配列を作ります。

テキストを走査する前に,前処理として,パターンから二つの関数delta1, delta2を構成する. delta1の構成に要する時間は,パターン長をm,アルファベットサイズをqとするとき, O(q+m)時間です.
また, delta2の構成に要する時間はO(m)時間です.
テキストの文字の参照回数で効率を評価するとき,平均時の参照回数はテキスト長より小さい.一方,再悪時にはO(mn)回の参照を行います.

(2)KMP法(Knuth-Morris-Pratt algorithm)
Donald Knuth氏,James Morris氏,Vaughan Pratt氏らが発見した文字列探索アルゴリズムです.

KMPアルゴリズムの特徴
Knuth, Morris, PrattによるKMPアルゴリズムは,文字列パターン照合問題が線形時間で解けることを最初に示したアルゴリズムです.テキストを走査する前に,前処理として,パターンからnextという関数を構成する.この関数は,パターン長をmとするとサイズm+1の配列により表現できる.この構成に要する時間は,O(m)時間になります.
テキスト長をnとするとき,文字比較の回数は高々2n回です.したがって,テキスト走査時間はO(n)時間です.
KMPアルゴリズムはテキストの文字を左から1文字ずつ読むたびに jの値を更新していくものです.これは,Aho-Corasickのパターン照合機械の状態遷移に相当します.


(3)単純な文字列照合(string pattern matching)

一番単純な文字列照合の方法は、先頭から順番に一文字ずつ照合していく方法です。文字列照合の対象とする文字列をstr、照合文字列をpatternとすると、次のようにカウンタi,jを用意して比較を進めていけば良いです。途中で一致しない文字が出現すればmatchはfalseとなりますが、すべて一致していればmatchはtrueでこの処理を終了します。この処理の終了時のmatchを参照することにより、文字列照合の結果を判断できます。

参考文献
http://www.i.kyushu-u.ac.jp/~takeda/PM/BM/bm.html
http://homepage3.nifty.com/kenjiroom/prog/
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82F4B4D50CBA1.html 
http://www.pc-view.net/Solution/040120/page72.html              etc

参考文献はYahoo検索サイトで調べました。




月別リンク

ブログ気持玉

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

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

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