fc2ブログ



Brute force algorithm 力任せな文字列照合アルゴリズム

2006.05.25 21:57  文字列

文字列照合を行うための最も自明(素朴)な方法は、テキスト内のパタンが存在する可能性のある全ての位置を順番にチェックするものです。テキストの位置 i が 0 から n - m について、T[i + j] = P[j] ( 0 ≦ j ≦ m - 1 ) を満たすかをチェックします。

T[i] ≠ P[j] が検出されたときに、i = i - j + 1 (次の i の位置) j = 0 (パタンの先頭)にリセットします。(下図参照)
bruteForce2.gif


文字列照合アルゴリズムでは、文字を比較する回数により計算効率を評価します。Brute force algorithm は最悪の場合 m( n - m + 1) 回の比較が必要なので、m が n に比べて十分小さいと考えるとオーダーは O(nm) となります。例えば、テキスト "000000001" に対して、パタン "001" の照合がこの最悪のケースを引き起こします(試してみましょう)。

しかし、実際のテキストエディタなどのアプリケーションで、この最悪のケースが発生することはないと考えて良いでしょう。なぜなら、T[i + j] と P[j] をチェックする内側のループは高確率で j = 0 のときに終了することが考えられるからです。従って、文字コードが多い実際の文字列に対しては、Brute force algorithm で十分実用的なのです。

しかし一方で、先ほどの例のように、バイナリ(S = {0, 1})のテキストなど、ある特定の文字列に対しては非常に効率が悪くなります。
Brute force algorithm の流れ
bruteForce.gif


int bruteForceSearch( string T, int n, string P, int m ){
    int i, j;
    i = j = 0;
    while ( i <= n - m ){
        while( i < n && j < m ){
            if ( T[i] != P[j] ){
                i = i - j + 1; j = 0;
            } else { i++; j++; }
        }
        if ( j == m ) {
            match( i - j );
            i = i - j + 1; j = 0;
        }
    }
}
スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ