如何使用Node.js快速搜尋字串？

字串搜尋是開發程式的時候時常會碰到的議題，由於常用，所以了解一個有效率進行字串搜尋的方式是很重要的。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))) {
    console.log(match);
    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

node-stringbuilder是一個使用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]