Golang 實現搜索引擎

概述

主要包括三個部分:

網絡爬蟲: 爬取儘可能多的網頁;
網頁分詞: 利用jieba庫對網頁內容進行分詞, 並存儲分詞結果（格式爲: 文檔 id, 文檔長度, 詞頻, 分詞偏移 - 文檔 id, 文檔長度, 詞頻, 分詞偏移）;
搜索頁面: 提供一個前端頁面, 用戶輸入搜索詞, 基於分詞相關性, 返回結果;

不要害怕，整個邏輯很簡單，邏輯拆分的很獨立，便於理解。項目地址: https://github.com/gofish2020/easysearch

如何啓動

在當前目錄執行 docker-compose up -d命令, 啓動 docker 環境;(進入 mysql 的 docker 內部, 查詢下 select host,user,plugin,authentication_string from mysql.user; 需要修改 root 的 host 爲 %，然後重啓 mysql, 否則外部是連接不上 mysql) 默認用戶名爲: root 密碼: 1 端口: 3306
修改 easysearch.ini文件中，關於數據庫的配置信息
執行 ./easysearch spider 命令 (可以重複執行), 會進行網頁數據的爬取, 結果保存到spider庫t_source表中;
執行./easysearch dict命令 (可以重複執行), 會對上述爬取的網頁進行分詞, 結果保存在 dictionary庫 t_dict表中;
執行 ./easysearch命令, 啓動 Web 服務器, 瀏覽器輸入 http://127.0.0.1:8080輸入關鍵詞, 點擊搜索

效果如下:

基本原理

1. 網絡爬蟲

既然要做搜索引擎，那麼我們就需要擁有數據供我們搜索。。數據來源於哪裏？數據全部都在互聯網上，別人不會主動把數據按照統一格式提供給我們的。所以，只能自己去爬取。

那麼爬取的思路是怎樣的？

爬取的思路：從某一個 url 開始（通過修改db/db.go中baseUrl常量來表示你想從哪個 url 開始，作爲創世紀的 URL），遍歷互聯網上的所有的 url。比如我們從https://hao123.com這個 url 開始，通過 http 請求，獲取到整個網頁數據，我們將網頁數據保存到數據庫中。同時解析網頁數據，將頁面中的所有的a標籤中的 href屬性全部提取出來，這些新的 url 繼續作爲我們待爬取的鏈接。這樣就不會源源不斷的產生新的 url。

這個理論就是：網頁的 “六度分隔理論”：從一個網頁到另外一個網頁，最多隻需 19 次點擊。

源碼位置： db/spider.go

t_source表結構

CREATE TABLE `t_source` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT COMMENT '自增id',
  `html_len` bigint unsigned NOT NULL DEFAULT '0' COMMENT '文檔長度',
  `title` varchar(1000) CHARACTERSET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL DEFAULT '' COMMENT '標題',
  `url` varchar(1024) CHARACTERSET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL DEFAULT '' COMMENT '鏈接',
  `md5`varchar(32) CHARACTERSET utf8 COLLATE utf8_unicode_ci NOTNULLDEFAULT '' COMMENT 'url對應的md5值',
  `html` longtext CHARACTERSET utf8mb4 COLLATE utf8mb4_unicode_ci COMMENT '頁面文字',
  `host` varchar(255) CHARACTERSET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL DEFAULT '' COMMENT '域名',
  `craw_done` tinyint NOT NULL DEFAULT '0' COMMENT '0 未爬 1 已爬 2 失敗',
  `dict_done` tinyint NOT NULL DEFAULT '0' COMMENT '0 未分詞 1 已分詞',
  `deleted_at` timestamp NULL DEFAULT NULL,
  `created_at` timestamp NOTNULL DEFAULT CURRENT_TIMESTAMP COMMENT '插入時間',
  `updated_at` timestamp NOTNULL DEFAULT CURRENT_TIMESTAMP ONUPDATE CURRENT_TIMESTAMP COMMENT'插入時間',
  PRIMARY KEY (`id`),
  UNIQUEKEY `md5` (`md5`)
) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

思路如下：

從表t_source中查詢爬取狀態爲 craw_done=0 【未爬取】的一組 url
針對每一個 url 發送 http 請求 queryUrl; 如果這裏你需要禁止爬取處於黑名單中的 url，那隻需要爬取之前判斷下域名，是不是在黑名單裏面，如果在的話，就直接跳過爬取，同時設定爲已爬去即可
如果可以正常爬取成功，利用 goquery這個庫，提取網頁的文本數據並保存到數據庫中；
同時利用goquery庫，對該網頁進行標籤遍歷，提取其中的a標籤中的 url，並保存到數據庫中（這裏要記得去重，因爲同一個頁面的中會存在相同的 url（局部去重），而且不同的頁面中也會存在相同的 url（全局去重）），避免無意義的重複爬取。

因爲整個中文互聯網的數據大概是 400 + 萬個網站，3000 億 + 網頁。如果只爬取 1% 的網頁，那也有 30 億。所以，如果想在生產環境上實現爬蟲，代碼肯定是要做優化的。

比如：分表：表肯定是要分表，按照單表 2000w 行計算的話，100 個表就是 20 億，大家可以分成 256 個表；啓動 256 個協程針對每個表進行單獨爬取，可以大幅提高效率。

去重：url 我們可以進行 md5 化，相同的 url 一定 md5 值相同。同時可以利用 md5 值，對 256 求餘，得到應該放到哪個表中（比如 md5 值爲 f2898798732, 我們可以直接截取 [f2]898798732，將 16 進制 f2 轉成 10 進制，不就是 256 的餘數嘛）；

全局去重：因爲要通過查 mysql 數據庫纔可知道是否重複。優化方案：可以將 md5 值放到 redis 集合中，提高查詢的效率，爲了避免 redis 大 key，依然可以分成多個 key。制訂好規則即可。（當然用布隆過濾器的思路也可以）

// craw_done = 0  從數據庫一次獲取limit個url，然後進行處理
func DoSpider(limit int) {
	//1. 指定使用spider數據庫
	mysqlDB.Exec("use " + SpiderDBName)

	//2. 執行t_source表查詢
	srcs := []Source{}
	//mysqlDB.Raw(" select id,url,md5 from t_source where craw_done=0 order by id asc limit 0,?", limit).Find(&res)
	mysqlDB.Model(&Source{}).Select([]string{"id,url,host,md5"}).Where("craw_done = ?", 0).Limit(limit).Order("id asc").Find(&srcs)

	for _, src := range srcs {
		//爬取信息
		doc := queryUrl(src.Url, 3)
		if doc == nil { // 爬取失敗
			src.CrawDone = "2"
			if src.Host == "" {
				u, _ := url.Parse(src.Url)
				src.Host = strings.ToLower(u.Host)
			}
			if src.Md5 == "" {
				src.Md5 = tools.GetMD5Hash(src.Url)
			}
			src.HtmlLen = 0
			src.UpdatedAt = time.Now()
			mysqlDB.Model(&src).Select("craw_done", "host", "md5", "html", "html_len", "title", "updated_at").Updates(src)
		} else {

			src.CrawDone = "1"
			src.Html = tools.StringStrip(strings.TrimSpace(doc.Text()))
			src.HtmlLen = uint(utf8.RuneCountInString(src.Html))
			src.Title = tools.StringStrip(strings.TrimSpace(doc.Find("title").Text()))
			src.UpdatedAt = time.Now()
			if src.Md5 == "" {
				src.Md5 = tools.GetMD5Hash(src.Url)
			}
			if src.Host == "" {
				u, _ := url.Parse(src.Url)
				src.Host = strings.ToLower(u.Host)
			}

			// 爬取成功,更新數據庫
			res := mysqlDB.Model(&src).Select("craw_done", "html", "html_len", "title", "update_at", "md5", "host").Updates(src)
			if res.RowsAffected > 0 {
				fmt.Println("已成功爬取", src.Url)
			}

			uniqueUrl := make(map[string]struct{}) // 當前頁面中的a鏈接去重
			// 解析html，提取更多的a鏈接，保存到數據庫
			doc.Find("a").Each(func(i int, s *goquery.Selection) {
				//
				href := width.Narrow.String(strings.Trim(s.AttrOr("href", ""), " \n"))
				_url, _, _ := strings.Cut(href, "#") // 去掉 #後面的
				_url = strings.ToLower(_url)

				if _, ok := uniqueUrl[_url]; ok { // 重複
					return
				}
				uniqueUrl[_url] = struct{}{}

				if tools.IsUrl(_url) { // 有效 url

					// 這裏還需要做一次全局去重複( 如果數量大，可以用redis來記錄url是否記錄過)
					md5 := tools.GetMD5Hash(_url)
					u, _ := url.Parse(_url)

					src := Source{Md5: md5, Url: _url, Host: strings.ToLower(u.Host), Model: gorm.Model{CreatedAt: time.Now(), UpdatedAt: time.Now()}}

					result := mysqlDB.First(&src, "md5 = ?", md5)

					if errors.Is(result.Error, gorm.ErrRecordNotFound) { // 說明不存在
						// 保存到數據庫中
						result := mysqlDB.Create(&src)

						if result.Error == nil && result.RowsAffected > 0 {
							fmt.Println("插入成功", _url)
						}
					}
				}
			})
		}

	}
}

2. 網頁分詞

說到分詞，就說下倒排索引。

比如有下面 3 篇文檔

XeFsxN

然後利用分詞庫，對文檔內容進行分詞

LzgQKL

將分詞結果和 ID 調換下位置，也就是 Dict 作爲唯一鍵，ID 作爲值，建立分詞表

ygVkS5

以這條記錄【愛 1,1-2,0-3,1- 】解釋下含義：

1,1表示 愛出現在文檔1的偏移量1的位置
- 表示文檔之前的分割
2,0 表示 愛出現在文檔2的偏移量0的位置
- 表示文檔之前的分割
3,1 表示 愛出現在文檔3的偏移量1的位置
- 表示文檔之前的分割

當我們要搜索【愛】字的時候，就可以從這個分詞表，查找到 1,1-2,0-3,1 - 這條內容，然後解析這串字符串得到文檔 ID，根據文檔 ID 再查詢出文檔內容，就是倒排索引。

當然存儲分詞的方式很多，你可以放到 MYSQL/MongoDB 中，也可以自己實現一個數據庫做分詞的快速檢索。

比如 ES 中，利用前綴樹給這些分詞再做一層索引 (Term Index)，通過 Term index 可以快速地定位到 term dictionary 的某個 offset（相當於縮小了查詢的範圍），然後從這個 offset 位置在 Term Dictionary 中往後順序查找，定位要搜索的詞，最後返回分詞對應的文檔列表 (Posting list)。

如果不加 Term Index，那麼搜索分詞就需要在 Term Dictionary 中通過二分法來查找，每次查找都對應一次磁盤 IO（因爲 Dictionary 數據量肯定很大，一定是在磁盤中存儲的，不可能全量都放在內存中的）。通過增加 Term Index，並且經過壓縮，這個前綴樹的數據量足夠的小，可以直接放在內存中。這樣可以直接在內存中定位到分詞的大概位置，然後再經過一次磁盤 IO，在 Term dictionary 中定位出分詞，那速度肯定就更快了。

源碼位置： /db/dict.go

我們這裏將分詞保存到 Mysql 數據庫中（等價於用 B + 樹作爲詞彙的索引了）

t_dict表結構:

CREATE TABLE `t_dict` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT COMMENT '自增id',
  `word` varchar(255) DEFAULT '' COMMENT '分詞',
  `positions` longtext CHARACTERSET utf8mb4 COLLATE utf8mb4_bin COMMENT '文檔id,文檔長度,詞頻,分詞偏移-文檔id,文檔長度,詞頻,分詞偏移',
  `deleted_at` timestamp NULL DEFAULT NULL,
  `created_at` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '插入時間',
  `updated_at` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ONUPDATE CURRENT_TIMESTAMP COMMENT '更新時間',
  PRIMARY KEY (`id`),
  UNIQUEKEY`word` (`word`)
) ENGINE=InnoDB AUTO_INCREMENT=26149 DEFAULTCHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

這裏解釋下字段positions的含義：比如 “我愛番茄炒蛋” 這個文檔（假設文檔 id 爲：20），經過分詞後，結果爲 ” 我 / 愛 / 番茄 / 炒 / 蛋 “，保存到 t_dict表爲

Fk6d3M

格式爲： 文檔id,文檔長度,詞頻,位置1,位置2-

文檔id:表示詞彙出現在哪些文檔中
文檔長度：記錄文檔id對應的長度
詞頻：表示詞彙在文檔中出現的次數；比如 【我愛愛我】假如分詞結果爲【我/愛/愛/我】，那麼，我和愛都各自出現了2次
位置1,位置2,位置N ： 表示文字在文檔中的偏移位置（不是字節數，而是字符數）
- ：表示多個文檔的分詞線

大家可能會好奇，爲什麼要存儲這些東西？其實這個是因爲接下來的文章的第三部分，BM25 算法需要這些值。（這裏你是用逗號分隔，還是 - 分割這些沒影響）

實際效果如下：

代碼思路如下：

初始化黑名單詞彙（比如 "的" "(" ")" 等等，這些詞基本每個文檔都會存在，沒有意義，直接忽略對這些詞彙的處理）
從數據庫t_source中查找已爬取（craw_done = 1），但是未分詞（dict_done = 0）的多條記錄
利用 jieba 庫，對爬取的網頁進行分詞, 得到一個分詞數組words
對每個詞彙統計該詞彙在當前的文檔中出現的【詞頻 / 位置】信息
最後將詞彙的信息進行彙總，保存到 t_dict表中

// craw_done = 1 and dict_done = 0 分詞多少條記錄
func DoDict(limit int) {

	// 1.使用 spider 庫
	mysqlDB.Exec("use " + SpiderDBName)

	// 黑名單詞彙
	once.Do(func() {
		blacks := []BlackList{}
		mysqlDB.Model(&blackList).Order("id asc").Find(&blacks)
		for _, black := range blacks {
			blackWord[black.Word] = struct{}{}
		}

	})
	// 2.查詢
	var srcs []Source
	mysqlDB.Model(&Source{}).Where("dict_done = ? and craw_done=1 and id > ?", 0, maxId).Limit(limit).Order("id asc").Find(&srcs)

	batchUpdate := make(map[string]string)

	for _, src := range srcs {

		fmt.Println("文檔id:", src.ID)
		htmlLen := utf8.RuneCountInString(src.Html)               // 頁面字符數
		words := jieba.JiebaInstance.CutForSearch(src.Html, true) // 頁面分詞

		// 比如：我愛你你愛我，分詞後就是：我/愛/你/你/愛/我 -->> 分詞結果就是有2個我2個你2個愛
		pos := 0
		statWork := make(map[string]wordInfo) // 一個網頁中，每個詞彙出現的頻次以及位置
		for _, word := range words {

			// 不區分大小寫 比如 baidu 和 BAIDU是 一個詞彙
			newWord := strings.ToLower(width.Narrow.String(word)) // 轉半角
			wordLen := utf8.RuneCountInString(newWord)

			// 判斷是否爲黑名單詞彙
			if _, ok := blackWord[newWord]; ok {
				pos += wordLen
				continue
			}

			if winfo, ok := statWork[newWord]; !ok {
				statWork[newWord] = wordInfo{
					count:     1,
					positions: []string{strconv.Itoa(pos)},
				}
			} else {
				winfo.count++
				winfo.positions = append(winfo.positions, strconv.Itoa(pos))
				statWork[newWord] = winfo
			}

			pos += wordLen
		}

		// 彙總結果
		for word, wordInfo := range statWork {

			// 文檔id,文檔長度,詞頻,位置1,位置2-
			infoString := strconv.FormatUint(uint64(src.ID), 10) + "," + strconv.Itoa(htmlLen) + "," + strconv.Itoa(wordInfo.count) + "," + strings.Join(wordInfo.positions, ",") + "-"

			batchUpdate[word] += infoString

		}

		// 更新t_source表分詞狀態
		src.DictDone = "1"
		src.UpdatedAt = time.Now()
		mysqlDB.Model(&src).Select("dict_done", "updated_at").Updates(src)

		if src.ID > maxId {
			maxId = src.ID
		}

	}

	// 開啓一個新鏈接，批量更新 t_dict
	mysqlDB.Connection(func(tx *gorm.DB) error {
		tx.Exec("use " + DictDBName)

		tx = tx.Begin()
		for word, positions := range batchUpdate {
			tx.Exec(" insert into "+dictTable.TableName()+" (word,positions) values (?,?) on duplicate key update positions = concat(ifnull(positions,''), ?) ", word, positions, positions)
		}
		tx.Commit()
		returnnil
	})

}

3. 搜索頁面

當我們爬取完網頁，並且分詞完成以後，那接下來就要對外提供服務了。

效果如下：

當我們輸入一個關鍵詞以後，到底是怎麼知道，我們的這個關鍵詞應該最後匹配哪些文檔返回給用戶呢？

這就要說到 BM25 算法（某一個目標文檔（Document）相對於一個查詢關鍵字（Query）的 “相關性”），本質就是一組數學公式。我們只需要套公式即可。

【公式 1】判斷一個詞語與一個文檔的相關性權重，較常用的就是 TF-IDF 算法中的 IDF

公式解釋：

N 表示待檢索文檔的數目（其實就是已經完成分詞的網頁總數量）
n(Qi) 表示包含被搜索詞的文檔數量（其實就是包含該詞的網頁數量，這個不就是上面分詞結果中positions字段保存的值嘛，用多個 - 分割的文檔 id 數量）
最終的結果 IDF ：說人話就是，比如 “的” 這個詞，幾乎每個文檔中都包含，那麼就說明這個 “的” 詞就不重要，那麼詞彙和文檔的相關性就不強。（再比如：我們去公安局想找個叫毛蛋的人，全國叫這個名字的會非常多，說明毛蛋這個詞太沒特色了）

【公式 2】相關性得分

k1 k2 b 爲調節因子，通常爲 k1 = 2 b = 0.75
fi 表示詞彙在文檔中出現的頻次（上面的 positions 中有保存）
Dj 表示文檔的長度（上面的 positions 中有保存）
avgDj 表示所有文檔的平均長度

【最終公式爲】

將詞彙的相關性權重 IDF * 詞彙的相關性得分，得到的就是詞彙和文檔的相關性，將文檔的得分累加起來，文檔的得分越高，說明和被搜索詞的相關度也越高，對於用戶來說越有價值。做個倒序排列返回給用戶即可。

源碼路徑:db/search.go

結合註釋，照着上面的公式很好理解。

注意一點：用戶輸入的搜索詞，到了我們服務端，也是要進行分詞的，然後用分詞後的詞彙，來進行計算

func Search(words []string) []SearchResult {

	statRes := StatResult{}
	mysqlDB.Exec("use " + SpiderDBName)
	mysqlDB.Raw("select count(1) as count, sum(html_len) as total from "+srcTable.TableName()+" where dict_done=?", 1).Find(&statRes)

	// N 已經完成分詞的文檔數量
	N := statRes.Count
	if N == 0 { // do nothing
		returnnil
	}

	// 平均文檔長度
	avgDocLength := float64(statRes.Total) / float64(statRes.Count)

	// 記錄文檔的總得分
	docScore := make(map[string]float64)

	mysqlDB.Exec("use " + DictDBName)

	// 每次針對一個詞進行處理
	for _, word := range words {

		var dict Dict
		mysqlDB.Model(&dictTable).Where("word = ?", word).Find(&dict)
		if dict.ID == 0 {
			continue
		}

		positions := strings.Split(dict.Positions, "-")
		positions = positions[:len(positions)-1] // 去掉最後一個【符號-】

		// NQi 含有這個詞的文檔有多少個
		NQi := int64(len(positions)) // -1因爲尾部多了一個【符號-】
		// IDF ： 如果一個詞在很多頁面裏面都出現了，那說明這個詞不重要，例如“的”字，哪個頁面都有，說明這個詞不準確，進而它就不重要。
		IDF := math.Log10((float64(N-NQi) + 0.5) / (float64(NQi) + 0.5))

		// 固定值
		k1 := 2.0
		b := 0.75
		for _, position := range positions { // 這裏其實就是和 word 關聯的 所有文檔

			docInfo := strings.Split(position, ",") //  文檔id,文檔長度,詞頻,位置1,位置2-

			//Dj :文檔長度
			Dj, _ := strconv.Atoi(docInfo[1])
			//Fi :該詞在文檔中出現的詞頻
			Fi, _ := strconv.Atoi(docInfo[2])

			// 本詞和本文檔的相關性
			RQiDj := (float64(Fi) * (k1 + 1)) / (float64(Fi) + k1*(1-b+b*(float64(Dj)/avgDocLength)))

			// 彙總所有文檔的相關性總得分
			docScore[docInfo[0]] += RQiDj * IDF
		}
	}

	// 根據積分排序文檔

	docIds := make([]string, 0, len(docScore)) // 文檔ids
	for id := range docScore {
		docIds = append(docIds, id)
	}

	sort.SliceStable(docIds, func(i, j int) bool {
		return docScore[docIds[i]] > docScore[docIds[j]] // 按照分從【大到小排序】
	})

	// 默認取 20個
	limit := 20
	iflen(docIds) < limit {
		limit = len(docIds)
	}
	docIds = docIds[0:limit]

	// 然後利用id回表查詢文檔內容
	sousouResult := make([]SearchResult, 0)
	mysqlDB.Exec("use " + SpiderDBName)
	for _, docId := range docIds {

		var src Source
		mysqlDB.Table(src.TableName()).Where("id = ?", docId).Find(&src)

		// 從Html中截取 一段文本作爲簡介（去掉了其中的ascii編碼字符）
		rep := regexp.MustCompile("[[:ascii:]]")
		brief := rep.ReplaceAllLiteralString(src.Html, "")

		briefLen := utf8.RuneCountInString(brief)
		if briefLen > 100 {
			brief = string([]rune(brief)[:100])
		}

		sousouResult = append(sousouResult, SearchResult{
			Title: src.Title,
			Brief: brief,
			Url:   src.Url,
		})
	}

	return sousouResult
}

總結

整個搜索引擎的本質就是利用分詞庫jieba對網頁內容進行分詞，將分詞結果保存起到MYSQL中。當用戶搜索到時候，利用數學公式計算文檔和搜索詞之間的相關性得分，得分越高越是我們想要的文檔。

可能有人說，直接用 ES 不就可以了。。確實沒毛病。通過本項目，至少可以讓你知道，不用 ES 你也可以做到，而且讓你有種更直觀的感受。

通過上面的公式其實也可以看到，就是概率公式，當只有少量的網頁數據，除非你的搜索詞很” 特別 “，不然結果並不準確。當數據量大了以後，匹配的準確性就會很高，

參考資料：

【NLP】非監督文本匹配算法——BM25 https://zhuanlan.zhihu.com/p/499906089

2021 年中國互聯網發展基本情況分析 https://www.chyxx.com/industry/1104557.html

elasticsearch 倒排索引原理 https://zhuanlan.zhihu.com/p/33671444

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/H2sinHVwxp7FerFZfiVVeQ

概述