js-rabin-karp-matcher
v1.0.2
Published
简单的 Rabin-Karp 算法(即 "拉宾-卡普" 算法)的实现,用于学习之目的,代码当中有每一部分的详细说明。
Downloads
4
Readme
JS Rabin-Karp Matcher
简单的 Rabin-Karp 算法(即 "拉宾-卡普" 算法)的实现,用于学习之目的,代码当中有每一部分的详细说明。
算法简介
Rabin-Karp 是一种字符串搜索算法。字符串搜索是指在 目标字符串
里搜索指定 关键字
所出现的位置,比如在各种文本编辑器里使用 "查找" 功能就是字符串搜索。
简单思想
- 在
目标字符串
的开始位置里取一个跟 关键字 一样长的子字符串; - 计算子该字符串的 Hash 值,如果跟
关键字
的 Hash 值一样,则说明这个子字符串 有可能 跟关键字相同,再使用暴力搜索法比较这个字串和关键字,如果一样则表示已经找到匹配的字符并退出搜索过程,如果不一样则从目标字符串
里的下一个字符开始重复第一步。
Rabin-Karp 算法的 Hash 计算方法跟常见的 SHA、MD5 等 Hash 算法不同,它是一种简单得多且支持 滚动更新
的算法。所谓 滚动更新
是指:当从末尾抛弃一个字符以及从头部压入一个新字符时,并不需要重新计算这个 "新字符串" 的 Hash 值,而是类似数学的加减法,把末尾的字符(经过某种运算而得)的值减去,然后加上新字符(经过某种运算而得)的值,则刚好为 "新字符串" 的 Hash 值。
不妨把 Rabin-Karp 算法的 Hash 计算方法假想为目标字符的 Unicode 码点相加。
比如对于字符串从位置 0 到位置 3 的 Hash 值为:
hash(code[i:i+3]) = code[i] + code[i+1] + code[i+2] + code[i+3]
那么当把位置往右移动一位时,即 位置 1 到位置 4 的 Hash 值为:
hash(code[i+1:i+4]) = hash(code[i:i+3]) - code[i] + code[i+4]
如此一来即实现了 滚动更新
。
但实际上 Rabin-Karp 算法的 Hash 计算方法并不是简单地把字符的 Unicode 码点相加,因为对于小字符集(比如英文字母)这样出现 Hash 碰撞的机率较高;当然也不会太复杂,否则计算 Hash 的成本远远高于字符串比较的成本。所以它的 Hash 计算方法是:
hash(code[0:4]) = (code[0] * 256^4) + (code[1] * 256^3) + (code[2] * 256^2) + (code[3] * 256^1) + (code[4] * 256^0)
它的算法把连续字符中的每一位当成是一个 256
进制的数(因为英文每个字母使用一个 byte 存储,一个 byte 是值从 0 到 255 共 256 个值的自然数),然后 Hash 值就是把这个 256
进制的数转成的十进制数。所以当字符串 code[1:5]
的 Hash 值就是:
hash(code[1:5]) = (hash(code[0:4]) - (code[0] * 256^4)) * 256 + (code[5] * 256^0)
--------------- ---------------- ---------------- --- ----------------
新的 Hash 值 上一个 Hash 值 末尾字符 * height 左移一位 新字符
上面的 height
为最高位的权重,值为 Math.pow(256, keywordLength - 1)
在实际程序里,因为 关键字
的长度可能很长,导致高位的权重值超出整型甚至长整型数字能表示的范围,所以通常还需要对每一个乘法计算的结果使用一个素数进行 取余
。
比如计算从 0 到 keywordLength 的 Hash 值,代码如下:
const base = 256; // 基数
const prime = 101; // 素数
let hash = 0; // Hash 值的初始值
for (let i = 0; i < keywordLength; i++) {
hash = (hash * base + code[i]) % prime;
}
console.log(hash);
单元测试
执行命令:
$ npm test
应该能看到 testRabinKarp() passed.
字样。
单步调试/跟踪
有时跟踪程序的运行过程,能帮助对程序的理解,启动单步调试的方法是:
在 vscode 里打开该项目,然后在单元测试文件里设置断点,再执行 Run and Debug
即可。
字符串搜索算法系列项目
JS Rabin-Karp Matcher https://github.com/hemashushu/js-rabin-karp-matcher
JS Boyer-Moore-Horspool Matcher https://github.com/hemashushu/js-boyer-moore-horspool-matcher
JS KMP Matcher https://github.com/hemashushu/js-kmp-matcher
JS Aho-Corasick Matcher https://github.com/hemashushu/js-aho-corasick-matcher
JS Regexp Interpreter https://github.com/hemashushu/js-regexp-interpreter