fc2ブログ



Knuth Morris Pratt (KMP) algorithm

2006.05.29 05:27  文字列

Knuth, Morris, Pratt によって考案された KMP アルゴリズムは、T[n], P[m] に対して最悪の場合でも n + m 回の比較で文字列照合を行うことができます(O(n + m))。

Brute force アルゴリズムでは、不一致 T[i] ≠ P[j] が検出されると、i = i - j + 1 として i のポインタをリセットしていました。KMP アルゴリズムは、不一致 T[i] ≠ P[j] を検出した時点で、テキストとパタンがどこまで一致しているかが分かっていることを有効に利用します。つまり不一致 T[i] ≠ P[j] を検出した時点で 1 ≦ k ≦ j について T[i - k] = P[j - k] ということが既に分かっているのです(下図参照)。

kmp1.gif

具体的な例をいくつか見てみましょう。

Case 1:

右図の例において、不一致 T[i] ≠ P[j] が検出された時点で、T[i - j] = b, T[i - j + 1] = a, ... T[i - 1] = a ということが既に分かっています。 kmp2.gif
つまり、P[0] = b ということから ( T[1] = T[2] = T[3] ) ≠ P[0] ということが既に分かっているので、Brute force のように i のポインタを i - j + 1 に後戻りさせるのは明らかに無駄な処理を発生させます。 kmp3.gif
この例の場合、i はそのまま、j = 0 としてパタンのチェックを再開することができます。 kmp4.gif

Case 2:

右図の例において、不一致 T[i] ≠ P[j] が検出された時点で、T[0] = T[2] = a, T[1] = T[3] = b ということが既に分かっています。 kmp5.gif
P[0] ≠ P[1] = T[1] ということが既に分かっているので、Brute force のように i のポインタを i - j + 1 に後戻りさせるのは無駄になります。 kmp6.gif
では、テキトウに i を1つだけ後戻りさせてみましょう(i = i - 1)。しかしこれは、P[0] = T[2], P[1] = T[3] という事実、つまりパタンを見逃してしまいます。これは、少なくとも i を1つしか後戻りさせなかったら、パタンを見逃してしまうことを意味します。 kmp7.gif
この例の場合、i を2つ後戻りさせ(i = i - 2)、チェックを再開することが正しいのです。 kmp8.gif

KMP アルゴリズムでは、この「P[j] の位置で不一致が検出された時、i をどこまで後戻りさせるか」をテーブル N として記録しておき有効利用します。N の値は P にのみ依存することから、N は照合の処理をする前にあらかじめ計算しておくことができます。

j > 0 に対する N[j] の値は、k < j かつ パタンの先頭から j 文字の部分列において、最初の k 文字と最後の k 文字が一致するような最大の k です。

kmp9.gif

このパタンをあるテキストと照合してみましょう。

kmp10.gif

P[8] で不一致が検出されたとすると、k = N[8] = 5 なので、i を 5 つ後戻りさせ照合を再開すればよいことになります。

kmp11.gif

しかし、上で述べたように、 1 ≦ k ≦ j について T[i - k] = P[j - k] ということが既に分かっているので、元の i の位置から再開することができます。従って、N[j] は「i をどこまで後戻りさせるか」と表現するよりは「j をどこから再開するか」と表現した方が直感的に分かりやすいと思います。

kmp12.gif

ただし、P[0] で不一致が検出された場合は、無条件に i = i + 1, j = 0 となります。この例外処理を行うために、以下のプログラムのように N[0] = -1 としておくと便利です。

void initNext( string P, int m, int N[]){
    int i, j;
    N[0] = -1;
    for ( i = 0, j = -1; i < m; i++, j++, N[i] = j )
    while( ( j >= 0 ) && ( P[i] != P[j] ) ) j = N[j];
}

int KMPSearch( string T, int n, string P, int m ){
    int N[MAX];
    initNext( P, m, N );
    
    int i, j;
    i = j = 0;
    while ( i < n ){
        while( i < n && j < m ){
            while ( j >= 0 && T[i] != P[j] ) j = N[j];
            i++; j++;
        }
        if ( j == m ) {
            print( i - j );
            j = N[j];
        }
    }
}

上記のプログラムは、若干巧妙なので、P[0] で不一致が検出されたときの処理を明示的に書いたプログラム例を以下に示します。

void initNext( string P, int m, int N[]){
    int i, j;
    N[0] = -1;
    for ( i = 0, j = -1; i < m; i++, j++, N[i] = j )
    while( ( j >= 0 ) && ( P[i] != P[j] ) ) j = N[j];
}

int KMPSearch( string T, int n, string P, int m ){
    int N[MAX];
    initNext( P, m, N );
    
    int i, j;
    i = j = 0;
    
    while ( i < n ){
        while( i < n && j < m ){
            if ( j == 0 ){
                if ( T[i] != P[j] ){ j = 0; i++; }
                else { i++; j++; }
            } else {
                if ( T[i] != P[j] ){ j = N[j]; }
                else { i++; j++; }
            }
        }
        if ( j == m ) {
            printf("P appers at %d\n", i - j); j = N[j];
        }
    }
}
スポンサーサイト



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

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

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

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

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

↑ページトップ