一歩一歩アルゴリズムを書く(文字列検索下編)

【声明:著作権所有、転載歓迎、商業用途に使用しないでください.連絡ポスト:[email protected]】
前にKMPアルゴリズムについて述べたが,まだ詳細ではない.今日はこの問題を少し詳しく話してもいいです.文字列Aで文字列Bを探すと仮定し、文字列Bの長さはnであり、文字列Aの長さはnよりはるかに大きいと仮定し、ここではまず無視する.
文字列Aで検索を開始し、p番目の文字で検索エラーが検出されたと仮定します.つまり、次の場合です.

/*      
*    A: A1 A2 A3 A4 ... Ap ............
*    B: B1 B2 B3 B4 ... Bp ...Bn 
*                       (p)        
*/    

では、この時、Aにはどんな選択肢があるのでしょうか.それは左に1ビットシフトして、A 2~A(p-1)でB 1~B(p-2)を比較して、それからA(p)~A(n+1)でB(p-1)~B(n)ビットを比較することができる.あるいは左に2ビットシフトし、B 1~B(p-3)をA 3~A(p-1)で比較した後、B(p)~A(n+2)で比較する.順次類推し、左シフト(p−2)ビットまでA(p−1)でB(1)を比較した後、A(p)~A(p+n−2)でB(2)~B(n)ビットを比較する.
注意深い友达が何か規則を発見しましたか?AとBは前(p-1)のデータが等しいため、上の計算ではB 1~B(p-2)をA 2~A(p-1)で比較し、実際にはB 2~B(p-1)でB 1~B(p-2)を比較する.A 3~A(p-1)でB 1~B(p-3)を比較すると、実際にはB 3~B(p-1)でB 1~B(p-3)を比較する.最後にB(p)とB(1)の両者を比較するまで.これらのデータはすべてB自身のデータである以上、もちろん私たちは事前にこれらの結果を計算することができます.
では、こんなに多くの選択で、私たちは何桁左に移動すればいいのでしょうか.
実は判断が簡単です.1ビットを左にシフトすると,A 2~A(p-1)の結果とB 1~B(p-2)が一致することが分かったと仮定すると,両者は直接(p-1)ビットから比較できる.成功しなければ2桁左にシフトしてA 2~A(p-1)とB 1~B(p-2)の比較結果を判断するしかないのですが…、このように類推して比較する.残念ながらすべてのデータが比較的に成功しないことに気づいたら、最初からやり直すしかなく、1位のデータから順番に比較するしかありません.
はっきり言ったかどうか分からないが、まだ分からない友达は次のコードを見てもいいです.

int calculate_for_special_index(char str[], int index)
{
	int loop;
	int value;
	
	value = 0;
	for(loop = 1; loop < index; loop ++){
		if(!strncmp(&str[loop], str, (index - loop))){
			value = index - loop;
			break;
		}
	}
	
	return (value == 0) ? 1 : (index - value);
}

void calculate_for_max_positon(char str[], int len, int data[])
{
	int index;
	
	for(index = 0; index < len; index++)
		data[index] = calculate_for_special_index(str, index);
}

もちろん,上記はインデックスnの比較に失敗した場合に,このとき文字が左に何ビット移動すべきかを判断するためである.

char* strstr_kmp(const char* str, char* data)
{
	int index;
	int len;
	int value;
	int* pData;

	if(NULL == str || NULL == str)
		return NULL;

	len = strlen(data);
	pData = (int*)malloc(len * sizeof(int));
	memset(pData, 0, len * sizeof(int));
	calculate_for_max_positon((char*)str, len, pData);

	index = 0;
	while(*str && ((int)strlen(str) >= len)){
		for(; index < len; index ++){
			if(str[index] != data[index])
				break;
		}
		
		if(index == len){
			free(pData);
			return (char*) str;
		}
	
		value = pData[index];
		str += value;

		if(value == 1)
			index = 0;
		else
			index = index -value;
	}
	
	free(pData);
	return NULL;
}

友達が見たかもしれませんが、上のstrlenはまた帰ってきましたか?説明コード自体には最適化の余地があります.みんなは自分でやってみてもいいです.

int check_valid_for_kmp(char str[], int start, int len)
{
	int index;

	for(index = start; index < len; index++)
		if('\0' == str[index])
			return 0;
	return 1;
}

char* strstr_kmp(const char* str, char* data)
{
	int index;
	int len;
	int value;
	int* pData;

	if(NULL == str || NULL == str)
		return NULL;

	len = strlen(data);
	pData = (int*)malloc(len * sizeof(int));
	memset(pData, 0, len * sizeof(int));
	calculate_for_max_positon((char*)str, len, pData);

	index = 0;
	while(*str && check_valid_for_kmp((char*)str, index, len)){
		for(; index < len; index ++){
			if(str[index] != data[index])
				break;
		}
		
		if(index == len){
			free(pData);
			return (char*) str;
		}
	
		value = pData[index];
		str += value;

		if(value == 1)
			index = 0;
		else
			index = index -value;
	}
	
	free(pData);
	return NULL;
}

(三)、マルチコア検索
マルチコア検索は実は新鮮ではありません.検索を複数に分けて、異なる検索過程は異なるコアの上で完成します.例えば、現在使用しているcpuは一般的にデュアルコアcpuであり、検索する文字を2つに分けることができ、2つの検索をそれぞれ2つのコアの上で同時に行うことができます.具体的にどうすればいいのか、実は複雑ではありません.まず、データ構造を定義します.

typedef struct _STRING_PART
{
	char * str;
	int len;
}STRING_PART;

次に、文字列を2等分し、開始アドレスと長さをそれぞれ演算します.

void set_value_for_string_part(char str[], int len, STRING_PART part[])
{
	char* middle = str + (len >> 1);

	while(' ' != *middle)
		middle --;

	part[0].str = str;
	part[0].len = middle - (str -1);

	part[1].str = middle + 1;
	part[1].len = len - (middle - (str - 1));
}

点を取ると、並列演算が開始されます.

char* strstr_omp(char str[], char data[])
{
	int index;
	STRING_PART part[2] = {0};
	char* result[2] = {0};
	int len = strlen(str);

	set_value_for_string_part(str, len, part);

#pragma omp parellel for 
    for(index = 0; index < 2; index ++)
		result[index] = strstr(part[index].str, part[index].len, data);

	if(NULL == result[0] && NULL == result[1])
		return NULL;

	return (NULL != result[0]) ? result[0] : result[1];
}

注意事項:
(1)ここでompマクロはVS 2005以降で実行するとともにヘッダファイルinclude,openmpのスイッチを入れる;
(2)ここで呼び出されるstrstr関数の2番目のパラメータはターゲット文字列の長さであり,我々が先に紹介した通常の検索関数とは少し異なり,前の関数は直接使用できないが,少し変更すればよい.