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

具体的な例をいくつか見てみましょう。
Case 1:
Case 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]; } } }
| コメント(0) | トラックバック(0) | ↑ページトップ |