Go 數據結構和算法篇：字符串匹配之 Trie 樹

一、Trie 樹的定義

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

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

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

Trie 樹圖示

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

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

二、如何實現 Trie 樹

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

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

我們將 Trie 樹的每個節點抽象爲一個節點對象，對象包含的屬性有節點字符、子節點字典和是否是字符串結束字符標誌位：

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

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

要構造一棵完整的 Trie 樹，關鍵在於存儲子節點字典的 children 屬性的實現。藉助散列表的思想，我們通過一個下標與字符一一映射的數組，來構造 children：將字符串中每個字符轉化爲 Unicode 編碼作爲字典鍵，將對應節點對象指針作爲字典值，依次插入所有字符串，從而構造出 Trie 樹。對應 Go 實現代碼如下：

// Trie 樹結構
type Trie struct {
    root *trieNode     // 根節點指針
}

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

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

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

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

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

執行上述代碼，打印結果如下：

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

三、Trie 樹的複雜度

構建 Trie 樹的過程比較耗時，對於有 n 個字符的字符串集合而言，需要遍歷所有字符，對應的時間複雜度是 O(n)，但是一旦構建之後，查詢效率很高，如果匹配串的長度是 k，那隻需要匹配 k 次即可，與原來的主串沒有關係，所以對應的時間複雜度是 O(k)，基本上是個常量級的數字。

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

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

四、Trie 樹的應用

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

敏感詞過濾系統

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

搜索框聯想功能

另外，搜索框的查詢關鍵詞聯想功能也是基於 Trie 樹實現的：

Google 搜索框聯想詞

進而可以擴展到瀏覽器網址輸入自動補全、IDE 代碼編輯器自動補全、輸入法自動補全功能等。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/qG1Tn2s3zfCsmaYj94wZmw