npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

js-rabin-karp-matcher

v1.0.2

Published

简单的 Rabin-Karp 算法(即 "拉宾-卡普" 算法)的实现,用于学习之目的,代码当中有每一部分的详细说明。

Downloads

4

Readme

JS Rabin-Karp Matcher

简单的 Rabin-Karp 算法(即 "拉宾-卡普" 算法)的实现,用于学习之目的,代码当中有每一部分的详细说明。

算法简介

Rabin-Karp 是一种字符串搜索算法。字符串搜索是指在 目标字符串 里搜索指定 关键字 所出现的位置,比如在各种文本编辑器里使用 "查找" 功能就是字符串搜索。

简单思想

  1. 目标字符串 的开始位置里取一个跟 关键字 一样长的子字符串;
  2. 计算子该字符串的 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