在做一个小项目，需要做文本搜索。最初的想法是使用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] - 'a'
//搜索到nil节点，说明已经搜索结束，单词没有索引在该树
if current == nil || current.Children[index] == nil {
return false
}
}
return true
}
总结：
在字典树中查找数据，最坏的情况下还是很快的，时间复杂度为O(m)时间(m是搜索字符串的长度)。我们还可以在此基础上改进模糊搜索和自动补全。至于缓存，我们可以使用一个简单的golang map来存储已经搜索的单词或最常被搜索的单词。
网友评论