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

一、Trie 樹(shù)的定義

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

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

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

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

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

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

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

Trie 樹(shù)是個(gè)多叉樹(shù)，二叉樹(shù)中，一個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)是通過(guò)兩個(gè)指針來(lái)存儲(chǔ)的，對(duì)于多叉樹(shù)來(lái)說(shuō)，我們?cè)趺创鎯?chǔ)一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)的指針呢？

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

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

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

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

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

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

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

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

最后，我們可以編寫一段簡(jiǎn)單的 Trie 樹(shù)測(cè)試代碼：

func main() {
    trie := NewTrie()
    words := []string{"Golang", "學(xué)院君", "Language", "Trie", "Go"}
    // 構(gòu)建 Trie 樹(shù)
    for _, word := range words {
        trie.Insert(word)
    }
    // 從 Trie 樹(shù)中查找字符串
    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 代碼倉(cāng)庫(kù)獲取。

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

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

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

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

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

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

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

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

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

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

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