首页 / 算法 / Rabin-Karp 指纹字符串查找算法
Rabin-Karp 指纹字符串查找算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Rabin-Karp 指纹字符串查找算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6024字，纯文字阅读大概需要9分钟。
内容图文
文章目录
一、简介
M.O.Rabin 和 R.A.Karp 提出了一种完全不同的基于散列的字符串查找算法，我们只需要根据特定的 散列函数 计算出模式字符串的 hash 值，然后用相同的散列函数计算文本中所有可能的 M 个字符的子字符串散列值并寻找匹配。
如果找到了一个散列值和模式字符串的相同的子字符串，就继续验证两者是否匹配。但是实现这种算法其实要比暴力破解还要慢，不过 Rabin 和 Karp 进行了改进，发明了一种能够在 常数时间 算出 M 个字符的子字符串散列值的方法（需要预处理）。
二、散列函数
对于散列函数，我们都不陌生，其最重要的思想主要是以下两方面：
- 散列函数的设计
- 解决冲突的方法
2.1、RK 算法基本思想
长度为 M 的字符串对应一个 R 进制的 M 位数。为了用一张大小为 Q 的散列表来保存这种类型的键，需要一个能够将 R 进制的 M 位数转化为一个 0 到 Q - 1 之间的 int 值散列函数。
除留余数法（最常用的构建散列函数的方法） 是一个很好的选择：将该数除以 Q 并取余。在实际应用中会使用一个随机的 素数 Q，在不溢出的情况下选择一个尽可能大的值。（我们并不需要一张完整的散列表，只需要一个值就好了）
2.2、除留余数法
对于散列表长度为 M 的散列函数：
公式：f（key）= key mod Q （Q <= M）
mod 就是取模的意思，实际上，该方法不仅可以对关键字直接取模，也可以在折叠、平方取中后再取模。同时很明显可以看出来这个公式的关键在于选择一个合适的 Q 来减少冲突。
如何合理的选择 Q 值：
- 使用除留余数法的一个经验就是：若散列表表长为 M，通常 Q 为小于或等于表长（最好接近 M）的最小质数或不包含小于20质因子的合数
使用这种方法获取 hash 值的函数如下：
public static long getHash(String sub) { // 适用于数字组成的字符串
return Integer.parse(sub) % Q;
}
2.3、Horner 法则
如果使用常规的除留余数法作为散列函数是有局限性的，它适用于十进制字符。所以我们采用 霍纳规则 版本的除留余数法。
霍纳法则是求解多项式的一个经典方法。
通常我们在进行多项式求和问题的求解时，最朴素的思想是把每一项的值都求出来，然后相加，这种思想非常好，但是当数据量变大的时候，它的时间和空间效率都不高，这时候我们可以采取更高效的算法——霍纳法则。
在中国，霍纳法则也被称为 秦九韶算法。有兴趣可以看看。
下面直接上 java 代码：
其中滚动数组求解的思想很好。
// horner 法则
public static void main(String[] args) {
int[] c = {2, -1, 3, 1, -5};
int x = 3;
System.out.println(horner(c, x));
System.out.println(horner_recursion(c, x, c.length - 1));
}
// 滚动数组求解
public static int horner(int[] c, int x) {
int len = c.length;
int res = c[0];
for (int i = 1; i < len; i++) {
res = x * res + c[i];
}
return res;
}
// 递归求解 可以试着推一推递推式
public static int horner_recursion(int[] c, int x, int n) {
if (n == 0)
return c[n];
return horner_recursion(c, x, n - 1) * x + c[n];
}
2.4、horner 方法
了解了霍纳法则后，我们对除留余数法进行改进也就得到了 Rabin-Karp算法 的散列函数：
private static long getHash(String pat, int len) {
long hash = 0;
for (int i = 0; i < len; i++) {
hash = (hash * R + pat.charAt(i)) % Q;
}
return hash;
}
总结：
- 除留余数法：h（key） = key % Q；
- 将 key 换成多项式和，采用 horner 法则计算
- 将未知数 x 替换为 进制 R（其实就是字母表的大小）
- 将系数列表替换为 模式字符串，多项式的项数 n 就是模式字符串的长度
- 选取特定的 Q 减少 hash 冲突
我们也可以使用此方法来计算文本中的子字符串的 hash 值，但是这样一来字符串查找算法的成本就是将对文本中每一个字符进行乘法、加法和取余计算的成本之和。在最坏情况下需要 NM 次操作，相比于暴力破解法没有任何改进。
三、Rabin-Karp 算法关键思想
Rabin-Karp 算法的基础是对于所有位置 i ，高效计算文本中 i + 1 位置的子字符串散列值。
如果对文本中每个子字符串都采用 horner 方法进行计算，它的效率达不到我们的期望，我们可以利用取余操作的一个基本性质：
- 如果每次算术操作后都将结果除以 Q 并取余，这等价于在完成了所有算术操作后在将最后的结果除以 Q 取余。
所以我们只需要保存文本串的第一个子串求 hash 值时除以 Q 后的余数，进行一些特殊处理就可以在常数时间内高效的不断向右一格一格的移动。（滚动 hash ）
四、算法实现
private static final long Q = longRandomPrime(); // 生成一个很大的素数
private static final int R = 256; // 字母表的大小
private static long RM; // 用于保存临时余数 R ^ (M - 1) % Q
public static int rabin_karp(String txt, String pat) {
int pLen = pat.length();
int tLen = txt.length();
RM = 1;
for (int i = 1; i <= pLen - 1; i++) {
RM = (R * RM) % Q; // 减去第一个数字的时候计算
}
// 获取模式字符串的 hash 值
long patHash = getHash(pat, pLen);
// 获取文本串第一个子字符串的 hash 值
long txtHash = getHash(txt, pLen);
if (patHash == txtHash && check(txt, pat, 0))
return 0;
for (int i = pLen; i < tLen; i++) {
// 减去第一个数字，加上最后一个数字，再次检查匹配
txtHash = (txtHash + Q - RM * txt.charAt(i - pLen) % Q) % Q;
txtHash = (txtHash * R + txt.charAt(i)) % Q;
if (patHash == txtHash)
if (check(txt, pat, i - pLen + 1))
return i - pLen + 1; // 找到匹配
}
return -1;
}
// 处理可能存在的 hash 冲突
private static boolean check(String txt, String pat, int index) {
for (int i = index, j = 0; j < pat.length(); i++, j++) {
if (txt.charAt(i) != pat.charAt(j))
return false;
}
return true;
}
// 散列函数
private static long getHash(String pat, int len) {
long hash = 0;
for (int i = 0; i < len; i++) {
hash = (hash * R + pat.charAt(i)) % Q;
}
return hash;
}
// 不溢出的情况下生成一个尽可能大的素数
private static long longRandomPrime() {
BigInteger prime = BigInteger.probablePrime(31, new Random());
return prime.longValue();
}
五、小技巧：蒙特卡洛法 和 拉斯维加斯算法
Rabin-Karp 算法是基于散列思想的，所以它一定会存在 散列值冲突 的问题，通常在文本中找到一个子串和模式串的 hash 值相同的时候，我们可能会逐个比较它们的字符以确保得到一个匹配而非相同的散列值。
但是我们不会这么做，因为这需要回退文本指针，作为替代，这里将散列表的规模 “Q” 设置成了一个任意大的值，我们不会真的构造一张散列表，而是仅仅希望用模式字符串的散列值验证是否会产生冲突。
在上面的算法中，Q 取得是一个大于 10^20 的 long 值，使得一个随机键的散列值与模式字符串冲突的概率小于 10^-20，这是一个极小的值，如果觉得它还不够小，可以进行二次散列，这样失败的几率将会小于 10^-40。—— 这就是 蒙特卡洛 算法的一种著名早期应用。它既能保证运行时间，失败的概率也非常小。
但是我在上面的算法实现中使用了检查匹配的方法（check 方法），这样做在极端情况下性能有很小的概率相当于暴力算法，但是它能够保证正确性，不会失败。—— 这种算法就是 拉斯维加斯算法。
内容总结
以上是互联网集市为您收集整理的Rabin-Karp 指纹字符串查找算法全部内容，希望文章能够帮你解决Rabin-Karp 指纹字符串查找算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。