談到關鍵字搜尋,多數人第一時間想到的就是 indexOf、replace,最多再補上正規表達式。實作起來確實簡單,但你有沒有算過背後的效能帳?
論壇的關鍵字過濾之所以感覺很快,是因為關鍵字屈指可數、待測文本也不長,那一瞬間的開銷不值得計較。可一旦關鍵字從幾十個暴增到成千上萬,檢測對象又是一篇長文,結論就完全不同了。每多一個關鍵字,就多一遍全文掃描,總耗時會遠遠超出可接受範圍。
既然要處理的是極端場景,逐一遍歷顯然行不通。既然手上拿的是 JavaScript,不用 Hash 表實在太可惜——這門語言對「表」結構有著得天獨厚的支援,正好拿少量空間去換大量時間。
以 foo1、foo2、bar1、bar2 為例。預先處理後的結構長這樣,熟悉 JSON 的人會覺得很親切:
var Root = {
f: { o: { o: { 1: true } } },
b: { a: { r: { 1: true, 2: true } } }
};
這層層嵌套正如一棵樹:每個字元是一個分支,走到最後一個字元就成了樹葉,不再往下延伸。
於是只要拿文章裡的每個字沿著這棵樹往下走即可。能走到樹葉的,說明當前位置就是一個關鍵字;中途找不到對應分支的,自然不是。
例如 foo1,沿著 Root 一路拜訪到 Root['f']['o']['o']['1'],就完成了一次匹配,接著跳過 foo1 的長度繼續往後掃。整篇文章只需一次走訪,就能找出所有關鍵字的位置。由於 JS 的 Hash 表效能極高,所謂「找分支」也快得驚人。
值得注意的一點:關鍵字數量幾乎不影響搜尋時間,它只決定了樹有多寬;真正決定耗時的是文章長度。
關鍵字:成語全集(19830 條)
內容:誅仙全集.txt(1659219 字)
耗時:935ms
環境:Chrome 26 / i3-2312 CPU
160 萬字的長文、近 2 萬個關鍵字,不到一秒完成。可見把 JavaScript 的靈活性用到位,還有相當可觀的潛力可挖。