博客文章

从Horspool算法看Boyer-Moore算法

作者: andy.      时间: 2016-04-19 22:12:40

看了看网上的文章,大都是给出结论,都没有对算法为什么要这么做说个所以然,所以故写了这篇文章。因为是从Horspool算法看Boyer-Moore算法,所以不会有很多图啊什么的,默认是在对两个算法有一定了解的情况下写的。


先看看Horspool算法,四种情况就不做讨论了。这四种情况其实可以用一句话来总结:当前不匹配时,接下来移位的距离满足移位最少可能使得全部的匹配

为什么是移位最少?因为多了的话,有可能就移过了原本可以匹配的位置。每次移位距离为1的话不就是移位最少且可能使得全部的匹配么?但是很多情况下我们可以判断这种情况是绝对不会匹配成功的。大家可以用这段话去套那四种情况。


因为重点是在Boyer-Moore算法上,所以对Horspool算法到此为止,在文章的最后再给出Horspool的测试代码。

先来看看Boyer-Moore维护的两张表:坏符号移动表和好后缀移动表。所谓坏符号,因为这个符号使得字符串不能全匹配。而好后缀,这个后缀和要查找的单词的后面几个字符相匹配。

坏符号移动表,直接套用的Horspool的表就成。

再看一张好后缀移动表:

K

模式

d2

1

BAOAB

2

2

AOBAB

5

3

AOBAB

5

4

AOBAB

5

5

AOBAB

5

看k = 1的情况,当从右往左(进行匹配)第一个A出现不匹配的时候,按照我们上面总结的理论。就是将有上划线的B移动到最后一个字符的位置,d2就为了2。

同理,k = 2的时候,如果移OB的话,肯定不会和AB相同(因为后缀AB已经匹配,被查找字符串中该位置肯定为AB)。只好移动第一个B。

同理,k = 3的时候,同二。

同理,k = 4的时候,同二。

同理,k = 5的时候,同二。

上面的例子太特殊了。比如要查找的字符串为XAOBAB,k = 2的时候,d2 = 6,直接跳完,因为移动1~5肯定不能完全匹配。这样子就获得了好后缀移动表。

再举一个例子,DBCBAB,k = 3的情况,可以确定从右向左匹配中出现了BAB三个字符,而移动两个或者四个距离,D和A、C和A都不会出现匹配的情况,所以移动距离为6。

而对于ABCBAB来说,k = 3时,移动距离为4,这个可以通过上述总结容易得到。于是下面这张好后缀表就非常好理解了:

K

模式

d2

1

ABCAB

2

2

CBAB

4

3

BAB

4

4

CBAB

4

5

 CBAB

4

 

通过上面的叙述我可以得出如果移动的距离小于坏符号的移动距离或者小于好后缀的移动距离都不能使得字符串得到匹配。所以在实际匹配的时候要结合坏符号移动表和好后缀移动表。遵循的一个条件:在遇到不匹配的情况下,移动距离尽量的大。

在实际的移动比较当中取的是t1(坏符号) – k,因为如果这个坏符号存在于要查找的字符串中的,这个距离刚好使得坏符号与查找字符串中的字符匹配。如果不存在于话,这个距离刚好跳过坏符号。下面的图可以很好的说明这个情况:




A

E

R



B

A

R

B

E

R





B

A

R

B

E

R

当A出现不匹配的时候,坏符号的移动距离为:d1 = t1(A) – 2 = 4 – 2 = 2,坏符号不存在于查找字符串中就不做说明了。

 

至此,通过Horspool算法看 Boyer-Moore就叙述完毕了。因为它们的思路都基本相同,在发生不匹配的时候尽最大可能移动。所以理解了Horspool算法后,Boyer-Moore算法就非常简单了。

 

下面说说算法的实现。关键点在Boyer-Moore的好后缀,其实很容易观察得到。比如说k位的后缀,将k位向前移动(从1开始),直到全匹配,就是好后缀的移动距离。如果移动的时候出界了砍掉出界的不要就行了(默认已经匹配)。如果全部都出界了,那就完了,移动距离为整个字符串的长度。这儿还要介绍一种特殊情况01010k = 1的情况下,好后缀的偏移量(移动距离)为4,为什么呢?按照刚刚的说法,应该为2啊?因为3个字符前面为1,后面的坏字符也是1,移动过去肯定是不匹配的看下面的匹配表应该好理解一点儿:

偏移/移位距离k

0

1

0

1

0

1




0


2



0



3


0




4

0





红色标注的位置不是最佳移动距离,因为坏字符是1,而该位置的前一个字符也是1,移动过去肯定不会全匹配。不满足我们在第二段说的:“移位的距离满足移位最少可能使得全部的匹配”可能使得全匹配。所以继续向后寻找。找到了移动距离4.

.在构建好后缀的代码中,这个是有体现的。如果是第一个字符,那么不考虑上述的特殊情况,所以代码如下:

			if (tempWord != word)
				if (*(tempWord - 1) == *(tempWord - 1 - offset))
					continue;

好了,直接看好后缀的代码,这段代码用的蛮力法,想了半天最后觉得这样子应该是最简洁的:

void SetVal2(char * word, short * hash) {
	short wordLen = strlen(word);
	short k = NULL, offset = NULL, j = NULL;
	char * tempWord = NULL;
	//k 后缀至少为1
	for (k = 1; k < wordLen; k++) {
		hash[k - 1] = wordLen;
		//移位 至少移位一个 最多移 length - 1个距离
		for (offset = 1; offset < wordLen; offset++) {
			tempWord = word + wordLen - k;
			//如果偏移比较的时候 超出部分跳过 不比较
			if (wordLen - k - offset < 0)
				tempWord += offset + k - wordLen;
				
			//如果前一字符偏移量 和该字符相等了 就算移过去也是肯定不等的
			if (tempWord != word)
				if (*(tempWord - 1) == *(tempWord - 1 - offset))
					continue;
				
			for (; *tempWord; tempWord++) {
				if (*tempWord != *(tempWord - offset))
					break;
			}

			if (!*tempWord) {
				hash[k - 1] = offset;
				break;
			}
		}
	}
}

坏符号的代码:

void SetVal1(char * word, short * hash) {
	short i = NULL;
	short wordLen = strlen(word);
	short len = NULL;
	for (i = 0; i < 256; i++)
		hash[i] = wordLen;

	for (i = wordLen - 2; i >= 0; i--) {
		if (hash[word[i]] != wordLen)
			continue;
		hash[word[i]] = wordLen - i - 1;
	}
}

Boyer-moore代码:

int BoyerMoore(char *word, char *list, short * hash1, short * hash2)
{
	int k = NULL;
	char * temp = list;
	char * lastAddr = list + strlen(list) - strlen(word);
	short offset = strlen(word) - 1;
	while (temp <= lastAddr)
	{
		k = 0;
		while (*(temp + offset) == word[offset] && offset > 0) {
			offset--;
			k++;
		}

		if (offset == 0)
			return (temp - list);

		offset = strlen(word) - 1;
		if (k == 0)
			temp += hash1[*(temp + offset)] - k >= 0 ? hash1[*(temp + offset)] - k : 1;
		else
			temp += MAX(hash1[*(temp + offset)] - k >= 0 ? hash1[*(temp + offset)] - k : 1, hash2[k - 1]);
	}
	return -1;
}

Horspool代码:

char * Find(char * word, char * list, short * hash) {
	char * temp = list;
	char * lastAddr = list + strlen(list) - strlen(word);
	short offset = strlen(word) - 1;
	while (temp <= lastAddr)
	{
		while (*(temp + offset) == word[offset] && offset > 0)
			offset--;

		if (offset == 0)
			return (temp - list);

		offset = strlen(word) - 1;
		temp += hash[*(temp + offset)];
	}
	return -1;
}

主函数都差不多,给一个就是了:

int main(int argc, char * argv[]) {
	short * hash1 = (short *)malloc(sizeof(short) * 256);
	short * hash2 = (short *)malloc(sizeof(short) * 256);
	char * list = malloc(1024 * 1024);

	SetVal1(argv[1], hash1);
	SetVal2(argv[1], hash2);

	FILE* file = NULL;
	if ((file = fopen(argv[2], "r")) == NULL) {
		printf("failed.");
		return -1;
	}
	fread(list, sizeof(char), 1024 * 1024 - 1, file);
	fclose(file);

	printf("第一个位置:%d", BoyerMoore(argv[1], list, hash1, hash2));

	free(hash1);
	free(hash2);
	free(list);
}