C++ 敏感詞過濾系統：Trie 樹 (字典樹) 實現與 AC 自動機優化

需求背景

實現高性能敏感詞過濾：給定敏感詞庫，對輸入文本進行檢測並替換 (如用 * 遮罩)。要求支持中英文混合、大小寫不敏感、高併發。

核心數據結構：Trie 樹 (字典樹)

每個節點存儲：

• 子節點映射：map 或數組 Node* next[CHARS]
• 結束標記：bool isEnd
• (可選) 故障指針：用於 AC 自動機

基本 Trie 實現 (C++11)

struct TrieNode {
    unordered_map children;
    bool isEnd = false;
    TrieNode() {}
    ~TrieNode() {
        for (auto& p : children) delete p.second;
    }
};

class SensitiveFilter {
    TrieNode* root;
public:
    SensitiveFilter() : root(new TrieNode()) {}
    ~SensitiveFilter() { delete root; }

    void addWord(const string& word) {
        TrieNode* p = root;
        for (char c : word) {
            if (!p->children.count(c)) p->children[c] = new TrieNode();
            p = p->children[c];
        }
        p->isEnd = true;
    }

    // 簡單過濾：逐字符匹配，命中則替換
    string filter(const string& text) {
        string result;
        for (size_t i = 0; i < text.size(); ) {
            TrieNode* p = root;
            size_t j = i;
            int lastEnd = -1;
            while (j < text.size() && p->children.count(text[j])) {
                p = p->children[text[j]];
                if (p->isEnd) lastEnd = j;
                ++j;
            }
            if (lastEnd != -1) {
                result.append(lastEnd - i + 1, '*');
                i = lastEnd + 1;
            } else {
                result.push_back(text[i]);
                ++i;
            }
        }
        return result;
    }
};

進階：AC 自動機 (Aho-Corasick) —— 多模式匹配 O(n + m + z)

Trie 逐字符匹配最壞 O(n × maxLen)。AC 自動機構建失敗指針，單次掃描文本即可找出所有敏感詞位置。

AC 自動機核心結構

struct ACNode {
    array next{};
    ACNode* fail = nullptr;
    bool isEnd = false;
    int wordLen = 0; // 敏感詞長度，用於替換
    ACNode() { next.fill(nullptr); }
};

class ACFilter {
    ACNode* root;
public:
    ACFilter() : root(new ACNode()) {}
    ~ACFilter() { deleteTree(root); }

    void addWord(const string& word) {
        ACNode* p = root;
        for (char c : word) {
            int idx = tolower(c) - 'a';
            if (!p->next[idx]) p->next[idx] = new ACNode();
            p = p->next[idx];
        }
        p->isEnd = true;
        p->wordLen = word.length();
    }

    void buildFail() {
        queue q;
        root->fail = root;
        for (int i = 0; i < 26; ++i) {
            if (root->next[i]) {
                root->next[i]->fail = root;
                q.push(root->next[i]);
            } else {
                root->next[i] = root; // 統一跳轉
            }
        }
        while (!q.empty()) {
            ACNode* u = q.front(); q.pop();
            for (int i = 0; i < 26; ++i) {
                if (u->next[i]) {
                    u->next[i]->fail = u->fail->next[i];
                    u->next[i]->isEnd |= u->next[i]->fail->isEnd; // 合併輸出
                    q.push(u->next[i]);
                } else {
                    u->next[i] = u->fail->next[i];
                }
            }
        }
    }

    string filter(const string& text) {
        string result = text;
        ACNode* p = root;
        for (size_t i = 0; i < text.size(); ++i) {
            int idx = tolower(text[i]) - 'a';
            if (idx < 0 || idx >= 26) { p = root; continue; }
            p = p->next[idx];
            if (p->isEnd) {
                // 替換結尾為 i，長度 p->wordLen
                for (int k = 0; k < p->wordLen; ++k)
                    result[i - k] = '*';
            }
        }
        return result;
    }
};

中文支持：UTF-8 處理

中文字符佔 3 字節 (UTF-8)。選項：

1. 按字節建 Trie：直接用 unsigned char 作為邊，節點數增加但實現簡單
2. 解碼為 Unicode 碼點：用 char32_t 或 uint32_t，邊數大需用 unordered_map
3. 雙數組 Trie (Double-Array Trie)：極致壓縮，靜態構建，查詢極快

UTF-8 字節級 Trie 簡易版

struct ByteTrieNode {
    array next{};
    bool isEnd = false;
    ByteTrieNode() { next.fill(nullptr); }
};

// 插入時直接按字節遍歷
void addWordBytes(ByteTrieNode* root, const string& word) {
    ByteTrieNode* p = root;
    for (unsigned char c : word) {
        if (!p->next[c]) p->next[c] = new ByteTrieNode();
        p = p->next[c];
    }
    p->isEnd = true;
}

工程優化建議

總結

• 基礎 Trie：實現簡單，適合詞庫較小、查詢不極頻繁場景
• AC 自動機：單次掃描多模式匹配，適合高吞吐、長文本、大詞庫
• 中文處理：UTF-8 字節級 Trie 最通用；生產環境推薦 Double-Array Trie + 分詞預處理
• 替換策略：最長匹配優先、全匹配替換、標記位置二次處理

敏感詞過濾是典型的「多模式匹配」問題，Trie/AC 自動機是標準解法。理解其原理與工程化細節，可構建高性能、可維護的內容安全系統。