多模式字元串比對：Trie樹

Trie樹

定義

Trie樹，也叫“字典樹”，是一種樹形結構，專門用來處理字元串比對的資料結構。

Trie樹的本質，利用字元串間的公共字首，将重複的字元合并在一起，形成一個樹形結構，并且給葉子節點打上标記。其中，根節點不包含任何資訊，每個節點表示一個字元串中的一個字元，從根節點到葉子節點的一個路徑，表示一個字元串。

Trie樹是一個多叉樹。

多叉樹存儲 todo

實作

插入字元串

查詢字元串

代碼實作

package main

import (
	"fmt"
)

type TrieNode struct {
	data     interface{}
	isEnding bool
	child    map[rune]*TrieNode
}

func NewTrieNode(data interface{}) *TrieNode {
	return &TrieNode{
		data:     fmt.Sprint(data),
		isEnding: false,
		//child:    make(map[rune]*TrieNode, 26), // 純小寫英文時候
		child:    make(map[rune]*TrieNode),
	}
}

func (this *TrieNode) Insert(s string) bool {
	ss := []rune(s)
	if len(ss) == 0 {
		return false
	}

	for _, index := range ss {
		if this.child[index] == nil {
			node := NewTrieNode(index)
			this.child[index] = node
		}
		this = this.child[index]
	}
	this.isEnding = true
	return true
}

func (this *TrieNode) Find(s string) bool {
	ss := []rune(s)
	l := len(ss)

	if l == 0 {
		return false
	}

	for _, index := range ss {
		if this.child[index] == nil {
			return false
		} else {
			this = this.child[index]
		}
	}
	if this.isEnding {
		return true
	}

	return false
}

func main() {
	root := NewTrieNode("/")
	b := root.Insert("a中國")
	fmt.Println(b)
	fmt.Println(root)
	bb := root.Find("a中國")
	fmt.Println(bb)
	b = root.Insert("b中c")
	fmt.Println(b)
	b = root.Insert("b中國hfjh")
	fmt.Println(b)
	fmt.Println(root)
}
           

時間複雜度

從插入和查找實作代碼分析複雜度很簡單，而且時間複雜度非常高效，一旦建好trie樹以後，查找一個字元串K，僅需要周遊一遍K即可，非常高效。

插入

O(n) n為要插入的字元串長度

查找

O(k) k為模式串字元串長度

優點

從時間複雜度可以看出，非常高效。

缺點

比較耗記憶體，因為每個節點都要維護一個哈希map，比如純英文，長度也許是26個字元就好，如果要是含有中文等，那這個map的長度就會更大，是以，trie樹是以空間換時間的思路。

當然，我們不可否認，Trie 樹盡管有可能很浪費記憶體，但是确實非常高效。那為了解決這個記憶體問題，我們是否有其他辦法呢？我們可以稍微犧牲一點查詢的效率，将每個節點中的數組換成其他資料結構，來存儲一個節點的子節點指針。用哪種資料結構呢？我們的選擇其實有很多，比如有序數組、跳表、散清單、紅黑樹等。假設我們用有序數組，數組中的指針按照所指向的子節點中的字元的大小順序排列。查詢的時候，我們可以通過二分查找的方法，快速查找到某個字元應該比對的子節點的指針。但是，在往 Trie 樹中插入一個字元串的時候，我們為了維護數組中資料的有序性，就會稍微慢了點。替換成其他資料結構的思路是類似的，這裡我就不一一分析了，你可以結合前面學過的内容，自己分析一下。

Trie 樹與散清單、紅黑樹的比較實際上，字元串的比對問題，籠統上講，其實就是資料的查找問題。對于支援動态資料高效操作的資料結構，我們前面已經講過好多了，比如散清單、紅黑樹、跳表等等。實際上，這些資料結構也可以實作在一組字元串中查找字元串的功能。我們選了兩種資料結構，散清單和紅黑樹，跟 Trie 樹比較一下，看看它們各自的優缺點和應用場景。在剛剛講的這個場景，在一組字元串中查找字元串，Trie 樹實際上表現得并不好。它對要處理的字元串有及其嚴苛的要求。第一，字元串中包含的字元集不能太大。我們前面講到，如果字元集太大，那存儲空間可能就會浪費很多。即便可以優化，但也要付出犧牲查詢、插入效率的代價。第二，要求字元串的字首重合比較多，不然空間消耗會變大很多。第三，如果要用 Trie 樹解決問題，那我們就要自己從零開始實作一個 Trie 樹，還要保證沒有 bug，這個在工程上是将簡單問題複雜化，除非必須，一般不建議這樣做。

第四，我們知道，通過指針串起來的資料塊是不連續的，而 Trie 樹中用到了指針，是以，對緩存并不友好，性能上會打個折扣。綜合這幾點，針對在一組字元串中查找字元串的問題，我們在工程中，更傾向于用散清單或者紅黑樹。因為這兩種資料結構，我們都不需要自己去實作，直接利用程式設計語言中提供的現成類庫就行了。講到這裡，你可能要疑惑了，講了半天，我對 Trie 樹一通否定，還讓你用紅黑樹或者散清單，那 Trie 樹是不是就沒用了呢？是不是今天的内容就白學了呢？實際上，Trie 樹隻是不适合精确比對查找，這種問題更适合用散清單或者紅黑樹來解決。Trie 樹比較适合的是查找字首比對的字元串，也就是類似百度的輸入字首後提示補全字元串功能。

應用

Trie 樹的優勢并不在于，用它來做動态集合資料的查找，因為，這個工作完全可以用更加合适的散清單或者紅黑樹來替代。Trie 樹最有優勢的是查找字首比對的字元串，比如搜尋引擎中的關鍵詞提示功能這個場景，就比較适合用它來解決，也是 Trie 樹比較經典的應用場景。