從零構建搜索引擎 build demo search engine from scratch
我們每天都會使用搜索引擎：打開google等搜索引擎，輸入關鍵詞，檢索出結果，這是一次搜索；當打開歷史記錄旁邊的🔍按鈕，輸入關鍵詞，檢索出結果，這也是一次搜索。
本文將從原理開始到最終實現一個搜索demo，探究搜索引擎背后是如何實現“一瞬間”從海量數據中檢索出想要的結果的。
配合本文，實現了一個本文講述的搜索引擎的demo用于檢索內容，支持AND、包含、排除查詢等常見的查詢，也附帶上簡單的benchmark對比，可見我的github倉庫：https://github.com/578223592/go-small-practices/tree/main/search_engine
全文搜索
全文搜索可以簡單的定義為：根據輸入的查詢語句（query），在一組文檔（document）中，篩選出符合條件的文檔。
過程
要實現全文搜索，我們可以想象到最簡單的方式就是循環去匹配，like如下的偽代碼，想象一下這種循環會在文檔數量增加和查詢復雜后產生多少次循環匹配計算：
a = ["just", "do"] #查詢條件count = 0 #匹配數量for d in tokenized_documents: #遍歷文檔for t in d: #遍歷文檔中的每個語句for c in a: # 遍歷查詢條件if c == t: # 如果匹配，則count++count += 1return count
因此在現實世界，會對文檔進行預處理（分析），分析之后產生索引。查詢的時候根據索引去匹配定位到源文件，比如下圖這樣的管道：
?
實際上索引是不同查詢引擎里面影響性能的關鍵，我們通常可以用如下指標來評價一個搜索索引的好壞：
- 計算索引的速度
- 壓縮率
- 可拓展性
- 查詢性能
由于本人目前對搜索索引的了解也不是特別深入，因此這里就不賣弄了。
關鍵詞
?document?：一組單詞。
Do it. Just do it. Don’t let your dreams be dreams. Yesterday, you said tomorrow. So just do it. Make your dreams come true. Just do it. Some people dream of success, while you’re gonna wake up and work hard at it. Nothing is impossible. You should get to the point where anyone else would quit, and you’re not gonna stop there. No, what are you waiting for? Do it! Just do it! Yes you can. Just do it.
?term?：詞。
just
?token?：用戶輸入的查詢詞（或其變體）在被檢索文檔中出現的每一個具體匹配實例。
Just do it. .... So just do it. Make your dreams come true. Just do it. ... Just do .... Just do it.
?query?：指定特定格式的查詢語句
以下舉例的是本文構建出來的搜索引擎支持的查詢格式，不同引擎的語句可能是不同的。
just：查詢包含just的文檔
just do：查詢包含just或者包含do的文檔
just AND do：查詢同時包含just和do的文檔
"just do"：查詢順序出現just和do的文檔
just do+it：出現it的文檔中，查詢包含just或者包含do的文檔
just do -it：查詢包含just或者包含do的文檔，再剔除掉包含it的文檔。
?score?：文檔匹配的分數，如果多個文檔都符合查詢條件，那么文檔的列表會按照分數從高到低給出。本文搜索引擎是按照文檔中匹配到的詞的個數來評分，現實世界中的評分會參考更多因素， 比如說地區、性別等等。
?index?：索引，搜索的索引為inverted-index?（倒序索引），其可以根據關鍵詞尋找關鍵詞出現的位置，通常的結構如下。這是搜索引擎如此之快的關鍵奧秘！通過inverted-index?，我們尋找關鍵詞不再需要通過遍歷文檔，而是可以直接通過類似key->value查找的方式，速度非常快。
just -> [(1, 0), (1, 5), (1, 20), (1, 28), (1, 76), (1, 82)] #含義是just出現的位置是document1的第0個位置，document1的第5個位置，document1的第20個位置。。。
do -> [(0, 94), (0, 399), (0, 455), (0, 493), (1, 1), (1, 3), (1, 6), (1, 21), (1, 29), (1, 74), (1, 77), (1, 83), (2, 15), (2, 33), (2, 44)] #含義是do出現的位置是。。。
搜索索引稱為inverted-index?的原因是通常的索引是根據位置去找內容，而inverted-index是根據內容去找位置，是inverted版本的普通索引。
關鍵算法實現
創建倒序索引：
func (a *Analyser) AnalyseAndIndex(documents []string) {for docId, oneDocument := range documents {tokens := regexp.MustCompile(`\w+`).FindAllString(oneDocument, -1) // 使用正則將文檔拆解成termfor index, token := range tokens {token = strings.ToLower(token)local_ := local{DocId: int64(docId), Indexes: int64(index)} //use inverted index to index termsif a.index == nil {a.index = make(map[string][]local)}a.index[token] = append(a.index[token], local_)}}
}
?
搜索：
我們將文檔檢索分成四種模式，如下代碼塊所示，默認來說是OR模式，如果出現其他模式的關鍵詞，那么就會調整對應的搜索模式：
const (AND searchModeExp = "AND"OR searchModeExp = "OR"INCLUDE searchModeExp = "+"EXCLUDE searchModeExp = "-"
)
我們創建了兩個結果數組，分別用于記錄結果和記錄必須要排除掉的文檔（EXCLUDE searchModeExp = "-"?)：
includeDocScoresMap := make(map[int64]float64)excludeDocMap := make(map[int64]any)
此外，還需要注意的是，為了支持"just do"?這樣保證順序的查找，我們需要匹配成對出現的"?，然后根據其中的內容去文檔中固定匹配內容，而不能直接簡單組合不同文檔的內容。
整個搜索過程關鍵算法如下：
func (a *Analyser) Search(keyWords string) []SearchRes {includeDocScoresMap := make(map[int64]float64)excludeDocMap := make(map[int64]any)queryExpressions := a.parseQuery(keyWords)var searchMode = OR // for i := 0; i < len(queryExpressions); i++ {var locals []localif isSearchMode(queryExpressions[i]) { //調整搜索模式searchMode = searchModeExp(queryExpressions[i])continue} else if queryExpressions[i] == Quote {endIndex := stringsIndex(queryExpressions[i+1:], Quote)if endIndex == -1 {continue // 缺少結束引號，忽略}if endIndex == 0 {continue // 引號中間沒有任何exp，忽略}quoteQueryExpressions := queryExpressions[i+1 : i+1+endIndex]i += endIndex + 1for i2 := range quoteQueryExpressions {quoteQueryExpressions[i2] = strings.ToLower(quoteQueryExpressions[i2])}firstExp, otherExp := quoteQueryExpressions[0], quoteQueryExpressions[1:]var ok boollocals, ok = a.index[firstExp]if !ok {// not found,early continuecontinue}for _, exp := range otherExp {locals = a.findExpInIndex(locals, exp)}} else {// searchlocals = a.index[queryExpressions[i]]}switch searchMode {case AND:for _, l := range locals {if _, ok := includeDocScoresMap[l.DocId]; ok {includeDocScoresMap[l.DocId] += 1}}case OR:for _, l := range locals {includeDocScoresMap[l.DocId] += 1}case INCLUDE:locsMap := make(map[int64]float64, len(includeDocScoresMap))for _, l := range locals {locsMap[l.DocId] = includeDocScoresMap[l.DocId] + 1}includeDocScoresMap = locsMapcase EXCLUDE:for _, l := range locals {excludeDocMap[l.DocId] = nil}}searchMode = OR}res := make([]SearchRes, 0)for k, v := range includeDocScoresMap {if _, ok := excludeDocMap[k]; ok {continue}res = append(res, SearchRes{DocId: k, Score: v})}slices.SortFunc(res, func(a, b SearchRes) int {return int(b.Score - a.Score) // order by score desc})return res
}
?
真正的搜索引擎考慮更多內容，比如說搜索計劃、ast、黑客、錯誤糾正、類型匹配（比如說搜索攀枝花，推薦攀枝花城市、攀枝花花朵等）。
?
總結
本文通過講解搜索中analyze-》index—》query步驟，其中出現的關鍵名詞，和一個簡單的demo代碼，講解了搜索引擎實現的關鍵技術， 希望對你有所幫助！
?
參考：
- strong thanks ：Building a search engine from scratch | by Halvor Fladsrud B? | Medium
?
