搜索引擎背后的經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法

由于渲染問題，文字漏了一大段，文章重發(fā)一遍

前言

我們每天都在用 Google, 百度這些搜索引擎，那大家有沒想過搜索引擎是如何實(shí)現(xiàn)的呢，看似簡(jiǎn)單的搜索其實(shí)技術(shù)細(xì)節(jié)非常復(fù)雜，說搜索引擎是 IT 皇冠上的明珠也不為過，今天我們來就來簡(jiǎn)單過一下搜索引擎的原理，看看它是如何工作的，當(dāng)然搜索引擎博大精深，一篇文章不可能完全介紹完，我們只會(huì)介紹它最重要的幾個(gè)步驟，不過萬(wàn)變不離其宗，搜索引擎都離不開這些重要步驟，剩下的無(wú)非是在其上添磚加瓦，所以掌握這些「關(guān)鍵路徑」，能很好地達(dá)到觀一斑而窺全貎的目的。

本文將會(huì)從以下幾個(gè)部分來介紹搜索引擎，會(huì)深度剖析搜索引擎的工作原理及其中用到的一些經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法，相信大家看了肯定有收獲。

1. 搜索引擎系統(tǒng)架構(gòu)圖
2. 搜索引擎工作原理詳細(xì)剖析

搜索引擎系統(tǒng)架構(gòu)圖

搜索引擎整體架構(gòu)圖如下圖所示，大致可以分為搜集，預(yù)處理，索引，查詢這四步，每一步的技術(shù)細(xì)節(jié)都很多，我們將在下文中詳細(xì)分析每一步的工作原理。

搜索引擎工作原理詳細(xì)剖析

一、搜集

爬蟲一開始是不知道該從哪里開始爬起的，所以我們可以給它一組優(yōu)質(zhì)種子網(wǎng)頁(yè)的鏈接，比如新浪主頁(yè)，騰訊主頁(yè)等，這些主頁(yè)比較知名，在 Alexa 排名上也非?？壳?，拿到這些優(yōu)質(zhì)種子網(wǎng)頁(yè)后，就對(duì)這些網(wǎng)頁(yè)通過廣度優(yōu)先遍歷不斷遍歷這些網(wǎng)頁(yè)，爬取網(wǎng)頁(yè)內(nèi)容，提取出其中的鏈接，不斷將其將入到待爬取隊(duì)列，然后爬蟲不斷地從 url 的待爬取隊(duì)列里提取出 url 進(jìn)行爬取，重復(fù)以上過程...

當(dāng)然了，只用一個(gè)爬蟲是不夠的，可以啟動(dòng)多個(gè)爬蟲并行爬取，這樣速度會(huì)快很多。

1、待爬取的 url 實(shí)現(xiàn)

待爬取 url 我們可以把它放到 Redis 里，保證了高性能，需要注意的是，Redis 要開啟持久化功能，這樣支持?jǐn)帱c(diǎn)續(xù)爬，如果 Redis 掛掉了，重啟之后由于有持續(xù)久功能，可以從上一個(gè)待爬的 url 開始重新爬。

2、如何判重

如何避免網(wǎng)頁(yè)的重復(fù)爬取呢，我們需要對(duì) url 進(jìn)行去重操作，去重怎么實(shí)現(xiàn)？可能有人說用散列表，將每個(gè)待抓取 url 存在散列表里，每次要加入待爬取 url 時(shí)都通過這個(gè)散列表來判斷一下是否爬取過了，這樣做確實(shí)沒有問題，但我們需要注意到的是這樣需要會(huì)出巨大的空間代價(jià)，有多大，我們簡(jiǎn)單算一下，假設(shè)有 10 億 url （不要覺得 10 億很大，像 Google, 百度這樣的搜索引擎，它們要爬取的網(wǎng)頁(yè)量級(jí)比 10 億大得多），放在散列表里，需要多大存儲(chǔ)空間呢？

我們假設(shè)每個(gè)網(wǎng)頁(yè) url 平均長(zhǎng)度 64 字節(jié)，則 10 億個(gè) url 大約需要 60 G 內(nèi)存，如果用散列表實(shí)現(xiàn)的話，由于散列表為了避免過多的沖突，需要較小的裝載因子（假設(shè)哈希表要裝載 10 個(gè)元素，實(shí)際可能要分配 20 個(gè)元素的空間，以避免哈希沖突），同時(shí)不管是用鏈?zhǔn)酱鎯?chǔ)還是用紅黑樹來處理沖突，都要存儲(chǔ)指針，各種這些加起來所需內(nèi)存可能會(huì)超過 100 G，再加上沖突時(shí)需要在鏈表中比較字符串，性能上也是一個(gè)損耗，當(dāng)然 100 G 對(duì)大型搜索引擎來說不是什么大問題，但其實(shí)還有一種方案可以實(shí)現(xiàn)遠(yuǎn)小于 100 G 的內(nèi)存：布隆過濾器。

針對(duì) 10 億個(gè) url，我們分配 100 億個(gè) bit，大約 1.2 G, 相比 100 G 內(nèi)存，提升了近百倍！可見技術(shù)方案的合理選擇能很好地達(dá)到降本增效的效果。

當(dāng)然有人可能會(huì)提出疑問，布隆過濾器可能會(huì)存在誤判的情況，即某個(gè)值經(jīng)過布隆過濾器判斷不存在，那這個(gè)值肯定不存在，但如果經(jīng)布隆過濾器判斷存在，那這個(gè)值不一定存在,針對(duì)這種情況我們可以通過調(diào)整布隆過濾器的哈希函數(shù)或其底層的位圖大小來盡可能地降低誤判的概率，但如果誤判還是發(fā)生了呢，此時(shí)針對(duì)這種 url 就不爬好了，畢竟互聯(lián)網(wǎng)上這么多網(wǎng)頁(yè)，少爬幾個(gè)也無(wú)妨。

3、網(wǎng)頁(yè)的存儲(chǔ)文件: doc_raw.bin

爬完網(wǎng)頁(yè)，網(wǎng)頁(yè)該如何存儲(chǔ)呢，有人說一個(gè)網(wǎng)頁(yè)存一個(gè)文件不就行了，如果是這樣，10 億個(gè)網(wǎng)頁(yè)就要存 10 億個(gè)文件，一般的文件系統(tǒng)是不支持的，所以一般是把網(wǎng)頁(yè)內(nèi)容存儲(chǔ)在一個(gè)文件（假設(shè)為 doc_raw.bin）中，如下

當(dāng)然一般的文件系統(tǒng)對(duì)單個(gè)文件的大小也是有限制的，比如 1 G，那在文件超過 1 G 后再新建一個(gè)好了。

圖中網(wǎng)頁(yè) id 是怎么生成的，顯然一個(gè) url 對(duì)應(yīng)一個(gè)網(wǎng)頁(yè) id，所以我們可以增加一個(gè)發(fā)號(hào)器，每爬取完一個(gè)網(wǎng)頁(yè)，發(fā)號(hào)器給它分配一個(gè) id，將網(wǎng)頁(yè) id 與 url 存儲(chǔ)在一個(gè)文件里，假設(shè)命名為 doc_id.bin,如下

二、預(yù)處理

爬取完一個(gè)網(wǎng)頁(yè)后我們需要對(duì)其進(jìn)行預(yù)處理，我們拿到的是網(wǎng)頁(yè)的 html 代碼，需要把 <script>,<style>,<option> 這些無(wú)用的標(biāo)簽及標(biāo)簽包含的內(nèi)容給去掉，怎么查找是個(gè)學(xué)問，可能有人會(huì)說用 BF ，KMP 等算法，這些算法確實(shí)可以，不過這些算法屬于單模式串匹配算法，查詢單個(gè)字段串效率確實(shí)不錯(cuò)，但我們想要一次性查出<script>,<style>,<option>這些字段串，有啥好的方法不，答案是用AC 自動(dòng)機(jī)多模式串匹配算法，可以高效一次性找出幾個(gè)待查找的字段串，有多高效，時(shí)間復(fù)雜度接近 0(n)！關(guān)于 AC 自動(dòng)機(jī)多模式匹配算法的原理不展開介紹，大家可以去網(wǎng)上搜搜看， 這里只是給大家介紹一下思路。

找到這些標(biāo)簽的起始位置后，剩下的就簡(jiǎn)單了，接下來對(duì)每個(gè)這些標(biāo)簽都查找其截止標(biāo)簽 </script>,</style>,</option>，找到之后，把起始終止標(biāo)簽及其中的內(nèi)容全部去掉即可。

做完以上步驟后，我們也要把其它的 html 標(biāo)簽去掉（標(biāo)簽里的內(nèi)容保留），因?yàn)槲覀冏罱K要處理的是純內(nèi)容（內(nèi)容里面包含用戶要搜索的關(guān)鍵詞）

三、分詞并創(chuàng)建倒排索引

拿到上述步驟處理過的內(nèi)容后，我們需要將這些內(nèi)容進(jìn)行分詞，啥叫分詞呢，就是將一段文本切分成一個(gè)個(gè)的詞。比如 「I am a chinese」分詞后，就有 「I」,「am」,「a」,「chinese」這四個(gè)詞,從中也可以看到，英文分詞相對(duì)比較簡(jiǎn)單，每個(gè)單詞基本是用空格隔開的，只要以空格為分隔符切割字符串基本可達(dá)到分詞效果，但是中文不一樣，詞與詞之類沒有空格等字符串分割，比較難以分割。以「我來到北京清華大學(xué)」為例，不同的模式產(chǎn)生的分詞結(jié)果不一樣，以 github 上有名的 jieba 分詞開源庫(kù)為例，它有如下幾種分詞模式

【全模式】: 我/ 來到/ 北京/ 清華/ 清華大學(xué)/ 華大/ 大學(xué)
【精確模式】: 我/ 來到/ 北京/ 清華大學(xué)
【新詞識(shí)別】：他, 來到, 了, 網(wǎng)易, 杭研, 大廈
【搜索引擎模式】： 小明, 碩士, 畢業(yè), 于, 中國(guó), 科學(xué), 學(xué)院, 科學(xué)院, 中國(guó)科學(xué)院, 計(jì)算, 計(jì)算所, 后, 在, 日本, 京都, 大學(xué), 日本京都大學(xué), 深造

分詞一般是根據(jù)現(xiàn)成的詞庫(kù)來進(jìn)行匹配，比如詞庫(kù)中有「中國(guó)」這個(gè)詞，用處理過的網(wǎng)頁(yè)文本進(jìn)行匹配即可。當(dāng)然在分詞之前我們要把一些無(wú)意義的停止詞如「的」,「地」,「得」先給去掉。

經(jīng)過分詞之后我們得到了每個(gè)分詞與其文本的關(guān)系，如下

細(xì)心的你一定發(fā)現(xiàn)了，不同的網(wǎng)頁(yè)內(nèi)容有可能出現(xiàn)同樣的分詞，所以我們把具有相同分詞的網(wǎng)頁(yè)歸在一起，如下所示

這樣我們?cè)谒选复髮W(xué)」的時(shí)候找到「大學(xué)」對(duì)應(yīng)的行，就能找到所有包含有「大學(xué)」的文檔 id 了。

看到以上「分詞」+「倒排索引」的處理流程，大家想到了什么？沒錯(cuò)，這不就是 ElasticSearch 搜索引擎干的事嗎，也是 ES 能達(dá)到毫秒級(jí)響應(yīng)的關(guān)鍵！

這里還有一個(gè)問題，根據(jù)某個(gè)詞語(yǔ)獲取得了一組網(wǎng)頁(yè)的 id 之后，在結(jié)果展示上，哪些網(wǎng)頁(yè)應(yīng)該排在最前面呢，為啥我們?cè)?Google 上搜索一般在第一頁(yè)的前幾條就能找到我們想要的答案。這就涉及到搜索引擎涉及到的另一個(gè)重要的算法: PageRank，它是 Google 對(duì)網(wǎng)頁(yè)排名進(jìn)行排名的一種算法，它以網(wǎng)頁(yè)之間的超鏈接個(gè)數(shù)和質(zhì)量作為主要因素粗略地分析網(wǎng)頁(yè)重要性以便對(duì)其進(jìn)行打分。我們一般在搜問題的時(shí)候，前面一兩個(gè)基本上都是 stackoverflow 網(wǎng)頁(yè)，說明 Google 認(rèn)為這個(gè)網(wǎng)頁(yè)的權(quán)重很高，因?yàn)檫@個(gè)網(wǎng)頁(yè)被全世界幾乎所有的程序員使用著，也就是說有無(wú)數(shù)個(gè)網(wǎng)頁(yè)指向此網(wǎng)站的鏈接，根據(jù) PageRank 算法，自然此網(wǎng)站權(quán)重就啦，恩，可以簡(jiǎn)單地這么認(rèn)為，實(shí)際上 PageRank 的計(jì)算需要用到大量的數(shù)學(xué)知識(shí)，畢竟此算法是 Google 的立身之本，大家如果有興趣，可以去網(wǎng)上多多了解一下。

完成以上步驟，搜索引擎對(duì)網(wǎng)頁(yè)的處理就完了，那么用戶輸入關(guān)鍵詞搜索引擎又是怎么給我們展示出結(jié)果的呢。

四、查詢

用戶輸入關(guān)鍵詞后，首先肯定是要經(jīng)過分詞器的處理。比如我輸入「中國(guó)人民」，假設(shè)分詞器分將其分為「中國(guó)」,「人民」兩個(gè)詞，接下來就用這個(gè)兩詞去倒排索引里查相應(yīng)的文檔

得到網(wǎng)頁(yè) id 后，我們分別去 doc_id.bin，doc_raw.bin 里提取出網(wǎng)頁(yè)的鏈接和內(nèi)容，按權(quán)重從大到小排列即可。

這里的權(quán)重除了和上文說的 PageRank 算法有關(guān)外，還與另外一個(gè)「 TF-IDF 」（https://zh.wikipedia.org/wiki/Tf-idf）算法有關(guān)，大家可以去了解一下。

另外相信大家在搜索框輸入搜索詞的時(shí)候，都會(huì)注意到底下會(huì)出現(xiàn)一串搜索提示詞，

如圖示：輸入 chin 這四個(gè)字母后，底下會(huì)出現(xiàn)一列提示詞。

如何實(shí)現(xiàn)的，這就不得不提到一種樹形結(jié)構(gòu)：Trie 樹。Trie 樹又叫字典樹、前綴樹（Prefix Tree）、單詞查找樹，是一種多叉樹結(jié)構(gòu)，如下圖所示：

這顆多叉樹表示了關(guān)鍵字集合 ["to"，"tea"，"ted"，"ten"，"a"，"i"，"in", "inn"]。從中可以看出 Trie 樹具有以下性質(zhì)：

1. 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符
2. 從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串
3. 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符互不相同

通常在實(shí)現(xiàn)的時(shí)候，會(huì)在節(jié)點(diǎn)結(jié)構(gòu)中設(shè)置一個(gè)標(biāo)志，用來標(biāo)記該結(jié)點(diǎn)處是否構(gòu)成一個(gè)單詞（關(guān)鍵字）。

另外我們不難發(fā)現(xiàn)一個(gè)規(guī)律，具有公共前綴的關(guān)鍵字（單詞），它們前綴部分在 Trie 樹中是相同的，這也是 Trie 樹被稱為前綴樹的原因，有了這個(gè)思路，我們不難設(shè)計(jì)出上文所述搜索時(shí)展示一串搜索提示詞的思路：

一般搜索引擎會(huì)維護(hù)一個(gè)詞庫(kù)，假設(shè)這個(gè)詞庫(kù)由所有搜索次數(shù)大于某個(gè)閾值（如 1000）的字符串組成，我們就可以用這個(gè)詞庫(kù)構(gòu)建一顆 Trie 樹，這樣當(dāng)用戶輸入字母的時(shí)候，就可以以這個(gè)字母作為前綴去 Trie 樹中查找，以上文中提到的 Trie 樹為例，則我們輸入「te」時(shí)，由于以「te」為前綴的單詞有 ["tea"，"ted"，"ted"，"ten"]，則在搜索引擎的搜索提示框中就可以展示這幾個(gè)字符串以供用戶選擇。

五、尋找熱門搜索字符串

Trie 樹除了作為前綴樹來實(shí)現(xiàn)搜索提示詞的功能外，還可以用來輔助尋找熱門搜索字符串，只要對(duì) Trie 樹稍加改造即可。假設(shè)我們要尋找最熱門的 10 個(gè)搜索字符串，則具體實(shí)現(xiàn)思路如下:

一般搜索引擎都會(huì)有專門的日志來記錄用戶的搜索詞，我們用用戶的這些搜索詞來構(gòu)建一顆  Trie 樹，但要稍微對(duì) Trie 樹進(jìn)行一下改造，上文提到，Trie 樹實(shí)現(xiàn)的時(shí)候，可以在節(jié)點(diǎn)中設(shè)置一個(gè)標(biāo)志，用來標(biāo)記該結(jié)點(diǎn)處是否構(gòu)成一個(gè)單詞，也可以把這個(gè)標(biāo)志改成以節(jié)點(diǎn)為終止字符的搜索字符串個(gè)數(shù)，每個(gè)搜索字符串在 Trie 樹遍歷，在遍歷的最后一個(gè)結(jié)點(diǎn)上把字符串個(gè)數(shù)加 1，即可統(tǒng)計(jì)出每個(gè)字符串被搜索了多少次（根節(jié)點(diǎn)到結(jié)點(diǎn)經(jīng)過的路徑即為搜索字符串），然后我們?cè)倬S護(hù)一個(gè)有 10 個(gè)節(jié)點(diǎn)的小頂堆（堆頂元素比所有其他元素值都小，如下圖示）

如圖示：小頂堆中堆頂元素比其他任何元素都小

依次遍歷 Trie 樹的節(jié)點(diǎn)，將節(jié)點(diǎn)（字符串+次數(shù)）傳給小頂堆，根據(jù)搜索次數(shù)不斷調(diào)整小頂堆，這樣遍歷完 Trie 樹的節(jié)點(diǎn)后，小頂堆里的 10 個(gè)節(jié)點(diǎn)即是最熱門的搜索字符串。

總結(jié)

本文簡(jiǎn)述了搜索引擎的工作原理，相信大家看完后對(duì)其工作原理應(yīng)該有了比較清醒的認(rèn)識(shí)，我們可以看到，搜索引擎中用到了很多經(jīng)典的數(shù)據(jù)結(jié)構(gòu)和算法，所以現(xiàn)在大家應(yīng)該能明白為啥 Google, 百度這些公司對(duì)候選人的算法要求這么高了。

本文只是介紹了搜索引擎的基本工作原理，要深入了解還需多查資料了解哦。