Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（十三）：字符串匹配之 Trie 樹

一、Trie 樹的定義

Trie 樹，也叫「前綴樹」或「字典樹」，顧名思義，它是一個樹形結(jié)構(gòu)，專門用于處理字符串匹配，用來解決在一組字符串集合中快速查找某個字符串的問題。

注：Trie 這個術(shù)語來自于單詞「retrieval」，你可以把它讀作 tree，也可以讀作 try。

Trie 樹的本質(zhì)，就是利用字符串之間的公共前綴，將重復(fù)的前綴合并在一起，比如我們有["hello","her","hi","how","see","so"] 這個字符串集合，可以將其構(gòu)建成下面這棵 Trie 樹：

每個節(jié)點表示一個字符串中的字符，從根節(jié)點到紅色節(jié)點的一條路徑表示一個字符串（紅色節(jié)點表示是某個單詞的結(jié)束字符，但不一定都是葉子節(jié)點）。

這樣，我們就可以通過遍歷這棵樹來檢索是否存在待匹配的字符串了，比如我們要在這棵 Trie 樹中查詢 her，只需從 h 開始，依次往下匹配，在子節(jié)點中找到 e，然后繼續(xù)匹配子節(jié)點，在 e 的子節(jié)點中找到 r，則表示匹配成功，否則匹配失敗。通常，我們可以通過 Trie 樹來構(gòu)建敏感詞或關(guān)鍵詞匹配系統(tǒng)。

二、如何實現(xiàn) Trie 樹

從剛剛 Trie 樹的介紹來看，Trie 樹主要有兩個操作，一個是將字符串集合構(gòu)造成 Trie 樹。這個過程分解開來的話，就是一個將字符串插入到 Trie 樹的過程。另一個是在 Trie 樹中查詢一個字符串。

Trie 樹是個多叉樹，二叉樹中，一個節(jié)點的左右子節(jié)點是通過兩個指針來存儲的，對于多叉樹來說，我們怎么存儲一個節(jié)點的所有子節(jié)點的指針呢？

我們將 Trie 樹的每個節(jié)點抽象為一個節(jié)點對象，對象包含的屬性有節(jié)點字符、子節(jié)點字典和是否是字符串結(jié)束字符標(biāo)志位：

// Trie 樹節(jié)點
type trieNode struct {
    char string                    // Unicode 字符
    isEnding bool                  // 是否是單詞結(jié)尾
    children map[rune]*trieNode    // 該節(jié)點的子節(jié)點字典
}

// 初始化 Trie 樹節(jié)點
func NewTrieNode(char string) *trieNode  {
    return &trieNode{
        char: char,
        isEnding: false,
        children: make(map[rune]*trieNode),
    }
}

要構(gòu)造一棵完整的 Trie 樹，關(guān)鍵在于存儲子節(jié)點字典的 children 屬性的實現(xiàn)。借助散列表的思想，我們通過一個下標(biāo)與字符一一映射的數(shù)組，來構(gòu)造 children：將字符串中每個字符轉(zhuǎn)化為 Unicode 編碼作為字典鍵，將對應(yīng)節(jié)點對象指針作為字典值，依次插入所有字符串，從而構(gòu)造出 Trie 樹。對應(yīng) Go 實現(xiàn)代碼如下：

// Trie 樹結(jié)構(gòu)
type Trie struct {
    root *trieNode     // 根節(jié)點指針
}

// 初始化 Trie 樹
func NewTrie() *Trie {
    // 初始化根節(jié)點
    trieNode := NewTrieNode("/")
    return &Trie{trieNode}
}

// 往 Trie 樹中插入一個單詞
func (t *Trie) Insert(word string) {
    node := t.root   // 獲取根節(jié)點
    for _, code := range word {  // 以 Unicode 字符遍歷該單詞
        value, ok := node.children[code]  // 獲取 code 編碼對應(yīng)子節(jié)點
        if !ok {
            // 不存在則初始化該節(jié)點
            value = NewTrieNode(string(code))
            // 然后將其添加到子節(jié)點字典
            node.children[code] = value
        }
        // 當(dāng)前節(jié)點指針指向當(dāng)前子節(jié)點
        node = value
    }
    node.isEnding = true  // 一個單詞遍歷完所有字符后將結(jié)尾字符打上標(biāo)記
}

// 在 Trie 樹中查找一個單詞
func (t *Trie) Find(word string) bool {
    node := t.root
    for _, code := range word {
        value, ok := node.children[code] // 獲取對應(yīng)子節(jié)點
        if !ok {
            // 不存在則直接返回
            return false
        }
        // 否則繼續(xù)往后遍歷
        node = value
    }
    if node.isEnding == false {
        return false // 不能完全匹配，只是前綴
    }
    return true // 找到對應(yīng)單詞
}

最后，我們可以編寫一段簡單的 Trie 樹測試代碼：

func main() {
    trie := NewTrie()
    words := []string{"Golang", "學(xué)院君", "Language", "Trie", "Go"}
    // 構(gòu)建 Trie 樹
    for _, word := range words {
        trie.Insert(word)
    }
    // 從 Trie 樹中查找字符串
    term := "學(xué)院君"
    if trie.Find(term) {
        fmt.Printf("包含單詞\"%s\"\n", term)
    } else {
        fmt.Printf("不包含單詞\"%s\"\n", term)
    }
}

執(zhí)行上述代碼，打印結(jié)果如下：

完整代碼可以從 https://github.com/nonfu/golang-tutorial 代碼倉庫獲取。

三、Trie 樹的復(fù)雜度

構(gòu)建 Trie 樹的過程比較耗時，對于有 n 個字符的字符串集合而言，需要遍歷所有字符，對應(yīng)的時間復(fù)雜度是 O(n)，但是一旦構(gòu)建之后，查詢效率很高，如果匹配串的長度是 k，那只需要匹配 k 次即可，與原來的主串沒有關(guān)系，所以對應(yīng)的時間復(fù)雜度是 O(k)，基本上是個常量級的數(shù)字。

Trie 樹顯然也是一種空間換時間的做法，構(gòu)建 Trie 樹的過程需要額外的存儲空間存儲 Trie 樹，而且這個額外的空間是原來的數(shù)倍。

你會發(fā)現(xiàn)，通過 Trie 樹進(jìn)行字符串匹配和之前介紹的 BF 算法和 KMP 算法有所不同，BF 算法和 KMP 算法都是在給定主串中匹配單個模式串，而 Trie 樹是將多個模式串與單個主串進(jìn)行匹配，因此，我們將 BF 和 KMP 這種匹配算法叫做單模式匹配算法，而將 Trie 樹這種匹配算法叫做多模式匹配算法。

四、Trie 樹的應(yīng)用

Trie 樹適用于那些查找前綴匹配的字符串，比如敏感詞過濾和搜索框聯(lián)想功能。

敏感詞過濾系統(tǒng)

2016 年新廣告法推出后，學(xué)院君為之前的公司商品庫做過一個簡單的敏感詞過濾系統(tǒng)，就用到了 Trie 樹來對敏感詞進(jìn)行搜索匹配：首先運營在后臺手動更新敏感詞，底層通過 Tire 樹構(gòu)建敏感詞庫，然后當(dāng)商家發(fā)布商品時，以商品標(biāo)題+詳情作為主串，將敏感詞庫作為模式串，進(jìn)行匹配，如果模式串和主串有匹配字符，則以此為起點，繼續(xù)往后匹配，直到匹配出完整字符串，然后標(biāo)記為匹配出該敏感詞（如果想嗅探所有敏感詞，繼續(xù)往后匹配），否則將主串匹配起點位置往后移，從下一個字符開始，繼續(xù)與模式串匹配。

搜索框聯(lián)想功能

另外，搜索框的查詢關(guān)鍵詞聯(lián)想功能也是基于 Trie 樹實現(xiàn)的：

進(jìn)而可以擴(kuò)展到瀏覽器網(wǎng)址輸入自動補(bǔ)全、IDE 代碼編輯器自動補(bǔ)全、輸入法自動補(bǔ)全功能等。