來源公眾號：碼海
作者：碼海
前言
我們每天都在用 Google, 百度這些搜索引擎腰涧，那大家有沒想過搜索引擎是如何實現(xiàn)的呢荒典，看似簡單的搜索其實技術(shù)細節(jié)非常復雜尝蠕，說搜索引擎是 IT 皇冠上的明珠也不為過礁击，今天我們來就來簡單過一下搜索引擎的原理庄萎，看看它是如何工作的迹恐，當然搜索引擎博大精深挣惰，一篇文章不可能完全介紹完，我們只會介紹它最重要的幾個步驟殴边，不過萬變不離其宗憎茂，搜索引擎都離開這些重要步驟，剩下的無非是在其上添磚加瓦锤岸，所以掌握這些「關(guān)鍵路徑」竖幔，能很好地達到觀一斑而窺全貎的目的。
本文將會從以下幾個部分來介紹搜索引擎是偷，會深度剖析搜索引擎的工作原理及其中用到的一些經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法拳氢，相信大家看了肯定有收獲。
- 搜索引擎系統(tǒng)架構(gòu)圖
- 搜索引擎工作原理詳細剖析
搜索引擎系統(tǒng)架構(gòu)圖
搜索引擎整體架構(gòu)圖如下圖所示蛋铆，大致可以分為搜集馋评，預處理，索引刺啦，查詢這四步留特，每一步的技術(shù)細節(jié)都很多，我們將在下文中詳細分析每一步的工作原理。
搜索引擎工作原理詳細剖析
一磕秤、搜集
爬蟲一開始是不知道該從哪里開始爬起的乳乌，所以我們可以給它一組優(yōu)質(zhì)種子網(wǎng)頁的鏈接，比如新浪主頁市咆，騰訊主頁等汉操，這些主頁比較知名，在 Alexa 排名上也非趁衫迹靠前磷瘤，拿到這些優(yōu)質(zhì)種子網(wǎng)頁后，就對這些網(wǎng)頁通過廣度優(yōu)先遍歷不斷遍歷這些網(wǎng)頁搜变，爬取網(wǎng)頁內(nèi)容采缚，提取出其中的鏈接，不斷將其將入到待爬取隊列挠他，然后爬蟲不斷地從 url 的待爬取隊列里提取出 url 進行爬取扳抽，重復以上過程...
當然了，只用一個爬蟲是不夠的殖侵，可以啟動多個爬蟲并行爬取贸呢，這樣速度會快很多。
1拢军、待爬取的 url 實現(xiàn)
待爬取 url 我們可以把它放到 Redis 里楞陷，保證了高性能，需要注意的是茉唉，Redis要開啟持久化功能固蛾，這樣支持斷點續(xù)爬，如果 Redis 掛掉了度陆，重啟之后由于有持續(xù)久功能艾凯，可以從上一個待爬的 url 開始重新爬。
2懂傀、如何判重
如何避免網(wǎng)頁的重復爬取呢览芳，我們需要對 url 進行去重操作，去重怎么實現(xiàn)鸿竖？可能有人說用散列表沧竟，將每個待抓取 url 存在散列表里，每次要加入待爬取 url 時都通過這個散列表來判斷一下是否爬取過了缚忧，這樣做確實沒有問題悟泵，但我們需要注意到的是這樣需要會出巨大的空間代價，有多大闪水，我們簡單算一下糕非，假設(shè)有 10 億 url （不要覺得 10 億很大，像 Google, 百度這樣的搜索引擎，它們要爬取的網(wǎng)頁量級比 10 億大得多）朽肥，放在散列表里禁筏，需要多大存儲空間呢？
我們假設(shè)每個網(wǎng)頁 url 平均長度 64 字節(jié)衡招，則 10 億個 url 大約需要 60 G 內(nèi)存篱昔，如果用散列表實現(xiàn)的話，由于散列表為了避免過多的沖突始腾，需要較小的裝載因子（假設(shè)哈希表要裝載 10 個元素州刽，實際可能要分配 20 個元素的空間，以避免哈希沖突）浪箭，同時不管是用鏈式存儲還是用紅黑樹來處理沖突穗椅，都要存儲指針，各種這些加起來所需內(nèi)存可能會超過 100 G奶栖，再加上沖突時需要在鏈表中比較字符串匹表，性能上也是一個損耗，當然 100 G 對大型搜索引擎來說不是什么大問題宣鄙，但其實還有一種方案可以實現(xiàn)遠小于 100 G 的內(nèi)存：布隆過濾器袍镀。
針對 10 億個 url，我們分配 100 億個 bit框冀，大約 1.2 G, 相比 100 G 內(nèi)存，提升了近百倍敏簿！可見技術(shù)方案的合理選擇能很好地達到降本增效的效果明也。
當然有人可能會提出疑問，布隆過濾器可能會存在誤判的情況惯裕，即某個值經(jīng)過布隆過濾器判斷不存在温数，那這個值肯定不存在，但如果經(jīng)布隆過濾器判斷存在蜻势，那這個值不一定存在,針對這種情況我們可以通過調(diào)整布隆過濾器的哈希函數(shù)或其底層的位圖大小來盡可能地降低誤判的概率撑刺，但如果誤判還是發(fā)生了呢，此時針對這種 url 就不爬好了握玛，畢竟互聯(lián)網(wǎng)上這么多網(wǎng)頁够傍，少爬幾個也無妨。
3挠铲、網(wǎng)頁的存儲文件: doc_raw.bin
爬完網(wǎng)頁冕屯，網(wǎng)頁該如何存儲呢，有人說一個網(wǎng)頁存一個文件不就行了拂苹，如果是這樣安聘，10 億個網(wǎng)頁就要存 10 億個文件，一般的文件系統(tǒng)是不支持的，所以一般是把網(wǎng)頁內(nèi)容存儲在一個文件（假設(shè)為 doc_raw.bin）中浴韭，如下
當然一般的文件系統(tǒng)對單個文件的大小也是有限制的丘喻，比如 1 G，那在文件超過 1 G 后再新建一個好了念颈。
圖中網(wǎng)頁 id 是怎么生成的泉粉，顯然一個 url 對應一個網(wǎng)頁 id，所以我們可以增加一個發(fā)號器舍肠，每爬取完一個網(wǎng)頁搀继，發(fā)號器給它分配一個 id，將網(wǎng)頁 id 與 url 存儲在一個文件里翠语，假設(shè)命名為 doc_id.bin,如下
二叽躯、預處理
爬取完一個網(wǎng)頁后我們需要對其進行預處理，我們拿到的是網(wǎng)頁的 html 代碼肌括，需要把 <script>,<style>,<option> 這些無用的標簽及標簽包含的內(nèi)容給去掉点骑，怎么查找是個學問，可能有人會說用 BF 谍夭，KMP 等算法黑滴，這些算法確實可以，不過這些算法屬于單模式串匹配算法紧索，查詢單個字段串效率確實不錯袁辈，但我們想要一次性查出<script>,<style>,<option>這些字段串，有啥好的方法不珠漂，答案是用AC 自動機多模式串匹配算法晚缩，可以高效一次性找出幾個待查找的字段串，有多高效媳危，時間復雜度接近 0(n)荞彼！關(guān)于 AC 自動機多模式匹配算法的原理不展開介紹，大家可以去網(wǎng)上搜搜看待笑， 這里只是給大家介紹一下思路鸣皂。
找到這些標簽的起始位置后，剩下的就簡單了暮蹂，接下來對每個這些標簽都查找其截止標簽 </script>,</style>,</option>寞缝，找到之后，把起始終止標簽及其中的內(nèi)容全部去掉即可仰泻。
做完以上步驟后第租，我們也要把其它的 html 標簽去掉（標簽里的內(nèi)容保留），因為我們最終要處理的是純內(nèi)容（內(nèi)容里面包含用戶要搜索的關(guān)鍵詞）
三我纪、分詞并創(chuàng)建倒排索引
拿到上述步驟處理過的內(nèi)容后慎宾，我們需要將這些內(nèi)容進行分詞丐吓，啥叫分詞呢，就是將一段文本切分成一個個的詞趟据。比如 「I am a chinese」分詞后券犁，就有 「I」,「am」,「a」,「chinese」這四個詞,從中也可以看到，英文分詞相對比較簡單汹碱，每個單詞基本是用空格隔開的粘衬，只要以空格為分隔符切割字符串基本可達到分詞效果，但是中文不一樣咳促，詞與詞之類沒有空格等字符串分割泵肄，比較難以分割互妓。以「我來到北京清華大學」為例，不同的模式產(chǎn)生的分詞結(jié)果不一樣，以 github 上有名的 jieba 分詞開源庫以例泞莉，它有如下幾種分詞模式
【全模式】: 我/ 來到/ 北京/ 清華/ 清華大學/ 華大/ 大學
【精確模式】: 我/ 來到/ 北京/ 清華大學
【新詞識別】：他, 來到, 了, 網(wǎng)易, 杭研, 大廈
【搜索引擎模式】： 小明, 碩士, 畢業(yè), 于, 中國, 科學, 學院, 科學院, 中國科學院, 計算, 計算所, 后, 在, 日本, 京都, 大學, 日本京都大學, 深造
分詞一般是根據(jù)現(xiàn)成的詞庫來進行匹配私杜，比如詞庫中有「中國」這個詞奠涌，用處理過的網(wǎng)頁文本進行匹配即可固灵。當然在分詞之前我們要把一些無意義的停止詞如「的」,「地」,「得」先給去掉。
經(jīng)過分詞之后我們得到了每個分詞與其文本的關(guān)系轴术，如下
細心的你一定發(fā)現(xiàn)了难衰，不同的網(wǎng)頁內(nèi)容有可能出現(xiàn)同樣的分詞，所以我們把具有相同分詞的網(wǎng)頁歸在一起逗栽，如下所示
這樣我們在搜「大學」的時候找到「大學」對應的行盖袭，就能找到所有包含有「大學」的文檔 id 了。
看到以上「分詞」+「倒排索引」的處理流程彼宠，大家想到了什么鳄虱？沒錯，這不就是 ElasticSearch 搜索引擎干的事嗎兵志，也是 ES 能達到毫秒級響應的關(guān)鍵醇蝴！
這里還有一個問題宣肚，根據(jù)某個詞語獲取得了一組網(wǎng)頁的 id 之后想罕，在結(jié)果展示上，哪些網(wǎng)頁應該排在最前面呢霉涨，為啥我們在 Google 上搜索一般在第一頁的前幾條就能找到我們想要的答案按价。這就涉及到搜索引擎涉及到的另一個重要的算法: PageRank，它是 Google 對網(wǎng)頁排名進行排名的一種算法笙瑟，它以網(wǎng)頁之間的超鏈接個數(shù)和質(zhì)量作為主要因素粗略地分析網(wǎng)頁重要性以便對其進行打分楼镐。我們一般在搜問題的時候，前面一兩個基本上都是 stackoverflow 網(wǎng)頁往枷，說明 Google 認為這個網(wǎng)頁的權(quán)重很高框产，因為這個網(wǎng)頁被全世界幾乎所有的程序員使用著凄杯，也就是說有無數(shù)個網(wǎng)頁指向此網(wǎng)站的鏈接，根據(jù) PageRank 算法秉宿，自然此網(wǎng)站權(quán)重就啦戒突，恩，可以簡單地這么認為描睦，實際上 PageRank 的計算需要用到大量的數(shù)學知識膊存，畢竟此算法是 Google 的立身之本，大家如果有興趣忱叭，可以去網(wǎng)上多多了解一下隔崎。
完成以上步驟，搜索引擎對網(wǎng)頁的處理就完了韵丑，那么用戶輸入關(guān)鍵詞搜索引擎又是怎么給我們展示出結(jié)果的呢爵卒。
四、查詢
用戶輸入關(guān)鍵詞后埂息，首先肯定是要經(jīng)過分詞器的處理技潘。比如我輸入「中國人民」，假設(shè)分詞器分將其分為「中國」,「人民」兩個詞千康，接下來就用這個兩詞去倒排索引里查相應的文檔
得到網(wǎng)頁 id 后享幽，我們分別去 doc_id.bin，doc_raw.bin 里提取出網(wǎng)頁的鏈接和內(nèi)容拾弃，按權(quán)重從大到小排列即可值桩。
這里的權(quán)重除了和上文說的 PageRank 算法有關(guān)外，還與另外一個「 TF-IDF 」（https://zh.wikipedia.org/wiki/Tf-idf）算法有關(guān)豪椿，大家可以去了解一下奔坟。
另外相信大家在搜索框輸入搜索詞的時候，都會注意到底下會出現(xiàn)一串搜索提示詞搭盾，
如圖示：輸入 chin 這四個字母后咳秉，底下會出現(xiàn)一列提示詞。
如何實現(xiàn)的鸯隅，這就不得不提到一種樹形結(jié)構(gòu)：Trie 樹澜建。Trie 樹又叫字典樹、前綴樹（Prefix Tree）蝌以、單詞查找樹炕舵，是一種多叉樹結(jié)構(gòu)，如下圖所示：
這顆多叉樹表示了關(guān)鍵字集合 ["to"跟畅，"tea"咽筋，"ted"，"ten"徊件，"a"奸攻，"i"蒜危，"in", "inn"]。從中可以看出 Trie 樹具有以下性質(zhì)：
- 根節(jié)點不包含字符睹耐，除根節(jié)點外的每一個子節(jié)點都包含一個字符
- 從根節(jié)點到某一個節(jié)點舰褪，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應的字符串
- 每個節(jié)點的所有子節(jié)點包含的字符互不相同
通常在實現(xiàn)的時候疏橄，會在節(jié)點結(jié)構(gòu)中設(shè)置一個標志占拍，用來標記該結(jié)點處是否構(gòu)成一個單詞（關(guān)鍵字）。
另外我們不難發(fā)現(xiàn)一個規(guī)律捎迫，具有公共前綴的關(guān)鍵字（單詞）晃酒，它們前綴部分在 Trie 樹中是相同的，這也是 Trie 樹被稱為前綴樹的原因窄绒，有了這個思路贝次，我們不難設(shè)計出上文所述搜索時展示一串搜索提示詞的思路：
一般搜索引擎會維護一個詞庫，假設(shè)這個詞庫由所有搜索次數(shù)大于某個閾值（如 1000）的字符串組成彰导，我們就可以用這個詞庫構(gòu)建一顆 Trie 樹蛔翅，這樣當用戶輸入字母的時候，就可以以這個字母作為前綴去 Trie 樹中查找位谋，以上文中提到的 Trie 樹為例山析，則我們輸入「te」時，由于以「te」為前綴的單詞有 ["tea"掏父，"ted"笋轨，"ted"，"ten"]赊淑，則在搜索引擎的搜索提示框中就可以展示這幾個字符串以供用戶選擇爵政。
五、尋找熱門搜索字符串
Trie 樹除了作為前綴樹來實現(xiàn)搜索提示詞的功能外陶缺，還可以用來輔助尋找熱門搜索字符串钾挟，只要對 Trie 樹稍加改造即可。假設(shè)我們要尋找最熱門的 10 個搜索字符串饱岸，則具體實現(xiàn)思路如下:
一般搜索引擎都會有專門的日志來記錄用戶的搜索詞掺出，我們用用戶的這些搜索詞來構(gòu)建一顆 Trie 樹，但要稍微對 Trie 樹進行一下改造伶贰，上文提到蛛砰，Trie 樹實現(xiàn)的時候罐栈，可以在節(jié)點中設(shè)置一個標志黍衙，用來標記該結(jié)點處是否構(gòu)成一個單詞，也可以把這個標志改成以節(jié)點為終止字符的搜索字符串個數(shù)荠诬，每個搜索字符串在 Trie 樹遍歷琅翻，在遍歷的最后一個結(jié)點上把字符串個數(shù)加 1位仁，即可統(tǒng)計出每個字符串被搜索了多少次（根節(jié)點到結(jié)點經(jīng)過的路徑即為搜索字符串），然后我們再維護一個有 10 個節(jié)點的小頂堆（堆頂元素比所有其他元素值都小方椎，如下圖示）
如圖示：小頂堆中堆頂元素比其他任何元素都小
依次遍歷 Trie 樹的節(jié)點聂抢，將節(jié)點（字符串+次數(shù)）傳給小頂堆，根據(jù)搜索次數(shù)不斷調(diào)整小頂堆棠众，這樣遍歷完 Trie 樹的節(jié)點后琳疏，小頂堆里的 10 個節(jié)點對應的字符串即是最熱門的搜索字符串。
總結(jié)
本文簡述了搜索引擎的工作原理闸拿，相信大家看完后對其工作原理應該有了比較清醒的認識空盼，我們可以看到，搜索引擎中用到了很多經(jīng)典的數(shù)據(jù)結(jié)構(gòu)和算法新荤，所以現(xiàn)在大家應該能明白為啥 Google, 百度這些公司對候選人的算法要求這么高了揽趾。
