字符串查找算法（二）

15 January 2015

RK算法和FNV算法。

接前面的《字符串查找算法》继续写。上一篇文章说过，神奇的数字16777619，当时不知道这个是干嘛用的，现在差不多知道了。

字符串哈希，会经常用到FNV哈希算法。FNV哈希算法如下：将字符串看作是字符串长度的整数，这个数的进制是一个质数。计算出来结果之后，按照哈希的范围求余数，结果就是哈希结果。

#define TRUE_HASH_SIZE ((u_int32_t)50000) /* range top plus 1 */
#define FNV_32_PRIME ((u_int32_t)16777619)
#define FNV1_32_INIT ((u_int32_t)2166136261)
#define MAX_32BIT ((u_int32_t)0xffffffff) /* largest 32 bit unsigned value */
#define RETRY_LEVEL ((MAX_32BIT / TRUE_HASH_SIZE) * TRUE_HASH_SIZE)
u_int32_t hash;
void *data;
size_t data_len;

hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
while (hash >= RETRY_LEVEL) {
		hash = (hash * FNV_32_PRIME) + FNV1_32_INIT;
}
hash %= TRUE_HASH_SIZE;

下面给出了三个质数，分别是求范围是32位、64位、128位和256位哈希值时使用。当然，这三个质数是怎么得到的，我肯定不知道。

32 bit FNV_prime = 224 + 28 + 0x93 = 16777619 64 bit FNV_prime = 240 + 28 + 0xb3 = 1099511628211 128 bit FNV_prime = 288 + 28 + 0x3b = 309485009821345068724781371 256 bit FNV_prime = 2168 + 28 + 0x63 = 374144419156711147060143317175368453031918731002211

继续看Golang的代码，字符串字串匹配用的是无符号32位整数，那就是32位长度，自然，质数就需要选16777619了。结果会按照32位最大的整数求余，在这里，因为是将结果存在uint32里面的，所以超出范围的会被丢弃，也可以认为是求余操作。

const primeRK = 16777619

// hashstr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func hashstr(sep string) (uint32, uint32) {
	hash := uint32(0)
	for i := 0; i < len(sep); i++ {
		hash = hash*primeRK + uint32(sep[i])
	}
	var pow, sq uint32 = 1, primeRK
	for i := len(sep); i > 0; i >>= 1 {
		if i&1 != 0 {
			pow *= sq
		}
		// 只有32位，超出范围的会被丢掉
		sq *= sq
	}
	return hash, pow
}

剩下的就是上一篇文章提到的，RK算法，根据FNV哈希得到的值进行推算，能够在o(1)时间范围内计算得到下一条字串的哈希值。然而，FNV哈希算法能够保证大部分情况下哈希的结果都在指定范围内均匀分布，但不是全部。所以在最后判断字串是否相等的时候，还会再加上s[:n] == sep来保证完全一致，所以，RK算法的复杂度准确的说是o(m+n)。

if h == hashsep && s[:n] == sep {
	return 0
}

为啥判断相等的时候不直接用s[:n] == sep来判断每个字串是否相等？因为这样的话，复杂度又变回o(m*n)了。

参考文献

原文链接：字符串查找算法（二），转载请注明来源！

–EOF–

Golang 50