メインコンテンツへ移動
黯羽軽揚毎日少しずつ

古典的な文字列マッチングアルゴリズム（KMP）解析

無料2015-03-17#Math#串匹配算法#KMP

問題の背景は、元の文字列中で与えられた文字列と完全に一致する部分を見つけることです。最も簡単に思いつく二重ループでの比較は当然できません（時間計算量が高すぎる）。最も古典的な解法は KMP アルゴリズムで、まずジャンプテーブル（next テーブル）を構築し、その後比較し、メイン文字列上のバックトラックを回避して時間を節約します。KMP アルゴリズムは理解が難しいため、本記事ではその核心である next 関数について解析します。

no_mkd

一.問題の再述

文字列 S1 があり、S1 中で文字列 S2 と完全に一致する部分を求めます。例えば：S1 = "ababaababc", S2 = "ababc"

マッチング結果は 5 になります（S1 中の"ababc"の a の位置）。もちろん S1 中に複数の S2 があっても関係ありません。1 つ目を見つけられれば 2 つ目も見つけられます。。

最も簡単に思いつく方法は二重ループで桁ごとに比較することです（BF アルゴリズム）が、最悪の場合 BF アルゴリズムの時間計算量は m * n に達し、これは実際のアプリケーションでは受け入れられません。そこで 3 人の人が KMP アルゴリズムを考え出しました（KMP は 3 人の名前です。。）

二.KMP アルゴリズムの具体的過程

（まず KMP アルゴリズムの公式定義を見ようとしてはいけません。非常に理解しにくいので、ここでは定義を提示しません。。）

S2 = "ababc" を注意深く観察してください。重要な点は：先頭に ab が現れ、中間部分にも ab が現れていることです（この詳細を覚えておいてください）

ある瞬間を想定します：

この時 abab 部分のマッチングは成功し、S1 の位置ポインタは a を指しており、現在行っていることは a と c の比較で、結果はマッチング失敗です

  • BF アルゴリズムの場合、次のステップは S1 の位置ポインタを 2 番目の b にバックトラックし、S2 の位置ポインタを先頭の a にリセットし、その後 b と a を比較し、その後。。
  • KMP アルゴリズムの場合、次のステップは S1 の位置ポインタを変えず（a を指したまま）、ジャンプテーブル（next テーブル）を照会してジャンプ値 2 を取得し、S2 のポインタを 2 番目の a に移動し、その後 a と a を比較し、その後。。

KMP のステップが理解できなくても関係ありません。ジャンプテーブル（next テーブル）が何かまだ説明していないので。ここでは結果だけ关注してください：

  • BF アルゴリズムでは S1 のポインタが左に移動しました（バックトラック）
  • KMP アルゴリズムでは S1 のポインタは戻りませんでした（バックトラックなし）

KMP アルゴリズムにはバックトラックプロセスが存在しないため、多くの時間を節約できます（S1 のポインタは先頭から末尾まで歩くだけで済みます）

KMP アルゴリズムの核心であるジャンプをもう一度見てみましょう

なぜジャンプできるのか？S2 = "ababc" を注意深く観察してください。この文字列の特徴は：先頭に ab が現れ、中間部分にも ab が現れていることです（この詳細を覚えていますか）。詳しく説明します：

S2 末尾の c が S1 の第 k 位とのマッチングに失敗した場合、2 つの情報を推測できます：

  1. 今回のマッチングは失敗しました（c のマッチング失敗は S1 中の某一部分が S2 とマッチングできないことを意味します）
  2. S1 中の第 k 位の前の 4 位は必ず abab です（S2 中の abab と S1 中の某一部分のマッチングが成功した後でなければ、S2 の c と S1 第 k 位の比較は発生し得ません）

第 2 点を無視すれば、次のステップは S1 ポインタのバックトラック、つまり BF アルゴリズムが行うことになります。第 2 点を掴み、さらに S2 文字列の特徴：

  • 先頭に ab が現れ、中間部分にも ab が現れている（もう一度強調します）

を加味すれば KMP アルゴリズムが得られます（S1 中の第 k 位の前の ab が S2 先頭の ab とマッチング済みなので、S1 の第 k 位と S2 の第 3 位 a の比較に直接ジャンプできます）

少し理解できたようです。ではこのジャンプ値 2 はどのようにして得られるのか？もっと例を挙げます：

  • S2 = "aba" 最後の位のジャンプ値は 0
  • S2 = "abaa" 最後の位のジャンプ値は 1
  • S2 = "abcabc" 最後の位のジャンプ値は 2

何か発見しましたか？そうです。S2 中の第 x 位（ここでの x は 0 から数えます）のジャンプ値を求めるプロセスは以下の通りです：

  1. x = 0 の場合、S2[x] のジャンプ値は -1（先頭要素のジャンプ値は -1）
  2. x = 1 の場合、S2[x] のジャンプ値は 0（2 番目の要素のジャンプ値は 0）
  3. S2[x - 1] = S2[0] の場合、S2[x] のジャンプ値は 1
  4. 第 3 条を満たさない場合、ジャンプ値は 0
  5. S2[x - 1] = S2[0] かつ S2[x - 2] = S2[1] の場合、S2[x] のジャンプ値は 2
  6. S2[x - 1] = S2[0] かつ S2[x - 2] = S2[1] かつ S2[x - 3] = S2[2] の場合、S2[x] のジャンプ値は 3
  7. 。。。

人が目で上記の方法に従ってジャンプ値を「目測」するのが最も速いですが、同じプロセスをコンピュータに適用するのはそれほど簡単ではありません。コンピュータにはコンピュータが好む方式があります。一篇の簡短な博文がこの方式を説明しています

簡単に言えば——「漸化式」、つまり既知の初項が -1、2 項目が 0 であることから、漸化式で後面のすべての項を得ます。詳細な過程は省略します。上記のリンク博文が非常に明確に書いています

以下で KMP アルゴリズムの具体的過程が得られます：

  1. パターン文字列 S2 に基づいてジャンプテーブル（next テーブル）を構築
  2. S1 先頭から比較を開始し、next テーブルを照会してジャンプ値を取得し、S1 ポインタを右に移動して比較を継続し、S1 末尾まで

言い換えれば、また空間で時間を交換しています（next テーブルが占有する空間）。も��ろん、このアルゴリズムでは next テーブルはパターン文字列 S2 の長さに等しい線形テーブルに過ぎず、多くの空間を必要としません

三.next 関数の実装

next 関数は next テーブル（ジャンプテーブル）を構築するために使用されます。next テーブルをどのように構築するかが KMP アルゴリズムの鍵です（KMP の証明プロセスに关注しない場合。。）。リンク博文の方式に従って自分で next 関数を実装できます：

//参考例子：http://blog.sina.com.cn/s/blog_96ea9c6f01016l6r.html

#include<stdio.h>


void getNext(char a[], int n, int next[]){
int i, j;


next[0] = -1;//首元跳转值为 -1
next[1] = 0;//第二个元素跳转值为 0

for(i = 2; i &lt; n; i++){
	j = i - 1;
	
	//递推得到 next 表中剩余值
	while(j != -1){
		if(a[i - 1] == a[next[j]]){
			next[i] = next[j] + 1;
			break;
		}
		else{
			j = next[j];
		}
	}
}



}


main(){
char a[] = "abaabcac";//模式串 S2
int next[8] = {0};//跳转表，初始化为全 0
int i;


//构造 next 表
getNext(a, 8, next);
//输出 next 表
for(i = 0; i &lt; 8; i++){
	printf("%d ", next[i]);
}
printf("\n");



}

もちろん、上記の getNext 関数はまだ効率的ではないようです（二重ループ。。）が、利点は理解しやすいことです。以下で書籍に載っている next 関数を見てみましょう：

#include<stdio.h>

void getNext(char a[], int n, int next[]){
int i, j;
i = 0;
next[0] = -1;//首元跳转值为 -1
j = -1;


//递推得到 next 表中剩余值
while(i &lt; n){
	if(j == -1 || a[i] == a[j]){
		++i;
		++j;
		next[i] = j;
	}
	else{
		j = next[j];
	}
}



}


main(){
char a[] = "abaabcac";//模式串 S2
int next[8] = {0};//跳转表，初始化为全 0
int i;


//构造 next 表
getNext(a, 8, next);
//输出 next 表
for(i = 0; i &lt; 8; i++){
	printf("%d ", next[i]);
}
printf("\n");



}

両者の計算結果は同じですが、書籍に載っているアルゴリズムは二重ループを消除しました。しかしこうすることでコードがより複雑になっただけで、実質的な最適化は何もありません

何？二重ループを消除しても効率が向上しない？ありえないでしょう？カウンターで検証してみましょう：

void getNext(char a[], int n, int next[]){
	int i, j;
	int counter = 0;///

next[0] = -1;//首元跳转值为 -1
next[1] = 0;//第二个元素跳转值为 0

for(i = 2; i &lt; n; i++){
	j = i - 1;
	
	//递推得到 next 表中剩余值
	while(j != -1){
		if(a[i - 1] == a[next[j]]){
			next[i] = next[j] + 1;
			counter++;///
			break;
		}
		else{
			j = next[j];
			counter++;///
		}
	}
}

printf("\n%d\n", counter);///



}


void getNext(char a[], int n, int next[]){
int i, j;
int counter = 0;///
i = 0;
next[0] = -1;//首元跳转值为 -1
j = -1;


//递推得到 next 表中剩余值
while(i &lt; n){
	if(j == -1 || a[i] == a[j]){
		++i;
		++j;
		next[i] = j;
		counter++;///
	}
	else{
		j = next[j];
		counter++;///
	}
}

printf("\n%d\n", counter);



}

P.S.具体的な操作部分（最も内部の if ブロックと else ブロック）に counter++;を挿入しました。こうして得られた結果だけが比較可能です（アルゴリズムが何回の具体的な操作を行ったか）

実行結果は以下の通り：

左図は自分で実装した next 関数のカウント結果で、この 4 ステップ少ないのは外側ループ回数の違いです（書籍のアルゴリズムは n 回、私たちのアルゴリズムは n-2 回）。私たちのアルゴリズムの外側ループ回数も n なら、14 回の具体的な操作が必要です（私たちは単なる簡単な最適化を行っただけです）

2 つの next 関数は形式が異なるだけで、内部操作順序は完全に同じです。next 関数を理解できれば、KMP アルゴリズムには難しい点はありません（S1 のポインタがバックトラックしない理由に关注しない場合、確かにこれだけが難しい点です。。）

四.KMP アルゴリズムの正しさの証明

（本記事ではここで展開しません。後で理解できればここで欠落した内容を補充するかもしれません。S1 のポインタがバックトラックしない理由、なぜ以前の部分が再びマッチングできないのかを詳しく説明します。。。）

しかし純粋に「実装」に关注する場合、next 関数を理解すれば完全に簡単に KMP アルゴリズムを実装できます（なぜこのようにできるのか、なぜこのようにするのが正しいのかの証明。。これは数学者の仕事です）

五.まとめ

KMP アルゴリズムの核心は next テーブルの構築プロセスで、next テーブルを構築する鍵となる思想は「漸化式」です。これを理解すれば、完全に数分で KMP アルゴリズムを書けます。。

少し余談：

KMP アルゴリズムにも変種があります。本記事で議論するのは最も原始的な KMP アルゴリズムで、一般的な変種には：

  • next テーブルの先頭要素が 0（-1 ではない）。最終的に得られる結果は私たちの next テーブルの各要素に +1 したもので、単なる約束の違いです（0 から始まるか 1 から始まるか）。実質的な違いはありません
  • next テーブル中に複数の -1 がある（私たちの結果には -1 が 1 つだけあり、つまり next テーブルの先頭要素）。これは実質的な最適化で、効率を効果的に向上できます。実は next テーブルを構築する際に私たちより 1 ステップ多く行い、構築プロセスが少し複雑になりますが、マッチングアルゴリズムの比較回数が減少します

コメント

コメントはまだありません

コメントを書く