一、什么是 Trie樹？

Trie樹，也叫字典樹，它是一個(gè)樹形結(jié)構(gòu)。它是一種專門處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，用來解決在一組字符串集合中快速查找某個(gè)字符串的問題。

Trie樹的本質(zhì)就是利用字符串之間的公共前綴，將重復(fù)的前綴合并在一起。如下圖。

Trie樹的根節(jié)點(diǎn)不存數(shù)據(jù)，每個(gè)節(jié)點(diǎn)表示一個(gè)字符串的字符，從根節(jié)點(diǎn)到紅色節(jié)點(diǎn)一條路徑代表一個(gè)字符串。

二、如何實(shí)現(xiàn)一棵 Trie樹。

1、存儲(chǔ) Trie樹

我們假設(shè)存儲(chǔ)的字符都是a~z，我們可以用一個(gè)數(shù)組大小26來存儲(chǔ)字符，每一層每個(gè)字符都有26個(gè)子節(jié)點(diǎn)，數(shù)組的下標(biāo)為存入下標(biāo)的字符ASCII碼值-a的ASCII碼值，這樣我們可以通過下標(biāo)就可以知道該節(jié)點(diǎn)存儲(chǔ)的是哪個(gè)字符。代碼表示如下：

class TrieNode{
  char data;
  TrieNode children[26];
}

2、將字符串集合構(gòu)造成 Trie 樹

構(gòu)造 Trie樹，相當(dāng)于把每個(gè)字符串插入到Trie樹中。代碼實(shí)現(xiàn)如下：

public class Trie {
    private TrieNode root;

    public Trie() {
        // 樹頂存儲(chǔ)無意義字符
        this.root = new TrieNode('/');
    }

    /**
     * 插入字符串
     *
     * @param text 字符串
     */
    public void insert(char[] text) {
        TrieNode p = root;
        int n = text.length;
        for (int i = 0; i < n; i++) {
            // 字符應(yīng)該存儲(chǔ)的數(shù)組下標(biāo)
            int idx = text[i] - 'a';
            // 該字符在Trie樹中不存在，將該字符插入到Trie樹中
            if (p.children[idx] == null) {
                TrieNode newNode = new TrieNode(text[i]);
                p.children[idx] = newNode;
            }
            // 繼續(xù)存儲(chǔ)下一個(gè)字符
            p = p.children[idx];
        }
        // 存儲(chǔ)完成后，修改結(jié)尾字符標(biāo)識(shí)
        p.isEndingChar = true;
    }
}

class TrieNode {
    public char data;
    public TrieNode[] children;
    public boolean isEndingChar;

    public TrieNode(char data) {
        this.data = data;
        this.children = new TrieNode[26];
        // 是否是字符串結(jié)尾字符
        this.isEndingChar = false;
    }
}

構(gòu)建Trie樹的過程，需要掃描所有的字符串，時(shí)間復(fù)雜度是O(n)，n表示所有字符串的長度和。

3、Tire樹匹配字符串

在 Trie 樹中，查找某個(gè)字符串，用代碼實(shí)現(xiàn)如下：

    /**
     * 在 Trie 樹中查找一個(gè)字符串
     * @param pattern 模式串
     * @return 是否存在
     */
    public boolean find(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; i++) {
            int index = pattern[i] - 'a';
            // 不存在 pattern
            if (p.children[index] == null) {
                return false;
            }
            // 存在繼續(xù)往下找
            p = p.children[index];
        }
        // ture 代表完全匹配，false 代表不能完全匹配，只是前綴
        return p.isEndingChar;
    }

從代碼中可以看出Tire樹的查找字符串，的時(shí)間復(fù)雜度為O(n)，n代表要查找的字符串的長度。如果不考慮構(gòu)建tire樹的操作，查詢字符串，還是比較高效的。

三、Tire 樹的優(yōu)缺點(diǎn)和應(yīng)場景

1、Tire樹是非常耗內(nèi)存的，拿空間換時(shí)間；如果字符串前綴重合不多，會(huì)導(dǎo)致空間消耗變大。
2、字符串包含的字符集不能太大。如果字符集太大，那存儲(chǔ)空間可能會(huì)浪費(fèi)很多。即便可以優(yōu)化，但也要付出犧牲查詢、插入的代價(jià)。
3、如果要用Trie樹解決問題，要從零開始實(shí)現(xiàn)一個(gè)Trie樹，還要保證沒有bug，這個(gè)工程上是將簡單問題復(fù)雜化，除非必須，一般不建議這樣做。
4、Trie樹中用到了指針，因?yàn)橹羔槾饋淼臄?shù)據(jù)塊是不連續(xù)的，所以對緩存并不友好，性能上會(huì)打個(gè)折扣。

綜合以上幾點(diǎn)，針對在一組字符串中查找字符串的問題，用散列表或者紅黑樹比較好。因?yàn)檫@兩種數(shù)據(jù)結(jié)構(gòu)，編程語言中現(xiàn)成類庫都有，不需要自己實(shí)現(xiàn)。

Trie 樹不適合精確匹配查找，它比較適合查找前綴匹配的字符串；比如搜索關(guān)鍵詞的提示功能，我們用代碼實(shí)現(xiàn)如下：

/**
     * 查找匹配前綴所有字符串
     *
     * @param pattern 前綴
     * @return 字符串集合
     */
    public List<String> findPrefix(char[] pattern) {
        TrieNode p = root;
        // 找出前綴的結(jié)尾字符所在節(jié)點(diǎn)
        for (int i = 0; i < pattern.length; i++) {
            int idx = pattern[i] - 'a';
            // 不存在，說明沒有這個(gè)前綴的字符串
            if (p.children[idx] == null) {
                return null;
            }
            p = p.children[idx];
        }
        // 遍歷節(jié)點(diǎn)p，把前綴是pattern都找出來
        List<String> res = new ArrayList<String>();
        iterateTrie(p, String.valueOf(pattern), res);
        return res;
    }

    // 遍歷
    private void iterateTrie(TrieNode node, String str, List<String> res) {
        TrieNode[] children = node.children;
        // 遍歷子節(jié)點(diǎn)
        for (TrieNode child : children) {
            // 如果當(dāng)前子節(jié)點(diǎn)為空，直接跳到下一個(gè)子節(jié)點(diǎn)
            if (child == null) continue;
            // 拼接字符串
            String temp = str + child.data;
            // 如果當(dāng)前子節(jié)點(diǎn)是結(jié)尾字符，把temp添加到res中
            if (child.isEndingChar) {
                res.add(temp);
            }
            // 繼續(xù)往下遞歸
            iterateTrie(child, temp, res);
        }
    }

四、擴(kuò)展—經(jīng)典多模式串匹配算法：AC自動(dòng)機(jī)

網(wǎng)上有很多發(fā)表內(nèi)容的網(wǎng)站，對于用戶輸入一些淫穢、反動(dòng)、謾罵等敏感內(nèi)容，會(huì)對進(jìn)行過濾。
我們現(xiàn)在來學(xué)習(xí)一下，如何實(shí)現(xiàn)一個(gè)高性能的敏感詞過濾系統(tǒng)呢？這里就需要用到多模式串匹配算法。

1、多模式串與單模式串匹配算法的區(qū)別

單模式匹配算法，是在一個(gè)模式串和主串之間進(jìn)行匹配，也就是說，在一個(gè)主串中查找一個(gè)模式串。用單模式串算法來實(shí)現(xiàn)多模式串的匹配，要讓每個(gè)模式串跟主串進(jìn)行匹配，這會(huì)導(dǎo)致主串會(huì)被掃描多次；當(dāng)主串特別長、模式串也很多時(shí)，這種處理就比較低效。

多模式串匹配算法，就是在多個(gè)模式串和一個(gè)主串之間做匹配，也就是上說，在一個(gè)主串中查找多個(gè)模式串。實(shí)現(xiàn)多模式串的匹配，它只需要掃描一遍主串，就能在主串中一次性查找多個(gè)模式串是否存在，大大提高了匹配效率。

2、AC自動(dòng)機(jī)

AC自動(dòng)機(jī)算法，全稱是Aho-Corasick算法；AC自動(dòng)機(jī)借鑒了單模式串的優(yōu)化改進(jìn)方法，對多模式串Trie樹進(jìn)行改進(jìn)，進(jìn)一步提高Trie樹的效率；AC自動(dòng)機(jī)實(shí)際上就是在Trie樹之上，加了類似KMP的next數(shù)組，只不過此處的next數(shù)組是構(gòu)建在樹上而已。 用代碼表示如下：

public class AcNode{
  public char data;
  public AcNode[] children;
  // 失敗指針
  public AcNode fail;
  // 當(dāng)isEndingChar = true，記錄模式串長度
  public int length;
  // 是否是結(jié)尾字符
  public boolean isEndingChar;
  public AcNode(char data){
    this.data = data;
    // 字符集只包含a~z 這26個(gè)字符
    this.children = new AcNode[26];
    this.length = -1;
    this.isEndingChar = false;
  }
}

AC自動(dòng)機(jī)的構(gòu)建包括兩個(gè)操作：
1、將多個(gè)模式串構(gòu)建成Trie樹
代碼實(shí)現(xiàn)如下：

public class AcTire{
  private AcNode root;
  public Tire(){
    // 樹頂存儲(chǔ)無意義
    this.root = new AcNode('/');
  }
  // 字符串插入
  public void insert(char[] text){
    AcNode p = root;
    int n = text.length;
    for(int i = 0; i < n; i++){
      // 當(dāng)前字符的下標(biāo)
      int idx = text[i] - 'a';
      // 在Trie樹中不存在，新增節(jié)點(diǎn)添加到樹中
      if(p.children[idx] == null){
        AcNode newNode = new AcNode(text[i]);
        p.children[idx] = newNode;
      }
      // 繼續(xù)下一個(gè)字符匹配
      p = p.children[idx] 
    }
    // 插入完成，記錄結(jié)尾字符下標(biāo)和字符串長度
    p.isEndingChar = true;
    p.length = n;
  } 
}

2、在Trie樹上構(gòu)建失敗指針（相當(dāng)于KMP中的失效函數(shù)next數(shù)組）

這個(gè)失敗指針的作用是什么？比如一個(gè)主串為：abce; 模式串為：abcd，bcd，bc，c；我們把主串字符匹配，發(fā)現(xiàn)匹配到第一個(gè)模式串a(chǎn)bcd的最后一個(gè)字符匹配失敗了，此時(shí)我們知道abcd模式串已經(jīng)匹配不上了；為了提高效率，我們把已經(jīng)能匹配上的字符串，跟其它其它模式串能不能匹配上；這時(shí)我知道abc是已經(jīng)匹配上的字符串，我們把a(bǔ)bc的后綴（bc、c）去跟其它模式串匹配，可以匹配到模式串bc和c；這時(shí)我們可以取最長可匹配后綴子串 bc 就可以了（因?yàn)閏已經(jīng)包含在bc中了，如果bc沒有匹配上，那么就取c），那么字符串a(chǎn)bc中的節(jié)點(diǎn)c的失敗指針指向模式串 bc。如下圖

通過上面的分析，主串匹配模式串，關(guān)鍵就是找到模式串每個(gè)節(jié)點(diǎn)的失敗指針；

現(xiàn)在我們來構(gòu)建Trie樹的失敗指針，這個(gè)過程跟KMP算法中next數(shù)組的構(gòu)建過程很相似，我們假設(shè)節(jié)點(diǎn)p的失敗指針指向節(jié)點(diǎn) q，我們看節(jié)點(diǎn)p的子節(jié)點(diǎn)pc對應(yīng)的字符，是否也可以在節(jié)點(diǎn)q的子節(jié)點(diǎn)找到。如果找到了節(jié)點(diǎn) q 的子節(jié)點(diǎn) qc，對應(yīng)字符跟節(jié)點(diǎn) pc 對應(yīng)的字符相同 ，則將節(jié)點(diǎn)pc的失敗指針指向節(jié)點(diǎn)qc；如果沒有找到，我們再找q的失敗指針子節(jié)點(diǎn)的字符跟節(jié)點(diǎn) pc 對應(yīng)的字符相同；就這樣繼續(xù)下去，如果都沒有找到，我們就把pc節(jié)點(diǎn)的失敗節(jié)點(diǎn)指向根節(jié)點(diǎn)；根節(jié)點(diǎn)的失敗指針對應(yīng)為 null； 如下圖

整個(gè)實(shí)現(xiàn)代碼如下：

 // 構(gòu)建失敗指針
    public void getFail() {
        // 使用隊(duì)列來遍歷每個(gè)節(jié)點(diǎn)
        Queue<AcNode> queue = new LinkedList<>();
        root.fail = null;
        queue.add(root);
        while (!queue.isEmpty()) {
            AcNode p = queue.remove();
            for (AcNode child : p.children) {
                // 當(dāng)前子節(jié)點(diǎn)為空，直接跳到下一個(gè)子節(jié)點(diǎn)；
                if (child == null) continue;
                // 父節(jié)點(diǎn)是根節(jié)點(diǎn)
                if (p == root) {
                    child.fail = root;
                } else {
                    // 比較child字符
                    int idx = child.data - 'a';
                    AcNode pFail = p.fail;
                    while (pFail != null) {
                        // 如果相等
                        if (pFail.children[idx] != null) {
                            child.fail = pFail.children[idx];
                            break;
                        }
                        pFail = pFail.fail;
                    }
                    // 如果沒找到
                    if (pFail == null) {
                        child.fail = root;
                    }
                }
                // 將子節(jié)點(diǎn)加入到隊(duì)列中
                queue.add(child);
            }
        }
    }

// 匹配字符串
public void match(char[] text){
  
}