編輯導(dǎo)讀：我們每天都在用的搜索引擎，看似簡(jiǎn)單，其實(shí)背后的技術(shù)細(xì)節(jié)非常復(fù)雜。本文將從六個(gè)方面分析搜索引擎是如何工作的，希望對(duì)你有幫助。

我們每天都在用 Google, 百度這些搜索引擎，那大家有沒(méi)想過(guò)搜索引擎是如何實(shí)現(xiàn)的呢？看似簡(jiǎn)單的搜索其實(shí)技術(shù)細(xì)節(jié)非常復(fù)雜，說(shuō)搜索引擎是 IT 皇冠上的明珠也不為過(guò)，今天我們來(lái)就來(lái)簡(jiǎn)單看一下搜索引擎的原理，看看它是如何工作的。

• 網(wǎng)頁(yè)抓?。核阉饕嫱ㄟ^(guò)爬蟲(chóng)將網(wǎng)頁(yè)爬取，獲得頁(yè)面 HTML 代碼存入數(shù)據(jù)庫(kù)中。
• 預(yù)處理：索引程序?qū)ψト?lái)的頁(yè)面數(shù)據(jù)進(jìn)行文字提取，中文分詞，(倒排)索引等處理，以備排名程序使用。
• 排序：排名程序調(diào)用索引數(shù)據(jù)庫(kù)數(shù)據(jù)，計(jì)算網(wǎng)頁(yè)的相關(guān)性。其中最著名的是Google搜索引擎的核心排序算法：PageRank。
• 查詢：用戶輸入關(guān)鍵詞后，首先肯定是要經(jīng)過(guò)分詞器的處理。比如我輸入「中國(guó)人民」，假設(shè)分詞器分將其分為「中國(guó)」,「人民」兩個(gè)詞，接下來(lái)就用這個(gè)兩詞去倒排索引里查相應(yīng)的文檔。

我們重點(diǎn)來(lái)看一下第一步：網(wǎng)頁(yè)抓取。

這一步的大致操作如下：給爬蟲(chóng)分配一組起始的網(wǎng)頁(yè)，我們知道網(wǎng)頁(yè)里其實(shí)也包含了很多超鏈接，爬蟲(chóng)爬取一個(gè)網(wǎng)頁(yè)后，解析提取出這個(gè)網(wǎng)頁(yè)里的所有超鏈接，再依次爬取出這些超鏈接，再提取網(wǎng)頁(yè)超鏈接。如此不斷重復(fù)就能不斷根據(jù)超鏈接提取網(wǎng)頁(yè)。

如下圖示：

如上所示，最終構(gòu)成了一張圖，于是問(wèn)題就轉(zhuǎn)化為了如何遍歷這張圖。

一、什么是圖的遍歷？

從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。

遍歷的實(shí)質(zhì)是找每個(gè)頂點(diǎn)的連接點(diǎn)的過(guò)程。

圖的特點(diǎn)：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其他頂點(diǎn)想通，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。

以逛公園為例，從公園入口v1出發(fā)，如何用最短的路程逛完公園全部7個(gè)景點(diǎn)，這就是一個(gè)典型的圖的遍歷。

圖常用的遍歷方法有兩種：

1. 深度優(yōu)先搜索（Depth_First Search——DFS）
2. 廣度優(yōu)先搜索（Breadth_First Search——BFS）

二、什么是深度優(yōu)先搜索？

以經(jīng)典的迷宮圖來(lái)看看如何遍歷。

題目：如何從迷宮入口出發(fā)，點(diǎn)亮迷宮中所有的燈？

步驟一：從頂點(diǎn)（迷宮入口）開(kāi)始遍歷，它相鄰的頂點(diǎn)有向右和向下的兩盞燈，我們隨機(jī)選擇向右的那盞燈并將其點(diǎn)亮。

步驟二：以點(diǎn)亮后的這盞燈為頂點(diǎn)繼續(xù)遍歷。它相鄰的頂點(diǎn)有兩個(gè)：入口的燈和右下角的燈，由于入口的燈已點(diǎn)亮，我們只能點(diǎn)亮右下角的那盞燈。

步驟三：重復(fù)以上步驟，以被點(diǎn)亮的燈為頂點(diǎn)繼續(xù)遍歷，直至這條路走不通為止，用通俗的話來(lái)說(shuō)就是“把一條路走到黑”。如下圖：

步驟四：無(wú)路可走后，沿著原路返回，繼續(xù)尋找沒(méi)有被點(diǎn)亮的燈，直至把所有的燈全部點(diǎn)亮。至此，我們完整地實(shí)現(xiàn)了深度優(yōu)先搜索。如下圖：

總結(jié)：

深度優(yōu)先搜索的主要思路是：從圖中一個(gè)未訪問(wèn)的頂點(diǎn) V 開(kāi)始，沿著一條路一直走到底，然后從這條路盡頭的節(jié)點(diǎn)回退到上一個(gè)節(jié)點(diǎn)，再?gòu)牧硪粭l路開(kāi)始走到底……

不斷遞歸重復(fù)此過(guò)程，直到所有的頂點(diǎn)都遍歷完成，它的特點(diǎn)是不撞南墻不回頭，先走完一條路，再換一條路繼續(xù)走。

三、什么是廣度優(yōu)先搜索？

題目：如何從入口1出發(fā)，遍歷整顆樹(shù)？

步驟一：先遍歷節(jié)點(diǎn)1的所有節(jié)點(diǎn)——2，3，4。

步驟二：再分別遍歷節(jié)點(diǎn)2，3，4的所有節(jié)點(diǎn)——5，6，7，8。

步驟三：再分別遍歷節(jié)點(diǎn)5，6，7，8的所有節(jié)點(diǎn)——9，10。

總結(jié)：

具體思想：從圖中某頂點(diǎn)1出發(fā)，在訪問(wèn)了1之后依次訪問(wèn)1的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，并使得“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)先于后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)被訪問(wèn)”，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則需要另選一個(gè)未曾被訪問(wèn)過(guò)的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。

簡(jiǎn)單來(lái)說(shuō)，廣度優(yōu)先遍歷，指的是從圖的一個(gè)未遍歷的節(jié)點(diǎn)出發(fā)，先遍歷這個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，再依次遍歷每個(gè)相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。

所以廣度優(yōu)先遍歷也叫層序遍歷，先遍歷第一層(節(jié)點(diǎn) 1)，再遍歷第二層(節(jié)點(diǎn) 2，3，4)，第三層(5，6，7，8)，第四層(9，10)。

四、什么是棧？

棧是一種只能從表的一端存取數(shù)據(jù)且遵循 “先進(jìn)后出”?原則的線性存儲(chǔ)結(jié)構(gòu)。

例如，我們經(jīng)常使用瀏覽器在各種網(wǎng)站上查找信息。假設(shè)先瀏覽的頁(yè)面 A，然后關(guān)閉了頁(yè)面 A 跳轉(zhuǎn)到頁(yè)面 B，隨后又關(guān)閉頁(yè)面 B 跳轉(zhuǎn)到了頁(yè)面 C。而此時(shí)，我們?nèi)绻胫匦禄氐巾?yè)面 A，有兩個(gè)選擇：

1. 重新搜索找到頁(yè)面 A；
2. 使用瀏覽器的”回退”功能。瀏覽器會(huì)先回退到頁(yè)面 B，而后再回退到頁(yè)面 A。

而瀏覽器 “回退” 功能的實(shí)現(xiàn)，底層使用的就是棧存儲(chǔ)結(jié)構(gòu)。

五、什么是隊(duì)列？

與棧結(jié)構(gòu)不同的是，隊(duì)列的兩端都”開(kāi)口”，要求數(shù)據(jù)只能從一端進(jìn)，從另一端出。隊(duì)列中數(shù)據(jù)的進(jìn)出要遵循 “先進(jìn)先出” 的原則，即最先進(jìn)隊(duì)列的數(shù)據(jù)元素，同樣要最先出隊(duì)列。

隊(duì)列的應(yīng)用也很廣泛，只要滿足“先來(lái)先服務(wù)”特性的應(yīng)用均可采用隊(duì)列作為其數(shù)據(jù)組織方式。例如在多用戶系統(tǒng)中，多個(gè)用戶排成隊(duì)，分時(shí)地循環(huán)使用CPU和主存。

棧和隊(duì)列在圖的遍歷中的應(yīng)用：

深度優(yōu)先搜索由于是先入后出的算法，使用棧來(lái)實(shí)現(xiàn)。而廣度優(yōu)先搜索是先入先出的算法，使用隊(duì)列實(shí)現(xiàn)。

以二叉樹(shù)為例來(lái)看下如何用棧來(lái)實(shí)現(xiàn) DFS。

同樣以以上圖二叉樹(shù)為例來(lái)看看如何用隊(duì)列來(lái)實(shí)現(xiàn)廣度優(yōu)先遍歷。

六、如何抓取網(wǎng)頁(yè)？

回到開(kāi)篇提到的搜索引擎，我們來(lái)繼續(xù)看看網(wǎng)頁(yè)抓取的大致思路。

如果是廣度優(yōu)先遍歷：先依次爬取第一層的起始網(wǎng)頁(yè)，再依次爬取每個(gè)網(wǎng)頁(yè)里的超鏈接。

如果是深度優(yōu)先遍歷：先爬取起始網(wǎng)頁(yè) 1，再爬取此網(wǎng)頁(yè)里的鏈接，爬取完之后，再爬取起始網(wǎng)頁(yè) 2。

實(shí)際上爬蟲(chóng)是深度優(yōu)先與廣度優(yōu)先兩種策略一起用的，比如在起始網(wǎng)頁(yè)里，有些網(wǎng)頁(yè)比較重要(權(quán)重較高)，那就先對(duì)這個(gè)網(wǎng)頁(yè)做深度優(yōu)先遍歷，遍歷完之后再對(duì)其他(權(quán)重一樣的)起始網(wǎng)頁(yè)做廣度優(yōu)先遍歷。

本文由 @CARRIE 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來(lái)自Unsplash，基于CC0協(xié)議