前綴樹介紹

前綴樹（Trie），也稱為字典樹或前綴字典樹，是一種特殊的多叉樹數(shù)據(jù)結(jié)構(gòu)。它用于高效地存儲和檢索字符串集合。以下是前綴樹的常見數(shù)據(jù)結(jié)構(gòu)和相關(guān)術(shù)語：

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

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

節(jié)點(diǎn)

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

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

下面是一個示例的前綴樹節(jié)點(diǎn)結(jié)構(gòu)：

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

    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é)點(diǎn)結(jié)構(gòu)，我們可以鏈接節(jié)點(diǎn)以形成一個樹形結(jié)構(gòu)，每個節(jié)點(diǎn)代表一個字符。通過不斷地添加子節(jié)點(diǎn)，我們可以構(gòu)建出完整的前綴樹，用于高效地存儲和搜索字符串集合。

初始化前綴樹

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

• 創(chuàng)建一個空的前綴樹，即一個根節(jié)點(diǎn)。

• 遍歷字符串集合，逐個插入字符串到前綴樹中。

• 對于每個字符串，從根節(jié)點(diǎn)開始，檢查當(dāng)前字符是否已經(jīng)存在于當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)中。

  • 如果存在，移動到該子節(jié)點(diǎn)，并繼續(xù)處理下一個字符。
  • 如果不存在，創(chuàng)建一個新的子節(jié)點(diǎn)，將當(dāng)前字符添加到子節(jié)點(diǎn)中，并移動到該子節(jié)點(diǎn)。

• 重復(fù)步驟3，直到字符串的所有字符都被插入到前綴樹中。

• 重復(fù)步驟2-4，直到字符串集合中的所有字符串都被插入到前綴樹中。

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

添加敏感詞

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

• 創(chuàng)建一個指向根節(jié)點(diǎn)的 current 變量，用于表示當(dāng)前節(jié)點(diǎn)。

• 遍歷敏感詞的每個字符。

• 對于每個字符，在當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)集合中查找是否存在字符對應(yīng)的子節(jié)點(diǎn)。

  • 如果存在子節(jié)點(diǎn)，則將 current 更新為該子節(jié)點(diǎn)；
  • 如果不存在子節(jié)點(diǎn)，則使用創(chuàng)建一個新的子節(jié)點(diǎn)，并將 current 更新為該新節(jié)點(diǎn)。

• 重復(fù)步驟3，直到遍歷完整個敏感詞的所有字符。

• 將最后一個字符所對應(yīng)的節(jié)點(diǎn)（即單詞的末尾字符）設(shè)置為單詞的結(jié)尾，將其 endOfWord 屬性設(shè)置為 true，表示該單詞在前綴樹中存在。

刪除敏感詞

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

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

敏感詞過濾

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

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

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

代碼實(shí)現(xiàn)

代碼實(shí)現(xiàn)如下：

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); // 將當(dāng)前節(jié)點(diǎn)標(biāo)記為非單詞結(jié)尾
            return current.getChildren().isEmpty(); // 判斷當(dāng)前節(jié)點(diǎn)是否有其他子節(jié)點(diǎn)
        }

        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); // 刪除當(dāng)前字符對應(yīng)的子節(jié)點(diǎn)
            return current.getChildren().isEmpty(); // 判斷當(dāng)前節(jié)點(diǎn)是否有其他子節(jié)點(diǎn)
        }

        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)) {  // 字母或數(shù)字，繼續(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 {  // 非字母或數(shù)字，結(jié)束當(dāng)前單詞匹配
                filteredText.append(currentWord);
                filteredText.append(c);
                currentWord.setLength(0);
                current = root;
            }
        }

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

    // 節(jié)點(diǎn)結(jié)構(gòu)
    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);
}

輸出結(jié)果：

這是一段包含***和敏感詞2的文本

在上述示例中，我們創(chuàng)建了一個 TrieFilter 類來實(shí)現(xiàn)敏感詞過濾功能。使用 addWord 方法將敏感詞添加到前綴樹中，然后使用 filter 方法對文本進(jìn)行過濾，將匹配到的敏感詞替換為 ***，使用 deleteWord 方法從前綴樹中刪除敏感詞。

到此這篇關(guān)于SpringBoot使用前綴樹實(shí)現(xiàn)敏感詞過濾示例的文章就介紹到這了,更多相關(guān)SpringBoot敏感詞過濾內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論