SpringBoot使用前綴樹實現敏感詞過濾示例

更新時間：2023年10月30日 09:54:12 作者：I'm?Jie

最近項目用到了敏感詞過濾,本文主要就來介紹一下SpringBoot使用前綴樹實現敏感詞過濾示例,具有一定的參考價值,感興趣的可以了解一下

前綴樹介紹

前綴樹（Trie），也稱為字典樹或前綴字典樹，是一種特殊的多叉樹數據結構。它用于高效地存儲和檢索字符串集合。以下是前綴樹的常見數據結構和相關術語：

節(jié)點（Node）：每個節(jié)點包含一個字符和指向子節(jié)點的鏈接。通常使用散列表、數組或其他數據結構來存儲子節(jié)點鏈接。
根節(jié)點（Root Node）：前綴樹的頂層節(jié)點，沒有父節(jié)點。
子節(jié)點（Child Node）：一個節(jié)點的直接后代節(jié)點。
葉節(jié)點（Leaf Node）：沒有后續(xù)節(jié)點的節(jié)點，用來表示字符串的結束字符。
邊（Edge）：連接相鄰節(jié)點的鏈接，每個邊上都標有一個字符。
樹的高度（Height）：從根節(jié)點到最深葉節(jié)點的最長路徑。
前綴（Prefix）：從根節(jié)點到任意節(jié)點的路徑，表示一個字符串的前綴。

基于這些術語，前綴樹的基本操作包括插入、搜索、刪除和前綴匹配。通過構建一個前綴樹，可以實現高效地存儲和檢索大量字符串，快速判斷一個字符串是否是集合中的成員，并找到具有給定前綴的所有字符串。

節(jié)點

前綴樹（Trie）的節(jié)點結構通常由兩部分組成：節(jié)點值和子節(jié)點集合。子節(jié)點集合通常使用散列表、數組或其他數據結構。

我們還需要使用 endOfWord 標識該節(jié)點是否為一個單詞的結尾。如果某個節(jié)點的 isEndOfWord 為 true，則表示從根節(jié)點到當前節(jié)點的路徑構成了一個完整的單詞，即過濾詞。

下面是一個示例的前綴樹節(jié)點結構：

class TrieNode {
    private Map<Character, TrieNode> children; // 子節(jié)點集合
    private boolean endOfWord; // 標識是否為單詞的結尾

    public TrieNode() {
        children = new HashMap<>();
        endOfWord = false;
    }

    public Map<Character, TrieNode> getChildren() {
        return children;
    }

    public boolean isEndOfWord() {
        return endOfWord;
    }

    public void setEndOfWord(boolean endOfWord) {
        this.endOfWord = endOfWord;
    }
}

通過這種節(jié)點結構，我們可以鏈接節(jié)點以形成一個樹形結構，每個節(jié)點代表一個字符。通過不斷地添加子節(jié)點，我們可以構建出完整的前綴樹，用于高效地存儲和搜索字符串集合。

初始化前綴樹

前綴樹有一個根節(jié)點（Root Node）作為起始節(jié)點。前綴樹的初始化過程如下：

創(chuàng)建一個空的前綴樹，即一個根節(jié)點。
遍歷字符串集合，逐個插入字符串到前綴樹中。
對于每個字符串，從根節(jié)點開始，檢查當前字符是否已經存在于當前節(jié)點的子節(jié)點中。
- 如果存在，移動到該子節(jié)點，并繼續(xù)處理下一個字符。
- 如果不存在，創(chuàng)建一個新的子節(jié)點，將當前字符添加到子節(jié)點中，并移動到該子節(jié)點。
重復步驟3，直到字符串的所有字符都被插入到前綴樹中。
重復步驟2-4，直到字符串集合中的所有字符串都被插入到前綴樹中。

通過上述初始化過程，我們可以構建一個包含所有字符串集合中字符串的前綴樹。這樣，在后續(xù)的搜索或過濾操作中，我們可以利用前綴樹的特性來提高效率，快速地查找和處理字符串。

添加敏感詞

我們可以將一個敏感詞插入到前綴樹中。每個字符都對應著一個節(jié)點，通過連接節(jié)點的方式，形成了一個表示敏感詞的路徑。最后一個字符對應的節(jié)點被標記為敏感詞的結尾，以便在后續(xù)的搜索操作中判斷是否存在完整的敏感詞。前綴樹中添加一個敏感詞的過程如下：

創(chuàng)建一個指向根節(jié)點的 current 變量，用于表示當前節(jié)點。
遍歷敏感詞的每個字符。
對于每個字符，在當前節(jié)點的子節(jié)點集合中查找是否存在字符對應的子節(jié)點。
- 如果存在子節(jié)點，則將 current 更新為該子節(jié)點；
- 如果不存在子節(jié)點，則使用創(chuàng)建一個新的子節(jié)點，并將 current 更新為該新節(jié)點。
重復步驟3，直到遍歷完整個敏感詞的所有字符。
將最后一個字符所對應的節(jié)點（即單詞的末尾字符）設置為單詞的結尾，將其 endOfWord 屬性設置為 true，表示該單詞在前綴樹中存在。

刪除敏感詞

要刪除前綴樹中的敏感詞，可以采用遞歸的方式遍歷前綴樹來查找待刪除的敏感詞。默認從根節(jié)點開始，并通過字符索引遞歸地將路徑沿著前綴樹向下移動。

如果到達了敏感詞的最后一個字符，表示找到了待刪除的單詞節(jié)點。將該節(jié)點的 endOfWord 屬性設置為 false，表示該單詞不再存在于前綴樹中，并判斷當前節(jié)點是否有其他子節(jié)點，如果沒有子節(jié)點則刪除當前字符對應的子節(jié)點。
如果還沒有到達敏感詞的最后一個字符，繼續(xù)向下遍歷前綴樹，直到找到敏感詞的最后一個字符。如果遞歸地刪除該字符之后，發(fā)現當前節(jié)點沒有其他子節(jié)點了，則可以將當前字符對應的子節(jié)點從父節(jié)點的子節(jié)點集合中刪除，保持樹的結構和有效性。

敏感詞過濾

假設我們已經初始化完成一個前綴樹，其中包含以下敏感詞：「bad」、「bar」、「byd」、「cao」，我們對「This is a bad example. The bar is closed.」進行過濾：

逐個字符遍歷「This is a bad example. The bar is closed.」：
- 第一個字符「T」與前綴樹匹配不上，因此將其添加到過濾后文本中。
- 第二個字符「h」與前綴樹匹配不上，因此將其添加到過濾后文本中。
- 第三個字符「i」與前綴樹匹配不上，因此將其添加到過濾后文本中。
- 第四個字符「s」與前綴樹匹配不上，因此將其添加到過濾后文本中。
由于字符「」（空格）不是字母或數字，直接添加到過濾后文本中，重置前綴樹的當前節(jié)點為根節(jié)點。
重復步驟1和2，直到遍歷完整個原始文本。
遍歷到「bad」時：
- 第一個字符「b」與前綴樹節(jié)點 b 匹配，繼續(xù)處理下一個字符。
- 第二個字符「a」與前綴樹節(jié)點 a 匹配，繼續(xù)處理下一個字符。
- 第三個字符「d」與前綴樹節(jié)點 d 匹配。
當前單詞為「bad」，由于結束符號「d」的 endOfWord 屬性為 true，代表這是一個敏感詞，將當前單詞替換為「***」并添加到過濾后文本中。
「bar」匹配流程相同。
最終過濾后的文本為：「This is a *** example. The *** is closed.」

通過前綴樹，我們可以高效地找到和替換敏感詞，將其過濾或標記為合適的內容。這樣能夠保護用戶免受敏感詞的影響。

代碼實現

代碼實現如下：

import java.util.HashMap;
import java.util.Map;

public class TrieFilter {
    private TrieNode root;

    public TrieFilter() {
        root = new TrieNode();
    }

    // 添加敏感詞
    public void addWord(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            current = current.getChildren().computeIfAbsent(c, k -> new TrieNode());
        }
        current.setEndOfWord(true);
    }

    // 刪除敏感詞
    public void deleteWord(String word) {
        deleteWord(root, word, 0);
    }

    private boolean deleteWord(TrieNode current, String word, int index) {
        if (index == word.length()) {
            if (!current.isEndOfWord()) {
                return false; // 單詞不存在于前綴樹中，無需刪除
            }
            current.setEndOfWord(false); // 將當前節(jié)點標記為非單詞結尾
            return current.getChildren().isEmpty(); // 判斷當前節(jié)點是否有其他子節(jié)點
        }

        char c = word.charAt(index);
        TrieNode child = current.getChildren().get(c);
        if (child == null) {
            return false; // 單詞不存在于前綴樹中，無需刪除
        }

        boolean shouldDeleteChild = deleteWord(child, word, index + 1);

        if (shouldDeleteChild) {
            current.getChildren().remove(c); // 刪除當前字符對應的子節(jié)點
            return current.getChildren().isEmpty(); // 判斷當前節(jié)點是否有其他子節(jié)點
        }

        return false;
    }

    // 敏感詞過濾
    public String filter(String text) {
        StringBuilder filteredText = new StringBuilder();
        StringBuilder currentWord = new StringBuilder();
        TrieNode current = root;

        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);

            if (Character.isLetterOrDigit(c)) {  // 字母或數字，繼續(xù)匹配
                current = current.getChildren().get(Character.toLowerCase(c));
                if (current != null) {
                    currentWord.append(c);
                    if (current.isEndOfWord()) {
                        currentWord.replace(0, currentWord.length(), "***");
                    }
                } else {
                    filteredText.append(currentWord);
                    filteredText.append(c);
                    currentWord.setLength(0);
                    current = root;
                }
            } else {  // 非字母或數字，結束當前單詞匹配
                filteredText.append(currentWord);
                filteredText.append(c);
                currentWord.setLength(0);
                current = root;
            }
        }

        filteredText.append(currentWord);
        return filteredText.toString();
    }

    // 節(jié)點結構
    class TrieNode {
        private Map<Character, TrieNode> children;
        private boolean endOfWord;

        public TrieNode() {
            children = new HashMap<>();
            endOfWord = false;
        }

        public Map<Character, TrieNode> getChildren() {
            return children;
        }

        public boolean isEndOfWord() {
            return endOfWord;
        }

        public void setEndOfWord(boolean endOfWord) {
            this.endOfWord = endOfWord;
        }
    }
}

使用示例：

public static void main(String[] args) {
  TrieFilter filter = new TrieFilter();
  filter.addWord("敏感詞1");
  filter.addWord("敏感詞2");
  filter.deleteWord("敏感詞2");

  String text = "這是一段包含敏感詞1和敏感詞2的文本";
  String filteredText = filter.filter(text);
  System.out.println(filteredText);
}

輸出結果：