萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

萬級關鍵字毫秒級匹配:JavaScript 字典樹(Trie)實戰解析

痛點:傳統關鍵字過濾的效能瓶頸

論壇敏感詞過濾、內容審核系統常面臨「關鍵字數量大、待檢測文本長」的雙重挑戰。傳統方案逐個 indexOf 或正則遍歷,時間複雜度達 O(m × n)(m=關鍵字數,n=文本長),萬級關鍵字配合百萬字文本極易超時。

破局思路:空間換時間,字典樹(Trie)索引

JavaScript 物件本質是高效雜湊表,天然適合構建字典樹。將所有關鍵字預處理為樹狀結構:

  • 每個字符為一層節點
  • 共同前綴共用路徑
  • 葉節點標記 isEnd: true 表示完整詞

預處理範例:關鍵字 [foo1, foo2, bar1, bar2]

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;
}

關鍵優化點:

  1. 利用 JS 物件 O(1) 屬性存取特性
  2. 失配即跳出內層迴圈,避免無效比對
  3. 跳過已匹配關鍵字長度,減少重複掃描

極限壓測數據

測試項目數據規模
關鍵字庫成語全集 19,830 條
待檢測文本《誅仙》全集 1,659,219 字
執行環境Chrome 26 / i3-2312 CPU
耗時935 ms

百萬字文本匹配兩萬關鍵字,**不足 1 秒**——證明字典樹在 JS 引擎上的驚人效能。

工程化考量

  • 記憶體佔用:萬級關鍵字樹約數 MB,現代瀏覽器輕鬆承受
  • 動態更新:支援增量插入/刪除節點,無需重建整棵樹
  • Unicode 支援:JS 字串原生 UTF-16,中英文混排無壓力
  • 輸出格式:可擴展輸出位置、原詞、替換建議等豐富資訊

總結

字典樹將「多模式匹配」轉化為「單模式掃描 + 狀態轉移」,完美契合 JS 物件高效雜湊特性。這不僅是演算法勝利,更是語言特性與資料結構深度融合的典範——證明了「用對工具,JS 也能跑出 C++ 級效能」。

copyright © 萬盛學電腦網 all rights reserved