golang-- 字典树_golang 字典树

一.前言
看了百度团队在 infoq 上发表的一篇【如何在秒级完成词表匹配】(https://xie.infoq.cn/article/97b2df7e41456335627ce4cd4)的文章，文章业务背景介绍的很清楚，里面有提到字典树，看到结构图我能明白工作原理，但是总感觉自己处于一种懂与不懂的半懂状态，希望通过写这篇文章我能彻底将字典树闹明白。

二.介绍
概念

字典树是一个存储字符串的树，一个节点的最大子节点数等于字母表的大小。支持在 O(L)时间内的搜索，插入和删除操作，L 是键的长度。

应用场景

1.可以在 O(L)时间内插入和查找字符串，其中 L 表示单个单词的长度。

2.可以轻松地按字母顺序打印所有单词。

3.可以使用字典树完成前缀搜索，这也是字典书叫前缀树的原因之一。

字典树样式

拥有字段：

（图有些问题，讲 i 视作右边最后一个节点）

b|bcd|abc|abd|abcd|efg|hi

总结

根据字典树特性，我们可以发现在敏感词场景中用字典树确实是一个很合理的选择，它采用空间换时间，保证用户可以在极短时间内获取字符串是否安全的结论，具体流程如下图所示：

针对百度的图，有以下两种情况

1.china，由于二级没有任何匹配的节点，所以安全

2.abd，在左边，有 abd 到有效节点 d，所以属于不安全

三.实现
了解了字典树的应用和特性，我们下一步要做的就是字典树的实现了,以下是我按照个人理解实现的源码，如有疑问欢迎沟通

3.1 字典树实现

type Trie struct {
   
	valid      bool                //判断是否是有效节点
	value      interface{
   }         //节点的值
	childMap   map[interface{
   }]int //子节点下是否有这个节点的map记录
	childNodes []*Trie             //包含的所有节点
}

func NewTrie() *Trie {
   
	t := &Trie{
   }
	return t
}
//新增数据时间复杂度是O(L),L是新增字符串的长度
func (this *Trie) AddWord(word []byte) {
   
	if len(word) < 1 {
   
		return
	}
	length := len(word)
	if this.childNodes == nil {
   
		//不存在子级，需要重新创建
		this.childNodes = append(this.childNodes, &Trie{
   
			valid:      length == 1,
			value:      word[0],
			childNodes: nil,
		})
		this.childMap = make(map[interface{
   }]int)
		this.childMap[word[0]] = 1
		this.childNodes[0].AddWord(word[1:])
	} else {
   
		index := this.childMap[word[0]]
		if index > 0 {
   
			//子级里面以及有这个值了
			if len(word) == 1 && this.childNodes[index-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43