論壇敏感詞過濾、內容審核系統常面臨「關鍵字數量大、待檢測文本長」的雙重挑戰。傳統方案逐個 indexOf 或正則遍歷,時間複雜度達 O(m × n)(m=關鍵字數,n=文本長),萬級關鍵字配合百萬字文本極易超時。
JavaScript 物件本質是高效雜湊表,天然適合構建字典樹。將所有關鍵字預處理為樹狀結構:
isEnd: true 表示完整詞const root = {
f: {
o: {
o: {
1: { isEnd: true },
2: { isEnd: true }
}
}
},
b: {
a: {
r: {
1: { isEnd: true },
2: { isEnd: true }
}
}
}
};
此結構將關鍵字集合壓縮為有向無環圖,搜尋時單次掃描文本即可完成所有匹配,時間複雜度降為 O(n × 平均詞長),與關鍵字數量幾乎無關。
function multiKeywordSearch(text, trieRoot) {
const matches = [];
for (let i = 0; i < text.length; i++) {
let node = trieRoot;
let j = i;
while (j < text.length && node[text[j]]) {
node = node[text[j]];
if (node.isEnd) {
matches.push({ keyword: text.slice(i, j + 1), index: i });
}
j++;
}
}
return matches;
}
關鍵優化點:
O(1) 屬性存取特性| 測試項目 | 數據規模 |
|---|---|
| 關鍵字庫 | 成語全集 19,830 條 |
| 待檢測文本 | 《誅仙》全集 1,659,219 字 |
| 執行環境 | Chrome 26 / i3-2312 CPU |
| 耗時 | 935 ms |
百萬字文本匹配兩萬關鍵字,**不足 1 秒**——證明字典樹在 JS 引擎上的驚人效能。
字典樹將「多模式匹配」轉化為「單模式掃描 + 狀態轉移」,完美契合 JS 物件高效雜湊特性。這不僅是演算法勝利,更是語言特性與資料結構深度融合的典範——證明了「用對工具,JS 也能跑出 C++ 級效能」。