常见字符串匹配算法以及 JS 的 Sring.prototype.indexOf() 源码分析

阅读数:65 2019 年 9 月 27 日 13:04

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

提到常见的字符串匹配算法,一般来说我们会想到一个是朴素算法(暴力破解),一个是比较巧妙的 KMP 算法。

KMP 算法图解

如果要在一个主串 ABCDABCDEF 里找关键字 ABCDABE,有哪些方法呢?我们很容易想到用暴力破解方法实现关键字搜索,如下图所示:

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

比较 i 指针和 j 指针指向的变量是否相同,如果相同,i 和 j 同时后移。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

本文约定待查找的字符串为主串 master 用 M 表示,关键字就是需要匹配的模式 pattern,用 P 表示。

到上图发现 M[i]!=P[j],于是 j 回到开头,将关键字右移一位,然后继续重复昨天的故事。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

上述是最坏的情况,一直比较到最后一位才不匹配,这种最坏情况下时间复杂度是 M*N,或许有人会觉得就这么暴力破解也行,不会这么巧每次都要到最后几位才发现不匹配。

然而数据在计算机里都是以 0101 这种二进制形式存储的,比如字符 1 是 00110001,字符 2 是 00110010,很容易发生直到最后几个字符才出现不匹配的情况,所以对于这样低效的算法, 我们是不能容忍的,因此有了本文接下来介绍的 KMP 算法。

当发现最后一个字符不匹配时,如果我们人为查找,不会重头一个一个匹配,而是会像下图这样查找,i 不动,j 移动到下图中位置。因为根据已经匹配的信息,我们知道 M 中指针 i 前面的两个 AB 和 P 中 j 前面的两个 AB 是相同的。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

KMP 算法就是利用已经部分匹配这个有效信息,保持 i 指针不回溯,移动模式串的 j 指针到有效的位置。关键点在于当 pattern 中某个字符与主串不匹配时,j 指针要移动到哪?

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

由上图,我们可以发现,当匹配失败时,j 要移动的下一个位置 k。存在着这样的性质:pattern 中最前面的 k 个字符和 j 之前的最后 k 个字符是一样的。

即 P[0,k-1] == P[j-k,j-1]

那么到底为什么可以移动到 k 呢?可以证明:

当 M[i] != P[j]
已经有 M[i-j,i-1] == P[0,j-1]
又有 P[0,k-1] == P[j-k,j-1]
可得 M[i-k,i-1] == P[0,k-1]

所以我们可以直接从 P[k] 开始比较。同时,我们还发现 k 是与主串无关的,只与 pattern 有关,看下图更明显。k 可以完全由 pattern 得到,k 只要满足 P[0,k-1] == P[j-k,j-1] 即可。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

那么我们完全可以根据 pattern 预处理生成一个 next 数组,next[j] 的值(即 k)表示,当 P[j] != M[i] 时,j 指针的下一步移动位置。

由下图可以发现一个规律,当 P[k]==P[j] 时,next[j+1]==k+1。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

那么当 P[k]!=P[j] 时呢?

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

上图看不出规律,转换成下图这样就比较明朗了。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

当就 j!=k 时,意味着没有 ABAEABAH 这样长的前缀,但我们可以退而求其次,在 ABAEABAH 中寻找最长的前缀。

则问题可以转化为在搜索 pattern ABAEABAH 时,H 和主串不一样了。 因此这时 k=next[k],然后重复上述步骤,继续把现在的 P[k] 和 P[j] 比较。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

走到上图发现现在的 P[k] 和 P[j] 还是不相等,则继续重复上述步骤,此时 k=next[next[k]]。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

发现终于 P[k]==P[j] 了,因此我们可以得到 next[j+1]==k+1(此时 k=next[next[next[j]]])。

总结一下:

比较 P[k] 和 P[j],当 P[k]!=P[j] 时,令 k=next[k],继续比较 P[k] 和 P[j],一直重复上述步骤,直到 P[k]==P[j] 或者 k 不能再前移为止, 则 next[j+1]==k+1

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

代码如下:

复制代码
/*
* @brief 计算部分匹配表,即 next 数组.
* @param[in] p 模式串
* @param[in] next 数组
* @return
*/
function compute_prefix (p, next) {
next[0] = -1; // 注释 1
let j = 0;
let k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
next[++j] = ++k; // 注释 2
} else {
k = next[k];
}
}
}

代码注释:

  • 注释 1 当 pattern 第一位就不匹配时,j 无法左移应保持不变,只需移动 i,所以初始化 next[0]=-1
  • 注释 2 如下图,当 j=1 时, 只能移动到 0 位置。而进入循环前初始化 k=-1, 进入循环首先就计算 next[1] 的值,所以当 k==-1 时 next[++j] = ++k

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

到现在,我们基本完成了生成预处理数组的任务,上面的代码看上去很不错了,然而它还有一个小缺陷。

如下图,当 P[j]==P[k] 时,之前的 P[j] 匹配不上,现在的 P[k] 肯定也匹配不上,所以这时的 k 要前移。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

所以在 P[j]==P[next[j]] 的特殊情况下,我们需要小小地修改一下代码:

复制代码
function compute_prefix (p, next) {
next[0] = -1; let j = 0; let k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
if (p[++j] == p[++k]) {
next[j] = next[k];
} else {
next[j] = k;
}
} else {
k = next[k];
}
}
}

完整的 KMP 算法如下:

复制代码
/*
* @brief KMP 算法
* @param[in] P pattern 模式串
* @param[in] M master 主串
* @return
*/
function KMP (M, P) {
let i = 0; // 主串的位置
let j = 0; // 模式串的位置
let next = [];
compute_prefix (P, next);
while (i < M.length && j < P.length) {
if (j == -1 || M[i] == P[j]) { // 当 j 为 -1 时,要移动的是 i,当然 j 也要归 0
i++;
j++;
} else {
j = next[j]; // i 不需要回溯了,j 回到指定位置
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}

看了上述 KMP 算法分析,各位童鞋是否觉得 KMP 在字符串搜索算法中算很不错的呢,我以前也这样以为,直到后来看到 Boyer-Moore 算法才发现,啊~ 当时我还太天真,Boyer-Moore 算法平均要比 KMP 快 3-5 倍,在实际的工业生产中,比如 GNU grep, 还有各种文本编辑器的查找功能(Ctrl+F)大多用的 BM(Boyer-Moore)算法。

KMP 算法利用的是 pattern 的前缀,而 Robert S. Boyer 教授和 J Strother Moore 教授发明的 BM 算法利用的则是 pattern 的后缀,关于 BM 算法的介绍,限于篇幅,本文就不详细介绍了,推荐阮一峰老师的博文,里面对于 BM 算法有详细的介绍 Boyer-Moore, 基于 BM 算法还有 Horspool 算法,感兴趣的童鞋可以自行查阅资料。

下图是朴素算法,KMP 算法,简化 BM 算法,BM 算法,Horspool 算法在不同长度的 pattern 下的性能比较。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

由图我们可以清楚发现,当 pattern 长度越长,BM 算法的表现越好,当长度大于 7 时,BM 以及基于 BM 衍生出来的算法简直是一骑绝尘,把 KMP 狠甩在后面。

那么现在,在了解常用的字符串匹配算法后,我们一起来看看 js 中 indexOf() 是怎么实现的。

v8 引擎源码实现源码地址看这里

在 src/string-search.h 文件中一共定义了五种搜索算法:

1.SingleCharSearch
2.LinearSearch
3.InitialSearch
4.BoyerMooreHorspoolSearch
5.BoyerMooreSearch

具体使用哪种,是在初始化 StringSearch 时根据 pattern 长度定义的。

部分代码如下:

复制代码
StringSearch(Isolate* isolate, Vector<const PatternChar> pattern)
: isolate_(isolate),
pattern_(pattern),
start_(Max(0, pattern.length() - kBMMaxShift)) {
if (sizeof(PatternChar) > sizeof(SubjectChar)) {
if (!IsOneByteString(pattern_)) {
strategy_ = &FailSearch;
return;
}
}
int pattern_length = pattern_.length();
if (pattern_length < kBMMinPatternLength) {
if (pattern_length == 1) {
strategy_ = &SingleCharSearch;
return;
}
strategy_ = &LinearSearch;
return;
}
strategy_ = &InitialSearch;
}

v8 是 c++ 实现的,不写 c++ 的童鞋看着可能不太习惯,没关系,上面的代码总结一下就是下图(设 pattern 长度为 length,其中 kBMMinPatternLength 在源码中设为 7)。

常见字符串匹配算法以及JS的Sring.prototype.indexOf()源码分析

可以看到 indexOf() 根据传入的 pattern 的长度选择对应长度下效率最高的匹配算法,真真是少林武功,集各家之所长啊~ 关于里面的每种算法,且待下回分解,总之一句话 indexOf(),你值得拥有~

作者介绍:
作者八路(企业代号名),目前负责贝壳找房商业化方向的前端工作。

本文转载自公众号贝壳产品技术(ID:gh_9afeb423f390)。

原文链接:

https://mp.weixin.qq.com/s/eLtQABruL9-Aut5fXl5x-g

评论

发布