前缀树又称为字典树，在搜索提示，分词，httprouter等领域都有广泛使用。其原理就像查字典一样，比如要从字典中查 tea，首先翻到以 t 开头的那几页，然后从那几页里找到第二个字母是 e 的，在此范围内找到第三个字母是 a 并且没有后续字母的单词。
我们可以这样实现一棵前缀树，每个节点都是完整的索引。这样实现起来非常简单，但正如上图可看出的，仅索引4个单词就消耗了大量的空间。这还是纯英文字母的情况，如果是中文，那每个节点几万个字节，可以说是相当浪费了。
为了节省空间，我们可以用链表节点替代上面的数组节点，这样只是额外消耗了一点指针的空间，相比数组节点能省下很多空间。但这样每次进入一个节点就要从头开始一个一个地搜相匹配的字符，然后再跳到下一个节点。是一种时间换空间的操作。
package main
type Trie struct {
id int
exist bool
text string
children map[rune]*Trie
}
type Output struct {
Id int
Text string
}
/* 初始化树 */
func Constructor() Trie {
root := new(Trie)
root.children = make(map[rune]*Trie)
root.exist = false
return *root
}
/* 添加数据 */
func (this *Trie) Insert(word string, id int) {
word_len := len([]rune(word))
i := 1
for _, c := range word {
if this.children[c] == nil {
node := &Trie{}
node.children = make(map[rune]*Trie)
if i == word_len {
node.exist = true
node.id = id
node.text = word
}
this.children[c] = node
}
this = this.children[c]
i++
}
}
/* 完全匹配 */
func (this *Trie) Search(word string) *Output {
ret := &Output{Id: 0, Text: ""}
for _, c := range word {
if this.children[c] == nil {
return nil
}
this = this.children[c]
}
if this.exist == true {
ret = &Output{Id: this.id, Text: this.text}
return ret
}
return nil
}
/* 找最后的内容 */
func recursion(data map[rune]*Trie, rets []*Output) []*Output {
ret := rets
for _, v := range data {
if v.exist == true {
ret = append(ret, &Output{Id: v.id, Text: v.text})
return ret
}
ret = recursion(v.children, ret)
}
return ret
}
/* 前缀匹配 */
func (this *Trie) StartsWith(word string) (ret []*Output) {
cur := this
for _, c := range word {
if cur.children[c] == nil {
return nil
}
cur = cur.children[c]
}
var now_ret *Output
if cur.exist == true {
now_ret = &Output{Id: cur.id, Text: cur.text}
}
if len(cur.children) > 0 {
ret = recursion(cur.children, nil)
}
ret = append(ret, now_ret)
return ret
}
/**
func main() {
obj := Constructor()
obj.Insert("喜欢空气的自由")
obj.Insert("空气的自由")
obj.Insert("自由空气")
param_1 := obj.Search("自由空气")
param_2 := obj.Search("自由")
param_3 := obj.Search("空气的自由")
fmt.Println(param_1, param_2, param_3)
param_4 := obj.StartsWith("空气")
fmt.Println(param_4)
}
*/
网友评论