字符串搜索是开发程序的时候时常会碰到的议题,由于常用,所以了解一个有效率进行字符串搜索的方式是很重要的。Node.js 使用的 Chrome V8 JavaScript 引擎对于字符串处理的性能已经十分良好,在很多情况下只要很直觉地使用原生的 JavaScript 或 Node.js 的功能就可以达成最佳效果了。像是字符串搜索,JavaScript 的字符串本身就有 indexOf 方法可以使用,也有功能强大的 RegExp 对象可以自订字符串的搜索条件,且它们的性能都还不差。然而,在有些情况下,使用内置的字符串搜索功能可能会有一些问题,像是搜索结果不精确,或是为求精确而导致搜索时间拉长。
何谓「搜索结果不精确」?难道程序会漏查字符串不成?不错,程序的确会漏查字符串。举例来说,假设我们要搜索 coocoocoo 这个字符串中,所有 oocoo 子字符串所存在的位置。以肉眼来看,我们可以很快速地找出 oocoo 存在于索引 1 和索引 4 的位置,但如果我们使用浏览器或是文字编辑器去实际搜索,却只会找到索引 1 的位置,从索引 4 开始的 oocoo 子字符串莫名其妙就是被边缘而无法被找到。这个现象同样会发生在自己写的程序中,如果我们把要搜索的字符串拉长成 coocoocoocoo,并撰写一段 Node.js 程序去找出其中所有 oocoo 子字符串开始出现的索引位置,使用 RegExp 对象来搜索字符串的程序可以这样写:
const text = "coocoocoocoo";
const regex = /oocoo/g;
let match;
const indexArray = [];
while ((match = regex.exec(text))) {
indexArray.push(match.index);
}
console.log(indexArray);
输出结果为:
索引 4 的位置开始明明就可以找到 oocoo 子字符串,但直接使用 RegExp 对象却无法成功找到。这个状况可以借由使用字符串本身的 indexOf 方法来重新改写成以下的字符串搜索程序来解决:
const text = "coocoocoocoo";
const pattern = "oocoo";
let offset = 0;
let index;
const indexArray = [];
while ((index = text.indexOf(pattern, offset)) >= 0) {
indexArray.push(index);
offset = index + 1;
}
console.log(indexArray);
输出结果为:
终于正确了!
这段程序使用字符串本身的 indexOf 方法搭配 offset 参数来决定下一次要从哪里开始搜索,这里的程序将下一次搜索的点设为这次找到的索引值再加一,可以有效地避免重复搜索到先前已搜索过的部份,但这样的作法性能却并不是很好,程序需要做很多次的字符串比对动作。这部份的深入解释可以参考这篇文章,在此不加以讨论。
为了解决类似这样的问题,光依靠 Node.js 内置的东西,程序员依然需要自己再加上不少的程序才能实现出真正兼顾性能与精确的字符串搜索功能。所以选用第三方模块来解决繁琐的字符串搜索还是比较方便的。
fast-string-search
fast-string-search 是一个使用 Node.js 8 之后才支持的 N-API 所开发的模块,使用 C 语言和「Boyer-Moore-MagicLen」算法实现出快速字符串搜索的功能。
npmjs.com
npm 安装指令
使用方法
初始化
使用 require 函数来引入 fast-string-search 模块。
const fss = require("fast-string-search");
indexOf
全文搜索。
const a = fss.indexOf("coocoocoocoo", "oocoo"); // [1, 4, 7]
也可以设置搜索时要跳过的字符数量和限制要查找的子字符串数。
const a = fss.indexOf(source, pattern, offset, limit);
offset 的默认值是 0,limit 的默认值是 1000。
indexOfSkip
如使用 RegExp 对象一样会略过重叠部份的搜索。较快,但会有不精确的问题。
const a = fss.indexOfSkip("coocoocoocoo", "oocoo"); // [1, 7]
lastIndexOf
从字符串尾端开始的全文搜索。
const a = fss.lastIndexOf("coocoocoocoo", "oocoo"); // [7, 4, 1]
utf16IndexOf/utf16IndexOfSkip/utf16LastIndexOf
直接搜索采用 UTF-16 编码的 Buffer,可以省去转成字符串的动作。
const a = fss.utf16IndexOf(Buffer.from("coocoocoocoo", "utf16le"), Buffer.from("oocoo", "utf16le")); // [1, 4, 7]
