索引引擎通常需要統計詞頻，根據前綴給出搜索建議等。字典樹 Trie Tree 就是一個典型的記錄詞頻和前綴的數據結構。
字典樹 Trie Tree字典樹，又稱前綴樹，通常用於詞頻統計、前綴統計、去重、排序等。
如圖所示：
圖中表示一棵 TrieTree，每個節點中的數字表示以該節點結尾的單詞的頻率，例如 go 單詞出現了4次。
而路徑表示組成單詞的每個字符，例如本圖例中表示：go、han、hank、java、jac、jack 幾個單詞的出現次數。
本結構即可統計詞頻。若需要統計前綴數量，在節點增加前綴計數器即可。
整體說，字典樹的特點如下：
路徑表示詞的組成
節點記錄需要統計的信息，例如詞頻和前綴量
根節點不記錄任何信息
任何節點的子節點路徑均不相同
以上結構在查詢單詞或前綴時效率很高，同時還可以記錄單詞的屬性，本例中就是頻率。
編碼Go 1// 字典樹
2type TrieTree struct {
3 Root *TrieNode
4}
5
6func NewTrieTree() *TrieTree {
7 return &TrieTree{
8 Root: NewTrieNode(),
9 }
10}
11
12// 字典樹節點
13type TrieNode struct {
14 Count int // 以當前節點為單詞結尾的數量
15 PrefixCount int // 以當前節點為單詞前綴的數量
16 childNodes map[rune]*TrieNode // 子節點
17}
18
19func NewTrieNode() *TrieNode {
20 return &TrieNode{
21 Count: 0,
22 PrefixCount: 0,
23 childNodes: map[rune]*TrieNode{},
24 }
25}
26
27// 插入單詞
28func (tt *TrieTree) Insert(word string) {
29 if len(word) == 0 {
30 return
31 }
32 node := tt.Root
33 // 遍歷單詞的每個字符
34 for _, c := range strings.ToLower(word) {
35 // 若節點不存在，創建
36 if _, exists := node.childNodes[c]; !exists {
37 node.childNodes[c] = NewTrieNode()
38 }
39 // 繼續
40 node = node.childNodes[c]
41 // 累加前綴數量
42 node.PrefixCount++
43 }
44 // 累加結尾數量
45 node.Count++
46}
47
48// 查詢單詞次數
49func (tt *TrieTree) Search(word string) int {
50 if 0 == len(word) {
51 return 0
52 }
53 node := tt.Root
54 for _, c := range strings.ToLower(word) {
55 if _, exists := node.childNodes[c]; !exists {
56 return 0
57 }
58 node = node.childNodes[c]
59 }
60 return node.Count
61}
62// 查詢前綴次數
63func (tt *TrieTree) Prefix(word string) int {
64 if 0 == len(word) {
65 return 0
66 }
67 node := tt.Root
68 for _, c := range strings.ToLower(word) {
69 if _, exists := node.childNodes[c]; !exists {
70 return 0
71 }
72 node = node.childNodes[c]
73 }
74 return node.PrefixCount
75}
76
77// 測試
78func main() {
79 tt := NewTrieTree()
80 tt.Insert("Hank")
81 tt.Insert("hank")
82 tt.Insert("hanker")
83 tt.Insert("hanken")
84 fmt.Println(tt.Search("hank")) // 2
85 fmt.Println(tt.Prefix("hank")) // 4
86}