Knuth Morris Pratt (KMP) algorithm

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] ということが既に分かっているのです（下図参照）。

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

Case 1:

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

Case 2:

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

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

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

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

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

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

ただし、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];
        }
    }
}

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

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

T[i] ≠ P[j] が検出されたときに、i = i - j + 1 (次の i の位置) j = 0 (パタンの先頭)にリセットします。（下図参照） 文字列照合アルゴリズムでは、文字を比較する回数により計算効率を評価します。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 の流れ

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;
        }
    }
}

String matching problem 文字列照合

ある文字列（テキスト）に対して、指定された照合文字列（パタン）の存在を発見するための機能は、多くのテキストエディタに実装されています。「テキストが変更中のドキュメントで、パタンがユーザーが探したい特定のキーワード」というのが典型的な例でしょう。

この文字列照合問題のための効率の良いアルゴリズムは、テキストエディタのプログラムには不可欠です。また、文字列照合アルゴリズムは、ＤＮＡ配列中の特定のパタンを発見したり、インターネットにおけるキーワード検索など、様々な場面で応用されます。

文字列照合問題は以下のように形式化されます。
文字列 T[n] を長さ n のテキスト、文字列 P[m] を長さ m のパタンとし、T と P の各要素はある有限の集合 S に属するとします。例えば、S = {0, 1}、S = {0, 1, 2, ..., a, b, ... z} などが考えられます。

「 0 ≦ i ≦ n - m 」 かつ 「 0 ≦ j ≦ m - 1 について P[j] = T[i + j] 」を満たすとき、「テキスト T の i の位置にパタン P が存在する」と言います（下図参照）。

例: i = 3 P[0] = T[3 + 0] = T[3] P[1] = T[3 + 1] = T[4] P[2] = T[3 + 2] = T[5]

文字列照合問題は、テキストの中に存在する指定されたパタンの全ての位置を発見する問題です。

これから紹介していこうと思うアルゴリズムです↓

• Brute-force algorithm 力任せの文字列照合アルゴリズム
• Knuth-Morris-Pratt (KMP) algorithm
• Boyer-Moore algorithm