DIV CSS 佈局教程網

JavaScript 上萬關鍵字瞬間匹配:用樹結構把兩萬詞壓進一秒內
編輯:關於JavaScript     

提到關鍵字搜索,直覺反應無非是 indexOf、replace 這類字串函式,最多再加上正則表達式。實作起來確實簡單,但背後的效率問題值得細究。

論壇的關鍵字過濾就是典型場景。一般情況下需過濾的關鍵字數量與待檢測的文本長度都不大,一瞬間的過程沒什麼好在意的。但若關鍵字不再屈指可數,而是成千上萬,待檢測的文本又是一整篇長文,結果就不那麼樂觀了。每多一個關鍵字,就要多做一次全文檢索,最終花費的時間會遠遠超出可接受範圍。

為什麼要用樹而不是迴圈

既然要處理的是極端規模的搜索,逐個遍歷顯然行不通。用 JavaScript 實現,不用 Hash 表實在太可惜了——這門語言對物件(也就是雜湊表)有著天獨厚的支援,不妨拿少量空間去換大量時間。

先看個例子。假設有這幾個關鍵字:foo1、foo2、bar1、bar2。既然要用空間換時間,那就先預處理它們。顯而易見,樹狀結構在這裡最有優勢:

var Root = {
    f: {
        o: {
            o: {
                "1": true,
                "2": true
            }
        }
    },
    b: {
        a: {
            r: {
                "1": true,
                "2": true
            }
        }
    }
};

這層層嵌套的結構正如一棵樹:每個字元是樹的一個分枝,最後一個字元則是樹葉,不再往下長出新節點。熟悉 JSON 的話會覺得很親切。

匹配過程

想通了這層結構,演算法就很直白:拿文章裡的每個字,沿著這棵樹往下走。能走到樹葉的,說明當前位置就是一個關鍵字;中途找不到對應枝幹的,自然就不是。

例如 foo1,順著結構存取 Root['f']['o']['o']['1'],抵達終點且值為 true,即完成一次匹配。之後跳過 foo1 的長度,繼續往後檢索。

因此,整篇文章只需一次掃描,就能找出所有關鍵字的位置。由於 JS 物件的屬性存取本身就是雜湊查表,時間複雜度接近 O(1),所謂「尋找枝幹」的動作非常快。

值得注意的一點:關鍵字的數量與搜索時間幾乎無關,它只影響了樹的寬度;真正決定耗時的是文章長度。這正是這個演算法相對於「關鍵字數 × 文本長度」的暴力做法的根本優勢。

極限測試

關鍵字:成語全集(19830 條)
內容:某部長篇小說全文(1659219 字)
用時:935ms
環境:Chrome 26 / i3-2312 CPU

160 萬字的文章,匹配近 2 萬個關鍵字,不到一秒。可見充分利用 JavaScript 的靈活性,仍能發揮很大的潛力。

這其實是 Aho-Corasick

這套做法在字串匹配領域有個正式名稱:Aho-Corasick 演算法,1975 年提出,至今仍是多模式匹配的標準解法。本文的實作是它的簡化版,缺少了「失敗指針」(fail pointer)這一關鍵元件。

少了失敗指針會有什麼問題?考慮關鍵字 abc 與 bc,文本是 abc。走到 a 時沿樹前進,到 b 時發現 ab 沒有子節點 c 的問題,但如果文本是 abx 而關鍵字包含 bx,簡化版會在 x 處直接放棄,而完整版能透過失敗指針回退到 b 這個節點繼續匹配。也就是說,簡化版只能處理「前綴不重叠」的關鍵字集合。成語這種多為四字、彼此前綴重疊機率低的資料碰巧很適合,但換成英文單字列表就會漏掉大量結果。

如果你要自己在專案裡實作,幾個實務建議:節點用 Map 而非純物件,避免 __proto__、constructor 這類字元序列污染原型鏈;節點結構用 { children: Map, isEnd: bool, fail: 節點 };建樹(build)一次即可,匹配階段可重複使用。

不過更實際的建議是:先確認你真的需要它。瀏覽器端做敏感詞過濾,通常幾百到幾千個詞,用 indexOf 迴圈搭配 includes 就綽綽有餘;真要處理萬級規模,Web Worker 丟到背景執行緒跑,比優化演算法更能改善使用者感受。演算法優化該是最後手段,而不是第一個想到的方案。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved