如何用前缀树实现敏感词过滤 ?

什么前缀树（字典树）？

1. **每个节点代表一个字符：**字符连接成路径，从根节点到一个节点的一条路径表示一个单词的前缀或完整单词。
2. **单词存储在路径中：**每个单词由树中的路径唯一表示，而不是节点本身。因此，前缀树可以共用前缀的部分，达到节省存储空间的目的。
3. **查找效率高：**前缀树非常适合用来查找具有相同前缀的字符串，时间复杂度为 O(m)，其中 m 是查询字符串的长度。

主要操作

• 插入（Insert）：将一个单词逐字符插入前缀树中；
• 查找（Search）：在树中查找是否存在某个单词；
• 前缀匹配（StartsWith）：查找是否存在以某前缀开头的单词；
• 删除（Delete）：从树中删除某个单词（这个场景用得不多）。

应用场景

1. 敏感词过滤：在文本中快速识别并替换敏感词。
2. 自动补全：基于已有单词，快速查找出以某前缀开头的所有单词，应用于搜索引擎的自动补全功能。
3. 拼写检查：拼写检查时可以快速查找并给出修正建议。
4. 字符串集合查找：用于快速查询一个字符串是否属于一个字符串集合。

结构

假设要插入单词集合 ["hey", "hello", "ik", "ikun"]，构建的前缀树可能如下所示：

        (root)
       /     \
      h       i
     /         \
    e           k
   / \           \
  y   l           u
     / \           \
    l   o           n
   /
  o

代码实现

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    contains(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    delete(word) {
        const deleteRecursively = (node, word, depth) => {
            if (!node) return false;

            // 如果已经达到单词的末尾
            if (depth === word.length) {
                // 仅在节点确实是单词结尾时设置 isEndOfWord 为 false
                if (node.isEndOfWord) {
                    node.isEndOfWord = false;
                    // 如果没有任何子节点，则可以删除此节点
                    return Object.keys(node.children).length === 0;
                }
                return false;
            }

            const char = word[depth];
            const childNode = node.children[char];

            // 递归删除子节点
            const shouldDeleteChild = deleteRecursively(
                childNode,
                word,
                depth + 1
            );

            if (shouldDeleteChild) {
                delete node.children[char];
                // 如果当前节点不是单词结尾并且没有其他子节点，可以删除
                return (
                    Object.keys(node.children).length === 0 && !node.isEndOfWord
                );
            }

            return false;
        };

        deleteRecursively(this.root, word, 0);
    }

    filter(text) {
        let result = '';
        let i = 0;

        while (i < text.length) {
            let node = this.root;
            let j = i;
            let matchLength = 0;

            while (j < text.length && node.children[text[j]]) {
                node = node.children[text[j]];
                j++;
                if (node.isEndOfWord) {
                    matchLength = j - i;
                }
            }
            if (matchLength > 0) {
                result += '*'.repeat(matchLength);
                i += matchLength;
            } else {
                result += text[i];
                i++;
            }
        }

        return result;
    }
}

// 示例使用
const trie = new Trie();
trie.insert('敏感');

const inputText = '这里包含敏感词1和其他内容。';
const filteredText = trie.filter(inputText);
const inputText2 = '灵敏';
const filteredText2 = trie.filter(inputText2);

console.log(filteredText); // 这里包含*感词1和其他内容。
console.log(filteredText2); // 灵敏

参考

力扣 208. 实现 Trie (前缀树)https://leetcode.cn/problems/implement-trie-prefix-tree/description/