在做一個(gè)小項(xiàng)目，需要做文本搜索。最初的想法是使用elastic serach。然而歧匈，安裝和管理elastic serach對(duì)于一個(gè)少于1000行代碼的項(xiàng)目來(lái)說(shuō)似乎有點(diǎn)大材小用垒酬。
我想要的只是一個(gè)可以搜索大約500萬(wàn)個(gè)單詞的小型嵌入式庫(kù)砰嘁。該庫(kù)具有以下特點(diǎn):
1、足夠快
2勘究、支持全文搜索
3矮湘、具有自動(dòng)補(bǔ)全功能
4、緩存結(jié)果
5口糕、內(nèi)存高效
嘗試使用Bleve搜索缅阳，但最終放棄了，因?yàn)楫?dāng)索引數(shù)據(jù)時(shí)景描，它占用很多內(nèi)存十办。最后，只能自己實(shí)現(xiàn)一個(gè)簡(jiǎn)單的文本搜索庫(kù)超棺，因此決定使用Golang來(lái)實(shí)現(xiàn)字典樹(shù)向族。
假設(shè)
1、僅存儲(chǔ)小寫(xiě)字母
2棠绘、字典樹(shù)用于索引和搜索數(shù)據(jù)
字典樹(shù)工作原理
它是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)件相，其中節(jié)點(diǎn)的所有子節(jié)點(diǎn)都有一個(gè)共同的前綴再扭。這意味著cat和can共享ca的前綴。查找數(shù)據(jù)非骋勾＃快泛范。最壞的情況是O(m)時(shí)間(其中m是搜索字符串的長(zhǎng)度)。
字典樹(shù)中的每個(gè)字符都可以用一個(gè)節(jié)點(diǎn)來(lái)表示紊撕。在我們的例子中罢荡，每個(gè)節(jié)點(diǎn)最多有26個(gè)子節(jié)點(diǎn)(a-z)，因?yàn)槲覀冎淮鎯?chǔ)小寫(xiě)字母逛揩。
看下面的圖以來(lái)解釋下：
從根節(jié)點(diǎn)開(kāi)始柠傍，根結(jié)點(diǎn)永遠(yuǎn)是查詢(xún)的第一個(gè)節(jié)點(diǎn)。如您所見(jiàn)辩稽，根節(jié)點(diǎn)有26個(gè)子節(jié)點(diǎn)(a-z)惧笛。節(jié)點(diǎn)a是根節(jié)點(diǎn)的子節(jié)點(diǎn)，它也有26個(gè)子節(jié)點(diǎn)逞泄，從a到z患整。我們將添加到字典樹(shù)的所有節(jié)點(diǎn)都有26個(gè)子節(jié)點(diǎn)。
以cat這個(gè)單詞為例喷众，如何在樹(shù)中表示：
從黑色節(jié)點(diǎn)索引或搜索單詞cat各谚，我們只需要訪問(wèn)4個(gè)節(jié)點(diǎn)。分別是根節(jié)點(diǎn)....然后是根節(jié)點(diǎn)的字節(jié)點(diǎn)c及其字節(jié)點(diǎn)a到千，最后是子節(jié)點(diǎn)a的子節(jié)點(diǎn)t昌渤。如果還有cats的話(huà)，將擴(kuò)展節(jié)點(diǎn)t包含26個(gè)子節(jié)點(diǎn)即a到z憔四，查詢(xún)t的子節(jié)點(diǎn)是s膀息。
不斷搜索字典樹(shù)，直到完成所有要查詢(xún)的單詞了赵。注意：即使字典里有10億個(gè)單詞潜支，我們也只需要4步就能找到cat這個(gè)單詞。
而且你會(huì)發(fā)現(xiàn)柿汛，大多數(shù)單詞共享一條路徑冗酿。例如，car和cat共享節(jié)點(diǎn)c和節(jié)點(diǎn)a络断，如下所示：
創(chuàng)建節(jié)點(diǎn)node
1裁替、字典樹(shù)的第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)，不包含任何字母可以為null貌笨。
2弱判、每個(gè)節(jié)點(diǎn)(包括本例中的根節(jié)點(diǎn))都應(yīng)該有26個(gè)子節(jié)點(diǎn)。
下面來(lái)實(shí)現(xiàn)代碼：
//Node 表示每個(gè)字符
type Node struct {
Char string //這是一個(gè)字母用于存儲(chǔ)類(lèi)似a,b,c,d等字母
Children [26]*Node //存儲(chǔ)本節(jié)點(diǎn)等所有字節(jié)點(diǎn)a到z
}
//NewNode 初始化一個(gè)新的節(jié)點(diǎn)躁绸，包含26個(gè)字節(jié)點(diǎn)
func NewNode(char string) *Node {
node := &Node{Char: char}
for i := 0; i < 26; i++ {
node.Children[i] = nil
}
return node
}
創(chuàng)建字典樹(shù)
1裕循、字典樹(shù)包含一個(gè)根節(jié)點(diǎn)臣嚣，用于搜索任何字符串的起始點(diǎn)。
//Trie 包含所有節(jié)點(diǎn)的樹(shù), 根節(jié)點(diǎn)為nil
type Trie struct {
RootNode *Node
}
//NewTrie 創(chuàng)建字典樹(shù)
func NewTrie() *Trie {
root := NewNode("\000") //根節(jié)點(diǎn)可以存任意內(nèi)容
return &Trie{RootNode: root}
}
索引數(shù)據(jù)
索引數(shù)據(jù)意味著用實(shí)際字符替換nil節(jié)點(diǎn)剥哑。 例如硅则，假設(shè)正在索引單詞cat。我們要做的是從根節(jié)點(diǎn)開(kāi)始株婴。然后開(kāi)始遍歷樹(shù)怎虫，試圖找到合適的節(jié)點(diǎn)來(lái)放置字符c。如果我們已經(jīng)到達(dá)樹(shù)的末端困介，但還沒(méi)有完成對(duì)整個(gè)單詞的索引大审，我們只需要?jiǎng)?chuàng)建一個(gè)新節(jié)點(diǎn)。
例如座哩，字典樹(shù)目前只包含根節(jié)點(diǎn)和26個(gè)子節(jié)點(diǎn)徒扶，它們的值都為nil。
對(duì)于每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)根穷，索引0將映射到字符a姜骡，索引1將映射到字符b，索引2將映射到字符c屿良，以此類(lèi)推圈澈。
這意味著在根節(jié)點(diǎn)的下標(biāo)為2處，我們應(yīng)該插入c尘惧，然后創(chuàng)建另一個(gè)子節(jié)點(diǎn)c康栈，并將a放在該節(jié)點(diǎn)的下標(biāo)0處。一直這樣做喷橙，直到cat所有的字符都被索引啥么。注意，如果一個(gè)節(jié)點(diǎn)已經(jīng)存在重慢，則移動(dòng)到下一個(gè)字符饥臂。
//Insert 插入單詞到字典樹(shù)
func (t *Trie)Insert(word string) error {
//查詢(xún)當(dāng)前節(jié)點(diǎn)逊躁，從樹(shù)到根節(jié)點(diǎn)開(kāi)始
current := t.RootNode
//去除單詞中到空格
strippedWord := strings.ToLower(strings.ReplaceAll(word, " ", ""))
for i := 0; i < len(strippedWord); i++{
//根據(jù)ASCII表97代表字符a似踱，將字符轉(zhuǎn)為整數(shù)索引值
index := strippedWord[i] - 'a'
//查看當(dāng)前字符是否存在，
if current.Children[index] == nil { //如果不存在
current.Children[index] = NewNode(string(strippedWord[i]))
}
current = current.Children[index]
//支持自動(dòng)補(bǔ)全
}
return nil
}
代碼index:= stripedword [i] - ' a '用來(lái)獲得一個(gè)字符的索引稽煤。就是從ascii表中取一個(gè)字符的十進(jìn)制表示，然后減去a(97)的十進(jìn)制表示酵熙。例如轧简，c-a會(huì)被翻譯成(99-97)=2匾二，這是c的索引拳芙。
搜索單詞
搜索單詞的函數(shù)與索引類(lèi)似，以同樣的方式遍歷這棵樹(shù)：
//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節(jié)點(diǎn)，說(shuō)明已經(jīng)搜索結(jié)束睹限，單詞沒(méi)有索引在該樹(shù)
if current == nil || current.Children[index] == nil {
return false
}
}
return true
}
總結(jié)：
在字典樹(shù)中查找數(shù)據(jù)，最壞的情況下還是很快的羡疗，時(shí)間復(fù)雜度為O(m)時(shí)間(m是搜索字符串的長(zhǎng)度)。我們還可以在此基礎(chǔ)上改進(jìn)模糊搜索和自動(dòng)補(bǔ)全别洪。至于緩存，我們可以使用一個(gè)簡(jiǎn)單的golang map來(lái)存儲(chǔ)已經(jīng)搜索的單詞或最常被搜索的單詞挖垛。
