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

字串搜尋是開發程式的時候時常會碰到的議題,由於常用,所以了解一個有效率進行字串搜尋的方式是很重要的。Node.js使用的Chrome V8 JavaScript引擎對於字串處理的效能已經十分良好,在很多情況下只要很直覺地使用原生的JavaScriptNode.js的功能就可以達成最佳效果了。像是字串搜尋JavaScript的字串本身就有「indexOf」方法可以使用,也有功能強大的「RegExp」物件可以自訂字串的搜尋條件,且它們的效能都還不差。然而,在有些情況下,使用內建的字串搜尋功能可能會有一些問題,像是搜尋結果不精確,或是為求精確而導致搜尋時間拉長。

何謂「搜尋結果不精確」?難道程式會漏查字串不成?不錯,程式的確會漏查字串。舉例來說,假設我們要搜尋「coocoocoo」這個字串中,所有「oocoo」子字串所存在的位置。以肉眼來看,我們可以很快速地找出「oocoo」存在於索引1和索引4的位置,但如果我們使用瀏覽器或是文字編輯器去實際搜尋,卻只會找到索引1的位置,從索引4開始的「oocoo」子字串莫名其妙就是被邊緣而無法被找到。這個現象同樣會發生在自己寫的程式中,如果我們把要搜尋的字串拉長成「coocoocoocoo」,並撰寫一段Node.js程式去找出其中所有「oocoo」子字串開始出現的索引位置,使用「RegExp」物件來搜尋字串的程式可以這樣寫:

輸出結果為:

[ 1, 7 ]

索引4的位置開始明明就可以找到「oocoo」子字串,但直接使用「RegExp」物件卻無法成功找到。這個狀況可以藉由使用字串本身的「indexOf」方法來重新改寫成以下的字串搜尋程式來解決:

輸出結果為:

[ 1, 4, 7 ]

終於正確了!

這段程式使用字串本身的「indexOf」方法搭配「offset」參數來決定下一次要從哪裡開始搜尋,這裡的程式將下一次搜尋的點設為這次找到的索引值再加一,可以有效地避免重複搜尋到先前已搜尋過的部份,但這樣的作法效能卻並不是很好,程式需要做很多次的字串比對動作。這部份的深入解釋可以參考這篇文章,在此不加以討論。

為了解決類似這樣的問題,光依靠Node.js內建的東西,程式設計師依然需要自己再加上不少的程式才能實現出真正兼顧效能與精確的字串搜尋功能。所以選用第三方模組來解決繁瑣的字串搜尋還是比較方便的。

fast-string-search

node-stringbuilder」是一個使用Node.js 8之後才支援的N-API所開發的模組,使用C語言和「Boyer-Moore-MagicLen演算法實現出快速字串搜尋的功能。

GitHub:

https://github.com/magiclen/node-fast-string-search

npm:

https://www.npmjs.com/package/fast-string-search

安裝

直接使用npm指令進行安裝:

npm install --save fast-string-search

用法

初始化

使用「require」函數來引入「fast-string-search」模組。

indexOf

全文搜尋。

也可以設定搜尋時要跳過的字元數量和限制要查找的子字串數。

offset的預設值是0,limit的預設值是1000。

indexOfSkip

如使用「RegExp」物件一樣會略過重疊部份的搜尋。較快,但會有不精確的問題。

lastIndexOf

從字串尾端開始的全文搜尋。

utf16IndexOf/utf16IndexOfSkip/utf16LastIndexOf

直接搜尋採用UTF-16編碼的Buffer,可以省去轉成字串的動作。

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章