乐趣区

关于算法:RabinKarp-算法字符串快速查找

Rabin-Karp 算法(字符串疾速查找)

Go 语言的 strings 包(strings.go)中用到了 Rabin-Karp 算法。Rabin-Karp 算法是基于这样的思路:即把字符串看作是字符集长度进制的数,由数值的比拟后果得出字符串的比拟后果。

奢侈的字符串匹配算法为什么慢?因为它太健忘了,前一次匹配的信息其实有局部能够利用到后一次匹配中去,而奢侈的字符串匹配算法只是简略的把这个信息扔掉,从头再来,因而,节约了工夫。好好的利用这些信息,天然能够进步运行速度。

因为实现两个字符串的比拟须要对其中蕴含的字符进行一一比拟,所需的工夫较长,而数值比拟则一次就能够实现,那么咱们首先把“搜索词”中各个字符的“码点值”通过计算,得出一个数值(这个数值必须能够示意出字符的前后程序,而且能够随时去掉某个字符的值,能够随时增加一个新字符的值),而后对“源串”中要比拟的局部进行计算,也得出一个数值,对这两个数值进行比拟,就能判断字符串是否匹配。对两个数值进行比拟,速度比简略的字符串比拟快很多。

比方咱们要在源串 “9876543210520” 中查找 “520”,因为这些字符串中只有数字,所以咱们能够应用字符集 {‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’} 来示意字符串中的所有元素,并且将各个字符映射到数字 0~9,而后用 M 示意字符集中字符的总个数,这里是 10,那么咱们就能够将搜索词 “520” 转化为上面的数值:

(“5″ 的映射值 M + “2” 的映射值) M + “0” 的映射值 = (5 10 + 2) 10 + 0 = 520

当然,如果“搜索词”很长,那么计算出来的这个数值就会很大,这时咱们能够选一个较大的素数对其取模,用取模后的值作为“搜索词”的值。

剖析一下这个数值:520,它能够代表字符串 “520”,其中:

代表字符 “5” 的局部是““5” 的映射值 (M 的 n – 1 次方) = 5 (10 的 2 次方) = 500”
代表字符 “2” 的局部是““2” 的映射值 (M 的 n – 2 次方) = 2 (10 的 1 次方) = 20”
代表字符 “0” 的局部是““0” 的映射值 (M 的 n – 3 次方) = 0 (10 的 0 次方) = 0”
(n 代表字符串的长度)

咱们能够随时减去其中一个字符的值,也能够随时增加一个字符的值。

“搜索词”计算好了,那么接下来计算“源串”,取“源串”的前 n 个字符(n 为“搜索词”的长度)”987″,依照同样的办法计算其数值:

(“9″ 的映射值 M + “8” 的映射值) M + “7” 的映射值 = (9 10 + 8) 10 + 7 = 987

而后将该值与搜索词的值进行比拟即可。

比拟发现 520 与 987 不相等,则阐明 “520” 与 “987” 不匹配,则持续向下寻找,这时候该如何做呢?下一步应该比拟 “520” 跟 “876” 了,那么咱们如何利用前一步的信息呢?首先咱们把 987 减去代表字符 “9” 的局部:

987 – (“9″ 的映射值 (M 的 n – 1 次方)) = 987 – (9 (10 的 2 次方)) = 987 – 900 = 87

而后再乘以 M(这里是 10),再加上 “6” 的映射值,不就成了 876 了么:

87 M + “6” 的映射值 = 87 10 + 6 = 876

当然了,因为采纳了取模操作,当两个数值相等时,未必是真正的相等,咱们须要进行一次粗疏的查看(再进行一次奢侈的字符串比拟)。若不匹配,则能够排除掉。持续下一步。

如果咱们要在 ASCII 字符集范畴内查找“搜索词”,因为 ASCII 字符集中有 128 个字符,那么 M 就等于 128,比方咱们要在字符串 “abcdefg” 中查找 “cde”,那么咱们就能够将搜索词 “cde” 转化为“(“c” 的码点 M + “d” 的码点) M + “e” 的码点 = (99 128 + 100) 128 + 101 = 1634917”这样一个数值。

剖析一下这个数值:1634917,它能够代表字符串 “cde”,其中:

代表字符 “c” 的局部是““c” 的码点 (M 的 n – 1 次方) = 99 (128 的 2 次方) = 1622016”
代表字符 “d” 的局部是““d” 的码点 (M 的 n – 2 次方) = 100 (128 的 1 次方) = 12800”
代表字符 “e” 的局部是““e” 的码点 (M 的 n – 3 次方) = 101 (128 的 0 次方) = 101”
(n 代表字符串的长度)

咱们能够随时减去其中一个字符的值,也能够随时增加一个字符的值。

“搜索词”计算好了,那么接下来计算“源串”,取“源串”的前 n 个字符(n 为“搜索词”的长度)”abc”,依照同样的办法计算其数值:

(“a” 的码点 M + “b” 的码点) M + “c” 的码点 = (97 128 + 98) 128 + 99 = 1601891

而后将该值与“搜索词”的值进行比拟即可。

比拟发现 1634917 与 1601891 不相等,则阐明 “cde” 与 “abc” 不匹配,则持续向下寻找,下一步应该比拟 “cde” 跟 “bcd” 了,那么咱们如何利用前一步的信息呢?首先去掉 “abc” 的数值中代表 a 的局部:

(1601891 – “a” 的码点 (M 的 n – 1 次方)) = (1601891 – 97 (128 的 2 次方)) = 12643

而后再将后果乘以 M(这里是 128),再加上 “d” 的码点值不就成了 “bcd” 的值了吗:

12643 * 128 + “d” 的码点 = 1618304 + 100 = 1618404

这样就能够持续比拟 “cde” 和 “bcd” 是否匹配,以此类推。

如果咱们要在 Unicode 字符集范畴内查找“搜索词”,因为 Unicode 字符集中有 1114112 个字符,那么 M 就等于 1114112,而 Go 语言中应用 16777619 作为 M 的值,16777619 比 1114112 大(更大的 M 值能够包容更多的字符,这是能够的),而且 16777619 是一个素数。这样就能够应用下面的办法计算 Unicode 字符串的数值了。进而能够对 Unicode 字符串进行比拟了。

其实 M 能够了解为进位值,比方 10 进制就是 10,128 进制就是 128,16777619 进制就是 16777619。

上面是 Go 语言中字符串匹配函数的源码,应用 Rabin-Karp 算法进行字符串比拟:

// primeRK 是用于 Rabin-Karp 算法中的素数,也就是下面说的 M
const primeRK = 16777619

// 返回 Rabin-Karp 算法中“搜索词”sep 的“哈希值”及相应的“乘数因子(权值)”
func hashstr(sep string) (uint32, uint32) {

// 计算 sep 的 hash 值
hash := uint32(0)
for i := 0; i < len(sep); i++ {hash = hash*primeRK + uint32(sep[i])
}
// 计算 sep 最高位 + 1 位的权值 pow(乘数因子)// 也就是下面说的 M 的 n 次方
// 这里通过遍历 len(sep) 的二进制位来计算,缩小计算次数
var pow, sq uint32 = 1, primeRK
for i := len(sep); i > 0; i >>= 1 {
    if i&1 != 0 { // 如果二进制最低位不是 0
        pow *= sq
    }
    sq *= sq
}
return hash, pow

}

// Count 计算字符串 sep 在 s 中的非重叠个数
// 如果 sep 为空字符串,则返回 s 中的字符(非字节) 个数 + 1
// 应用 Rabin-Karp 算法实现
func Count(s, sep string) int {

n := 0
// 非凡状况判断
switch {case len(sep) == 0: // 空字符,返回字符个数 + 1
    return utf8.RuneCountInString(s) + 1
case len(sep) == 1: // 单个字符,能够用疾速办法
    c := sep[0]
    for i := 0; i < len(s); i++ {if s[i] == c {n++}
    }
    return n
case len(sep) > len(s):
    return 0
case len(sep) == len(s):
    if sep == s {return 1}
    return 0
}
// 计算 sep 的 hash 值和乘数因子
hashsep, pow := hashstr(sep)
// 计算 s 中要进行比拟的字符串的 hash 值
h := uint32(0)
for i := 0; i < len(sep); i++ {h = h*primeRK + uint32(s[i])
}
lastmatch := 0 // 下一次查找的起始地位,用于确保找到的字符串不重叠
// 找到一个匹配项(进行一次奢侈比拟)if h == hashsep && s[:len(sep)] == sep {
    n++
    lastmatch = len(sep)
}
// 滚动 s 的 hash 值并与 sep 的 hash 值进行比拟
for i := len(sep); i < len(s); {
    // 加上下一个字符的 hash 值
    h *= primeRK
    h += uint32(s[i])
    // 去掉第一个字符的 hash 值
    h -= pow * uint32(s[i-len(sep)])
    i++
    // 开始比拟
    // lastmatch <= i-len(sep) 确保不重叠
    if h == hashsep && lastmatch <= i-len(sep) && s[i-len(sep):i] == sep {
        n++
        lastmatch = i
    }
}
return n

}

退出移动版