Trie（字典樹），正如它的名字一樣，其主要的作用就是來存儲字符串的，用它來實現字符串的查找效率比較高，查找的時間復雜度主要和它的元素（字符串的長度）O(W)相關，但是消耗的內存也比較大。
字典樹主要應用于：

• 字符串的檢索
• 詞頻統計
• 字符串的排序

利用Trie實現敏感詞過濾器主要有下面三個步驟：

• 定義前綴樹
• 根據敏感詞，初始化前綴樹
• 編寫過濾敏感詞的算法

定義和初始化前綴樹

• 根節點沒有字符
• 除了根節點每個節點都只有一個字符
• 每個節點所有的子節點的字符都不相同

字符串的每個字符作為一個Node節點，Node’節點主要有兩部分組成
1.是否為單詞（boolean isKeyWordEnd）
2.節點所有的子節點，用map來保存 key是字符，value 是子節點

//定義前綴樹private class TrieNode {//表示是否為關鍵詞的結尾private boolean isKeyWordEnd = false;//子節點private Map<Character, TrieNode> subNodes = new HashMap<>();//判斷是否是關鍵詞的結尾public boolean isKeyWordEnd() {return isKeyWordEnd;}//設置關鍵詞的結尾為truepublic void setKeyWordEnd(boolean isKeyWordEnd) {this.isKeyWordEnd = isKeyWordEnd;}//添加子節點public void addSubNode(Character c, TrieNode node) {subNodes.put(c, node);}//獲取子節點public TrieNode getSubNode(Character c) {return subNodes.get(c);}}

根據敏感詞，初始化前綴樹

//將一個敏感詞添加到前綴樹中private void addKeyWord(String keyword) {TrieNode temp = rootNode;for (int i = 0; i < keyword.length(); i++) {char c = keyword.charAt(i);TrieNode subNode = temp.getSubNode(c);//如果子節點中不存在該字符節點if (subNode == null) {subNode = new TrieNode();temp.addSubNode(c, subNode);}//指向下一個節點，進行下一個循環temp = subNode;//如果遍歷到字符結束的位置，就要設置節點的字符結束標志位為trueif (i == keyword.length() - 1) {temp.setKeyWordEnd(true);}}}

例如把單詞abc插入到前綴樹中，如果用戶輸入ab，盡管abc包含了ab，但是trie中仍然不包含ab這個單詞，所以插入到單詞的最后一個位置時，需要設置當前最后一個節點的結束標志位為true，代表這是一個完整的敏感詞。

敏感詞過濾算法的實現

設置三個指針
指針1：初始時指向前綴樹的root根節點
指針2：初始時指向待過濾字符的頭結點，表示敏感詞的開頭
指針3：初始時指向待過濾字符的頭結點，表示敏感詞的末尾
利用StringBuilder接收返回值

在指針1所指向節點的子節點中尋找是否出現指針3所指向的字符，如果沒有指針2和指針3進入下一個位置，并將滑過的值添加到stringbuilder中。

當指針1之指向的節點的子節點中能找到指針3指向的值時，指針1指向對應的子節點，指針2在原位置不動（疑似敏感詞的開頭位置）

指針3繼續步進，此時在指針1對應的子節點中找不動指針3的值f！=c，指針3就要回到指針2的下一個節點，指針1需要回到根節點，繼續尋找以b開頭的字符是不是敏感詞。

指針3繼續步進，并與指針1指向的節點的自己點的值比對，當兩者都指向字符’f’的時候，判斷節點f的敏感詞標志位是否為true，如果為true表示找到一個敏感詞，并將其替換為‘***’添加到stringbuilder中，隨后指針2指向指針3的下一個位置即a，指針1重回root，繼續進行過濾。

//敏感詞過濾算法的實現public String filter(String text){if(StringUtils.isBlank(text)){return null;}//指針1TrieNode tempNode=rootNode;//指針2 指向字符的開頭int begin=0;//指針3 指向疑似敏感字符的結尾int position=0;//結果StringBuilder sb=new StringBuilder();while(begin<text.length()) {char c = text.charAt(position);//跳過符號if (isSymbol(c)) {//如果指針1處于根節點，將此符號計入結果，讓指針2向下走一步if (tempNode==rootNode) {sb.append(c);begin++;}//無論符號在開頭還是中間，指針3都向下走一步position++;continue;}//檢查下級節點tempNode=tempNode.getSubNode(c);if (tempNode==null){//以begin開頭的字符串不是敏感詞sb.append(text.charAt(begin));//進入下一個位置position=++begin;//重新指向根節點tempNode=rootNode;}else if (tempNode.isKeyWordEnd()){//發現敏感詞，將begin-position字符串替換點sb.append(REPLACEMENT);//進入下一個位置begin=++position;//重新指向根節點tempNode=rootNode;}else{//檢查下一個字符if (position<text.length()-1){position++;}}}sb.append(text.substring(begin));return sb.toString();}

測試：

@Testpublic void testSensitiveFilter(){String text="這里可以賭博，可以嫖娼，可以吸毒，可以開票";text=sensitiveFilter.filter(text);System.out.println(text);text="這里可以🀁賭博，可以🀂嫖娼，可以🀂🀂🀂吸毒，可以開🀃🀃🀃票";text=sensitiveFilter.filter(text);System.out.println(text);}

結果：

總結

以上是生活随笔為你收集整理的利用Trie(字典树)实现敏感词过滤算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。