一、簡介

Trie 樹也稱為字典樹、單詞查找樹，最大的特點就是共享字符串的公共前綴來達到節省空間的目的。

例如，字符串 "abc" 和 "abd" 構成的 trie 樹如下：

在這里插入圖片描述

字典樹的根節點不存任何數據，每整個分支代表一個完整的字符串。像 abc 和 abd 有公共前綴 ab，所以我們可以共享節點 ab。

如果再插入 abf，則變成這樣：

在這里插入圖片描述

如果我再插入 bc，則是這樣(bc 和其他三個字符串沒有公共前綴)

在這里插入圖片描述

那如果再插入 "ab" 這個字符串呢？

每個分支的內部可能也含有完整的字符串，所以我們可以對于那些是某個字符串結尾的節點做一個標記，例如 abc，abd，abf 都包含了字符串 ab，所以我們可以在節點 b 這里做一個標記。如下(我用紅色作為標記)：

在這里插入圖片描述

二、應用

2.1 提前列出搜索信息

字典樹最大的特點就是利用了字符串的公共前綴，像我們有時候在百度、谷歌輸入某個關鍵字的時候，它會給我們列舉出很多相關的信息。

在這里插入圖片描述

2.2 敏感詞過濾

例：一段字符串 “abcdefghi" ，以及三個敏感詞 "de" ，"bca" ，"bcf" 。

先把三個敏感詞建立一顆字典樹，如下：

在這里插入圖片描述

接著可以采用三個指針來遍歷。

首先指針 p1 指向 root ，指針 p2 和 p3 指向字符串第一個字符。

在這里插入圖片描述

然后從字符串的 a 開始，檢測有沒有以 a 作為前綴的敏感詞，直接判斷 p1 的孩子節點中是否有 a 這個節點就可以了，顯然這里沒有。

接著把指針 p2 和 p3 向右移動一格。

在這里插入圖片描述

然后從字符串 b 開始查找，看看是否有以 b 作為前綴的字符串，p1 的孩子節點中有 b，這時，我們把 p1 指向節點 b ，p2 向右移動一格，不過，p3 不動。

在這里插入圖片描述

判斷 p1 的孩子節點中是否存在 p2 指向的字符 c ，顯然有。我們把 p1 指向節點 c ，p2 向右移動一格，p3 不動。

在這里插入圖片描述

判斷 p1 的孩子節點中是否存在 p2 指向的字符 d ，這里沒有。這意味著，不存在以字符 b 作為前綴的敏感詞。這時我們把 p2 和 p3 都移向字符 c ，p1 還是還原到最開始指向 root 。

在這里插入圖片描述

和前面的步驟一樣，判斷有沒以 c 作為前綴的字符串，顯然這里沒有，所以把 p2 和 p3 移到字符 d 。

在這里插入圖片描述

然后從字符串 d 開始查找，看看是否有以 d 作為前綴的字符串，p1 的孩子節點中有 d ，這時，我們把 p1 指向節點 b ，p2 向右移動一格，不過，p3 和剛才一樣不動。

在這里插入圖片描述

判斷 p1 的孩子節點中是否存在 p2 指向的字符 e ，顯然有。我們把 p1 指向節點 e ，并且，這里 e 是最后一個節點了，查找結束，所以存在敏感詞 de ，即 p3 和 p2 這個區間指向的就是敏感詞了，把 p2 和 p3 指向的區間那些字符替換成 * 。并且把 p2 和 p3 移向字符 f 。如下：

在這里插入圖片描述

接著還是重復同樣的步驟，直到 p3 指向最后一個字符。

復雜度分析

如果敏感詞的長度為 m，則每個敏感詞的查找時間復雜度是 O(m)，字符串的長度為 n，我們需要遍歷 n 遍，所以敏感詞查找這個過程的時間復雜度是 O(n * m)。如果有 t 個敏感詞的話，構建字典樹的時間復雜度是 O(t * m)。

這里我說明一下，在實際的應用中，構建字典樹的時間復雜度我覺得可以忽略，因為字典樹我們可以在一開始就構建了，以后可以無數次重復利用。

字典樹可以采用 HashMap 來實現，因為一個節點的字節點個數未知，采用 HashMap 可以動態拓展，而且可以在 O(1) 復雜度內判斷某個子節點是否存在。

三、敏感詞過濾代碼實現

3.1 字典樹結點

public class TrieNode { // 是否敏感詞的結尾 private boolean isEnd = false; // 下一層節點 Map<Character, TrieNode> subNodes = new HashMap<>(); /** * 添加下一個敏感詞節點 */ public void addSubNode(Character c, TrieNode node) { subNodes.put(c, node); } /** * 獲取下一個敏感詞節點 */ public TrieNode getSubNode(Character c) { return subNodes.get(c); } /** * 設置敏感詞標識 */ public void setEnd(boolean end) { this.isEnd = end; } /** * 判斷是否為敏感詞的結尾 */ public boolean getIsEnd() { return this.isEnd; }}

3.2 構建字典樹

public class TireTree { // 敏感詞替換字符 private static final String DEFAULT_REPLACEMENT = "*"; // 根節點 private final TrieNode rootNode; public TireTree() { rootNode = new TrieNode(); } /** * 識別特殊符號 */ private boolean isSymbol(Character c) { int ic = (int) c; // 0x2E80-0x9FFF 東亞文字范圍 return !CharUtils.isAsciiAlphanumeric(c) && (ic < 0x2E80 || ic > 0x9FFF); } /** * 將敏感詞添加到字典樹中 */ public void addWord(String text) { if (text == null || text.trim().equals("")) return; TrieNode curNode = rootNode; int length = text.length(); // 遍歷每個字 for (int i = 0; i < length; ++i) { Character c = text.charAt(i); // 過濾特殊字符 if (isSymbol(c)) continue; TrieNode nextNode = curNode.getSubNode(c); // 第一次添加的節點 if (nextNode == null) { nextNode = new TrieNode(); curNode.addSubNode(c, nextNode); } curNode = nextNode; // 設置敏感詞標識 if (i == length - 1) curNode.setEnd(true); } } /** * 過濾敏感詞 */ public String filter(String text) { if (text == null || text.trim().equals("")) return text; StringBuilder result = new StringBuilder(); TrieNode curNode = rootNode; int begin = 0; // 回滾位置 int position = 0; // 當前位置 while (position < text.length()) { Character c = text.charAt(position); // 過濾空格等 if (isSymbol(c)) { if (curNode == rootNode) { result.append(c); ++begin; } ++position; continue; } curNode = curNode.getSubNode(c); // 當前位置的匹配結束 if (curNode == null) { // 以begin開始的字符串不存在敏感詞 result.append(text.charAt(begin)); // 跳到下一個字符開始測試 position = begin + 1; begin = position; // 回到樹初始節點,重新匹配 curNode = rootNode; } else if (curNode.getIsEnd()) { // 發現敏感詞，從begin到position的位置用replacement替換掉 result.append(DEFAULT_REPLACEMENT); position = position + 1; begin = position; // 回到樹初始節點，重新匹配 curNode = rootNode; } else { ++position; } } result.append(text.substring(begin)); return result.toString(); }}

3.3 測試

class Test { public static void main(String[] args) { TireTree tree = new TireTree(); // 添加敏感詞 tree.addWord("de"); tree.addWord("bca"); tree.addWord("bcf"); // 過濾敏感詞 String res = tree.filter("abcdefghi"); System.out.println(res); // abc*fghi }}

總結

以上是生活随笔為你收集整理的字典树实现_反怼面试官系列之 字典树的全部內容，希望文章能夠幫你解決所遇到的問題。

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