原文連結
一、前言
我們每天都在用 Google, 百度這些搜尋引擎，那大家有沒想過搜尋引擎是如何實作的呢，看似簡單的搜尋其實技術細節非常複雜，說搜尋引擎是 IT 皇冠上的明珠也不為過，今天我們來就來簡單過一下搜尋引擎的原理，看看它是如何工作的，當然搜尋引擎博大精深，一篇文章不可能完全介紹完，我們隻會介紹它最重要的幾個步驟，不過萬變不離其宗，搜尋引擎都離不開這些重要步驟，剩下的無非是在其上添磚加瓦，是以掌握這些「關鍵路徑」，能很好地達到觀一斑而窺全貎的目的。
本文将會從以下幾個部分來介紹搜尋引擎，會深度剖析搜尋引擎的工作原理及其中用到的一些經典資料結構和算法，相信大家看了肯定有收獲。
- 搜尋引擎系統架構圖
- 搜尋引擎工作原理詳細剖析
二、搜尋引擎系統架構圖
搜尋引擎整體架構圖如下圖所示，大緻可以分為搜集，預處理，索引，查詢這四步，每一步的技術細節都很多，我們将在下文中詳細分析每一步的工作原理。
三、搜尋引擎工作原理詳細剖析
1. 搜集
爬蟲一開始是不知道該從哪裡開始爬起的，是以我們可以給它一組優質種子網頁的連結，比如新浪首頁，騰訊首頁等，這些首頁比較知名，在 Alexa 排名上也非常靠前，拿到這些優質種子網頁後，就對這些網頁通過廣度優先周遊不斷周遊這些網頁，爬取網頁内容，提取出其中的連結，不斷将其将入到待爬取隊列，然後爬蟲不斷地從 url 的待爬取隊列裡提取出 url 進行爬取，重複以上過程...
當然了，隻用一個爬蟲是不夠的，可以啟動多個爬蟲并行爬取，這樣速度會快很多。
（1）待爬取的 url 實作
待爬取 url 我們可以把它放到 Redis 裡，保證了高性能，需要注意的是，Redis 要開啟持久化功能，這樣支援斷點續爬，如果 Redis 挂掉了，重新開機之後由于有持續久功能，可以從上一個待爬的 url 開始重新爬。
（2）如何判重
如何避免網頁的重複爬取呢，我們需要對 url 進行去重操作，去重怎麼實作？可能有人說用散清單，将每個待抓取 url 存在散清單裡，每次要加入待爬取 url 時都通過這個散清單來判斷一下是否爬取過了，這樣做确實沒有問題，但我們需要注意到的是這樣需要會出巨大的空間代價，有多大，我們簡單算一下，假設有 10 億 url （不要覺得 10 億很大，像 Google, 百度這樣的搜尋引擎，它們要爬取的網頁量級比 10 億大得多），放在散清單裡，需要多大存儲空間呢？
我們假設每個網頁 url 平均長度 64 位元組，則 10 億個 url 大約需要 60 G 記憶體，如果用散清單實作的話，由于散清單為了避免過多的沖突，需要較小的裝載因子（假設哈希表要裝載 10 個元素，實際可能要配置設定 20 個元素的空間，以避免哈希沖突），同時不管是用鍊式存儲還是用紅黑樹來處理沖突，都要存儲指針，各種這些加起來所需記憶體可能會超過 100 G，再加上沖突時需要在連結清單中比較字元串，性能上也是一個損耗，當然 100 G 對大型搜尋引擎來說不是什麼大問題，但其實還有一種方案可以實作遠小于 100 G 的記憶體：布隆過濾器。
針對 10 億個 url，我們配置設定 100 億個 bit，大約 1.2 G, 相比 100 G 記憶體，提升了近百倍！可見技術方案的合理選擇能很好地達到降本增效的效果。
當然有人可能會提出疑問，布隆過濾器可能會存在誤判的情況，即某個值經過布隆過濾器判斷不存在，那這個值肯定不存在，但如果經布隆過濾器判斷存在，那這個值不一定存在,針對這種情況我們可以通過調整布隆過濾器的哈希函數或其底層的位圖大小來盡可能地降低誤判的機率，但如果誤判還是發生了呢，此時針對這種 url 就不爬好了，畢竟網際網路上這麼多網頁，少爬幾個也無妨。
（3）網頁的存儲檔案: doc_raw.bin
爬完網頁，網頁該如何存儲呢，有人說一個網頁存一個檔案不就行了，如果是這樣，10 億個網頁就要存 10 億個檔案，一般的檔案系統是不支援的，是以一般是把網頁内容存儲在一個檔案（假設為 doc_raw.bin）中，如下
當然一般的檔案系統對單個檔案的大小也是有限制的，比如 1 G，那在檔案超過 1 G 後再建立一個好了。
圖中網頁 id 是怎麼生成的，顯然一個 url 對應一個網頁 id，是以我們可以增加一個發号器，每爬取完一個網頁，發号器給它配置設定一個 id，将網頁 id 與 url 存儲在一個檔案裡，假設命名為 doc_id.bin,如下
2. 預處理
爬取完一個網頁後我們需要對其進行預處理，我們拿到的是網頁的 html 代碼，需要把 ,,，找到之後，把起始終止标簽及其中的内容全部去掉即可。
做完以上步驟後，我們也要把其它的 html 标簽去掉（标簽裡的内容保留），因為我們最終要處理的是純内容（内容裡面包含使用者要搜尋的關鍵詞）
3. 分詞并建立反向索引
拿到上述步驟處理過的内容後，我們需要将這些内容進行分詞，啥叫分詞呢，就是将一段文本切分成一個個的詞。比如 「I am a chinese」分詞後，就有 「I」,「am」,「a」,「chinese」這四個詞,從中也可以看到，英文分詞相對比較簡單，每個單詞基本是用空格隔開的，隻要以空格為分隔符切割字元串基本可達到分詞效果，但是中文不一樣，詞與詞之類沒有空格等字元串分割，比較難以分割。以「我來到北京清華大學」為例，不同的模式産生的分詞結果不一樣，以 github 上有名的 jieba 分詞開源庫為例，它有如下幾種分詞模式
【全模式】: 我/ 來到/ 北京/ 清華/ 清華大學/ 華大/ 大學
【精确模式】: 我/ 來到/ 北京/ 清華大學
【新詞識别】：他, 來到, 了, 網易, 杭研, 大廈
【搜尋引擎模式】： 小明, 碩士, 畢業, 于, 中國, 科學, 學院, 科學院, 中國科學院, 計算, 計算所, 後, 在, 日本, 京都, 大學, 日本京都大學, 深造 分詞一般是根據現成的詞庫來進行比對，比如詞庫中有「中國」這個詞，用處理過的網頁文本進行比對即可。當然在分詞之前我們要把一些無意義的停止詞如「的」,「地」,「得」先給去掉。
經過分詞之後我們得到了每個分詞與其文本的關系，如下
細心的你一定發現了，不同的網頁内容有可能出現同樣的分詞，是以我們把具有相同分詞的網頁歸在一起，如下所示
這樣我們在搜「大學」的時候找到「大學」對應的行，就能找到所有包含有「大學」的文檔 id 了。
看到以上「分詞」+「反向索引」的處理流程，大家想到了什麼？沒錯，這不就是 ElasticSearch 搜尋引擎幹的事嗎，也是 ES 能達到毫秒級響應的關鍵！
這裡還有一個問題，根據某個詞語擷取得了一組網頁的 id 之後，在結果展示上，哪些網頁應該排在最前面呢，為啥我們在 Google 上搜尋一般在第一頁的前幾條就能找到我們想要的答案。這就涉及到搜尋引擎涉及到的另一個重要的算法: PageRank，它是 Google 對網頁排名進行排名的一種算法，它以網頁之間的超連結個數和品質作為主要因素粗略地分析網頁重要性以便對其進行打分。我們一般在搜問題的時候，前面一兩個基本上都是 stackoverflow 網頁，說明 Google 認為這個網頁的權重很高，因為這個網頁被全世界幾乎所有的程式員使用着，也就是說有無數個網頁指向此網站的連結，根據 PageRank 算法，自然此網站權重就啦，恩，可以簡單地這麼認為，實際上 PageRank 的計算需要用到大量的數學知識，畢竟此算法是 Google 的立身之本，大家如果有興趣，可以去網上多多了解一下。
完成以上步驟，搜尋引擎對網頁的處理就完了，那麼使用者輸入關鍵詞搜尋引擎又是怎麼給我們展示出結果的呢。
4. 查詢
使用者輸入關鍵詞後，首先肯定是要經過分詞器的處理。比如我輸入「中國人民」，假設分詞器分将其分為「中國」,「人民」兩個詞，接下來就用這個兩詞去反向索引裡查相應的文檔
得到網頁 id 後，我們分别去 doc_id.bin，doc_raw.bin 裡提取出網頁的連結和内容，按權重從大到小排列即可。
這裡的權重除了和上文說的 PageRank 算法有關外，還與另外一個「 TF-IDF 」（
https://zh.wikipedia.org/wiki/Tf-idf）算法有關，大家可以去了解一下。
另外相信大家在搜尋框輸入搜尋詞的時候，都會注意到底下會出現一串搜尋提示詞，
如圖示：輸入 chin 這四個字母後，底下會出現一列提示詞。
如何實作的，這就不得不提到一種樹形結構：Trie 樹。Trie 樹又叫字典樹、字首樹（Prefix Tree）、單詞查找樹，是一種多叉樹結構，如下圖所示：
這顆多叉樹表示了關鍵字集合 ["to"，"tea"，"ted"，"ten"，"a"，"i"，"in", "inn"]。從中可以看出 Trie 樹具有以下性質：
- 根節點不包含字元，除根節點外的每一個子節點都包含一個字元
- 從根節點到某一個節點，路徑上經過的字元連接配接起來，為該節點對應的字元串
- 每個節點的所有子節點包含的字元互不相同
通常在實作的時候，會在節點結構中設定一個标志，用來标記該結點處是否構成一個單詞（關鍵字）。
另外我們不難發現一個規律，具有公共字首的關鍵字（單詞），它們字首部分在 Trie 樹中是相同的，這也是 Trie 樹被稱為字首樹的原因，有了這個思路，我們不難設計出上文所述搜尋時展示一串搜尋提示詞的思路：
一般搜尋引擎會維護一個詞庫，假設這個詞庫由所有搜尋次數大于某個門檻值（如 1000）的字元串組成，我們就可以用這個詞庫建構一顆 Trie 樹，這樣當使用者輸入字母的時候，就可以以這個字母作為字首去 Trie 樹中查找，以上文中提到的 Trie 樹為例，則我們輸入「te」時，由于以「te」為字首的單詞有 ["tea"，"ted"，"ted"，"ten"]，則在搜尋引擎的搜尋提示框中就可以展示這幾個字元串以供使用者選擇。
5. 尋找熱門搜尋字元串
Trie 樹除了作為字首樹來實作搜尋提示詞的功能外，還可以用來輔助尋找熱門搜尋字元串，隻要對 Trie 樹稍加改造即可。假設我們要尋找最熱門的 10 個搜尋字元串，則具體實作思路如下:
一般搜尋引擎都會有專門的日志來記錄使用者的搜尋詞，我們用使用者的這些搜尋詞來建構一顆 Trie 樹，但要稍微對 Trie 樹進行一下改造，上文提到，Trie 樹實作的時候，可以在節點中設定一個标志，用來标記該結點處是否構成一個單詞，也可以把這個标志改成以節點為終止字元的搜尋字元串個數，每個搜尋字元串在 Trie 樹周遊，在周遊的最後一個結點上把字元串個數加 1，即可統計出每個字元串被搜尋了多少次（根節點到結點經過的路徑即為搜尋字元串），然後我們再維護一個有 10 個節點的小頂堆（堆頂元素比所有其他元素值都小，如下圖示）
如圖示：小頂堆中堆頂元素比其他任何元素都小
依次周遊 Trie 樹的節點，将節點（字元串+次數）傳給小頂堆，根據搜尋次數不斷調整小頂堆，這樣周遊完 Trie 樹的節點後，小頂堆裡的 10 個節點即是最熱門的搜尋字元串。
四、總結
本文簡述了搜尋引擎的工作原理，相信大家看完後對其工作原理應該有了比較清醒的認識，我們可以看到，搜尋引擎中用到了很多經典的資料結構和算法，是以現在大家應該能明白為啥 Google, 百度這些公司對候選人的算法要求這麼高了。
本文隻是介紹了搜尋引擎的基本工作原理，要深入了解還需多查資料了解哦。
來源 | 碼海
作者 | 碼海