Go:实现字典树(搜索引擎)

2022-07-26 22:03
15
0
添加收藏
Go:实现字典树(搜索引擎)
 

在做一个小项目,需要做文本搜索。最初的想法是使用elastic serach。然而,安装和管理elastic serach对于一个少于1000行代码的项目来说似乎有点大材小用。

 

 

我想要的只是一个可以搜索大约500万个单词的小型嵌入式库。该库具有以下特点: 1、足够快 2、支持全文搜索 3、具有自动补全功能 4、缓存结果 5、内存高效 尝试使用Bleve搜索,但最终放弃了,因为当索引数据时,它占用很多内存。最后,只能自己实现一个简单的文本搜索库,因此决定使用Golang来实现字典树。

 

 

假设

 

 

1、仅存储小写字母 2、字典树用于索引和搜索数据

 

 

字典树工作原理

 

 

它是一种树形数据结构,其中节点的所有子节点都有一个共同的前缀。这意味着cat和can共享ca的前缀。查找数据非常快。最坏的情况是O(m)时间(其中m是搜索字符串的长度)。

 

 

字典树中的每个字符都可以用一个节点来表示。在我们的例子中,每个节点最多有26个子节点(a-z),因为我们只存储小写字母。 看下面的图以来解释下:

 

 

从根节点开始,根节点永远是查询的第一个节点。如您所见,根节点有26个子节点(a-z)。节点a是根节点的子节点,它也有26个子节点,从a到z。我们将添加到字典树的所有节点都有26个子节点。

 

 

以cat这个单词为例,如何在树中表示:

 

 

从黑色节点索引或搜索单词cat,我们只需要访问4个节点。分别是根节点....然后是根节点的字节点c及其字节点a,最后是子节点a的子节点t。如果还有cats的话,将扩展节点t包含26个子节点即a到z,查询t的子节点是s。

 

 

不断搜索字典树,直到完成所有要查询的单词。注意:即使字典里有10亿个单词,我们也只需要4步就能找到cat这个单词。

 

 

而且你会发现,大多数单词共享一条路径。例如,car和cat共享节点c和节点a,如下所示:

 

 

创建节点node

 

 

1、字典树的第一个节点是根节点,不包含任何字母可以为null。 2、每个节点(包括本例中的根节点)都应该有26个子节点。 下面来实现代码:

 

 

//Node 表示每个字符
type Node struct {

Char string //这是一个字母用于存储类似a,b,c,d等字母
Children [26]*Node //存储本节点等所有字节点a到z
}

//NewNode 初始化一个新的节点,包含26个子节点
func NewNode(char string) *Node {
node := &Node{Char: char}
for i := 0; i < 26; i++ {
node.Children[i] = nil
}
return node
}

 

 

创建字典树

 

 

1、字典树包含一个根节点,用于搜索任何字符串的起始点。

 

 

//Trie 包含所有节点的树, 根节点为nil
type Trie struct {
RootNode *Node
}

//NewTrie 创建字典树
func NewTrie() *Trie {
root := NewNode("\000") //根节点可以存任意内容
return &Trie{RootNode: root}
}

 

 

索引数据

 

 

索引数据意味着用实际字符替换nil节点。 例如,假设正在索引单词cat。我们要做的是从根节点开始。然后开始遍历树,试图找到合适的节点来放置字符c。如果我们已经到达树的末端,但还没有完成对整个单词的索引,我们只需要创建一个新节点。

 

 

例如,字典树目前只包含根节点和26个子节点,它们的值都为nil。

 

 

对于每个节点的子节点,索引0将映射到字符a,索引1将映射到字符b,索引2将映射到字符c,以此类推。

 

 

这意味着在根节点的下标为2处,我们应该插入c,然后创建另一个子节点c,并将a放在该节点的下标0处。一直这样做,直到cat所有的字符都被索引。注意,如果一个节点已经存在,则移动到下一个字符。

 

 

//Insert 插入单词到字典树
func (t *Trie)Insert(word string) error {
//查询当前节点,从树到根节点开始
current := t.RootNode
//去除单词中到空格
strippedWord := strings.ToLower(strings.ReplaceAll(word, " ", ))
for i := 0; i < len(strippedWord); i++{
//根据ASCII表97代表字符a,将字符转为整数索引值
index := strippedWord[i] - 'a'
//查看当前字符是否存在,
if current.Children[index] == nil { //如果不存在
current.Children[index] = NewNode(string(strippedWord[i]))
}
current = current.Children[index]
//支持自动补全
}
return nil
}

 

 

代码index:= stripedword [i] - ' a '用来获得一个字符的索引。就是从ascii表中取一个字符的十进制表示,然后减去a(97)的十进制表示。例如,c-a会被翻译成(99-97)=2,这是c的索引。

 

 

搜索单词

 

 

搜索单词的函数与索引类似,以同样的方式遍历这棵树:

 

 

//SearchWord 如果单词搜索不到返回false,否则返回true
func (t *Trie)SearchWord(word string) bool {
strippedWord := strings.ToLower(strings.ReplaceAll(word, , ))
current := t.RootNode
for i := 0; i < len(strippedWord); i++{
index := strippedWord[i] -
//搜索到nil节点,说明已经搜索结束,单词没有索引在该树
if current == nil || current.Children[index] == nil {
return false
}
}
return true
}

 

 

总结:

 

 

在字典树中查找数据,最坏的情况下还是很快的,时间复杂度为O(m)时间(m是搜索字符串的长度)。我们还可以在此基础上改进模糊搜索和自动补全。至于缓存,我们可以使用一个简单的golang map来存储已经搜索的单词或最常被搜索的单词。

全部评论