前綴樹(shù)介紹

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

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

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

節(jié)點(diǎn)

前綴樹(shù)（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)識(shí)該節(jié)點(diǎn)是否為一個(gè)單詞的結(jié)尾。如果某個(gè)節(jié)點(diǎn)的 isEndOfWord 為 true，則表示從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑構(gòu)成了一個(gè)完整的單詞，即過(guò)濾詞。

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

class TrieNode {
    private Map<Character, TrieNode> children; // 子節(jié)點(diǎn)集合
    private boolean endOfWord; // 標(biāo)識(shí)是否為單詞的結(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;
    }
}

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

初始化前綴樹(shù)

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

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

• 遍歷字符串集合，逐個(gè)插入字符串到前綴樹(shù)中。

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

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

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

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

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

添加敏感詞

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

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

• 遍歷敏感詞的每個(gè)字符。

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

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

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

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

刪除敏感詞

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

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

敏感詞過(guò)濾

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

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

通過(guò)前綴樹(shù)，我們可以高效地找到和替換敏感詞，將其過(guò)濾或標(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; // 單詞不存在于前綴樹(shù)中，無(wú)需刪除
            }
            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; // 單詞不存在于前綴樹(shù)中，無(wú)需刪除
        }

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

        if (shouldDeleteChild) {
            current.getChildren().remove(c); // 刪除當(dāng)前字符對(duì)應(yīng)的子節(jié)點(diǎn)
            return current.getChildren().isEmpty(); // 判斷當(dāng)前節(jié)點(diǎn)是否有其他子節(jié)點(diǎn)
        }

        return false;
    }

    // 敏感詞過(guò)濾
    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)建了一個(gè) TrieFilter 類來(lái)實(shí)現(xiàn)敏感詞過(guò)濾功能。使用 addWord 方法將敏感詞添加到前綴樹(shù)中，然后使用 filter 方法對(duì)文本進(jìn)行過(guò)濾，將匹配到的敏感詞替換為 ***，使用 deleteWord 方法從前綴樹(shù)中刪除敏感詞。

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

最新評(píng)論