騰訊面試題: 百度搜索為什麼那麼快?

blank

騰訊面試題: 百度搜索為什麼那麼快?

我還記得去年面騰訊時,面試官最後一個問題是:百度/google的搜索為什麼那麼快?

這個問題我懵了,我從來沒想過,搜素引擎的原理是什麼

然後我回答:百度爬取了各個網站的訊息,然後進行排序,當輸入關鍵詞的時候進行文檔比對...... 巴拉巴拉

面試官:這不是我想要的答案

我內心

這個問題我一直耿耿於懷,終於今天,我把他寫出來,以後再問,我直接把這篇文章甩給他!!!

兩個字:倒排,將貫穿整篇文章,也是面試官想要的答案

首先我們知道,百度肯定是有爬蟲,到處爬取網頁,進行某種處理。 然後通過你輸入的關鍵詞進行某種計算再返回給你的

目錄

某種處理

某種計算

兩次遍曆法

排序法

我們先來看看什麼是某種處理

某種處理

當百度爬取了海量網頁後,每一個網頁我們稱為"文檔",不可能就雜亂無章的放著,它使用了文檔集合,就是類似的文檔放在一個集合中

那什麼樣的文檔算類似呢? 相信你猜到了,文檔中有相同關鍵字的就可以放在一個集合中

來舉例說明

假設全世界只有下面5個文檔(網頁),文檔內容也很簡單,就一句話(注意是內容,不是標題)

blank

百度爬取后,將他們進行編號,然後對文檔進行掃描分詞,因為百度內部有詞庫,匹配上的詞將被切分,所以文檔1號將被切分為【谷歌,地圖,之父,跳槽,FaceBook】,後面的文檔也一樣,然後對切分出來的單詞進行倒排處理,形成倒排列表

blank

啥是倒排處理? 右邊這堆雜亂無章的數字咋來的? 別急,仔細看,1號單詞"谷歌"是不是在1,2,3,4,5號文檔都出現過? 9號單詞「離開」是不是只在3號文檔出現過?

是的,倒排列表所做的,就是保存對應單詞所出現過的文檔編號

我想你開始明白他的目的了,當我們搜索"谷歌"的時候,他就會獲得"谷歌"這一單詞對應的倒排列表,知道哪些文檔包含他,然後將這些文檔提取出來返回給你,這就是一種單詞映射文檔的方法

但是,沒那麼簡單,因為只有這樣的話,我在一篇部落格上把所有的單詞都寫上,這樣雜亂無章的文章豈不是要被推薦給全體台灣人???

所以倒排列表還要保存下列訊息

blank

保留的訊息變成了二元組,比如16號單詞"網站"的(5:1),5表示出現的文檔編號,1表示出現的次數,也就是說,有了這個訊息,如果一個單詞在文檔中頻率越高(英文縮寫TF),搜素引擎就可以把他排在前面推給你

除了頻率,還有位置,比如"谷歌"就是在1號文檔中出現了一次的單詞,位置在第一個,用<1>表示

blank

可能到這你有點記不住有哪些網頁了,再看一遍比對下

blank

這樣子,搜素引擎就可以根據你的關鍵詞在倒排列表中找到含有這個關鍵詞的文檔集合,然後根據關鍵詞在文檔集合中各個文檔出現的頻率和位置綜合判斷返回給你排序后的文檔

上句話比較長,加粗部分連在一起讀意思不變

實際上很多搜尋引擎基本就是這樣做的,只不過各家還有別的參考標準,比如百度還會參考熱度,你的搜索記錄,還有網站給的錢(你懂的)等等綜合打分,按評分高低返回搜索結果的排序

上面的所以記錄處理好后都會存放在磁盤中,然後等你關鍵詞來后再調入記憶體

假設世界上只有5個文檔,那麼上面的東西完全夠了,但實際上,世界上有億萬個文檔,此時,問題的性質已經變了,不是找不找得到的問題,而是怎麼找更快,更准的問題,這需要演算法,也就是我們上面提到的某種計算

某種計算

第一個問題就是,詞庫那麼多,當你輸入「蘋果」的時候,百度如何將你的關鍵詞和他內部倒排列表的「蘋果」一詞聯繫起來?

計算機是不認識"蘋果"的,這裡,可以通過哈希的方法將"蘋果"轉換為一個編號

所謂哈希,即使將一個詞通過某種演算法映射為一個符號,比如"將單詞轉換為其長度"就是一種演算法,雖然很low,這樣"蘋果"就是2,"梨"就是1,不同的哈希演算法有不同的轉換結果,但是必然會有一個東西——哈希衝突,比如"桃子"也是2,此時,需要使用鏈表,也稱衝突表,將編號相同的單詞鏈在一起

blank

當我們搜索「蘋果」的時候,經過哈希計算,得知其編號為2,然後發現2中有一個鏈表,裡面可能保存著「蘋果」,「桃子」,「蘑菇」等,然後再遍歷鏈表找到蘋果即可

這裡和java8中的hashmap思想一致,不過鏈錶也會過長,所以可以使用別的數據結構代替,比如紅黑樹,b樹等

解決了第一個問題,我們就可以通過關鍵詞獲得他的Id,然後得到所建立的倒排列表了,比如"谷歌"

blank

第二個問題,由於文檔的數量龐大,我們獲取的文檔往往編號位數都很多,而不像上圖那樣1,2,3,4,5,導致倒排列表無謂的擴大,所以我們這裡進行作差

blank

就是後面的文檔編號減去前面的,在取文檔(從磁盤中讀取)的時候加回來即可

第三個問題,如何從磁盤中讀取文檔

現在我們已經有了倒排列表

可以有兩種方法從磁盤中讀取文檔

兩次遍曆法

第一遍,掃描文檔集合,找到文檔數量N, 文檔集合內所包含的不同單詞數M,和每個單詞出現的頻率DF(如下圖),以及一些別的必要訊息,這些東西所佔記憶體加起來,得到需要開闢的記憶體空間,

blank

同時這個空間是以單詞為單位劃分,比如「谷歌」一詞有5篇文檔,

第一遍主要就是確定要開闢多大的記憶體空間來顯示文檔

第二遍掃描,就是邊掃描,匹配對應的文檔編號(三元組中的第一個數),載入記憶體

但是這個方法有一個問題,那就是文檔集合有多大,記憶體就有多大,所以,很可能記憶體會溢出,不過都放在記憶體中速度也很快,這是一種空間換時間的方法

相信你發現了,但凡設計到讀取,一定有兩種以上的方法,空間優先或是時間優先,第二種就是時間換空間——排序法

排序法

現在我們只用固定大小的記憶體,如何從上圖中的倒排列表得知每個單詞對應的文章集合所需要的記憶體空間有多少呢?

我們需要解析文檔,構造(單詞ID,文檔ID,單詞頻率)三元組,然後進行排序,按單詞ID,文檔ID,單詞頻率先後排,最後如果規定的記憶體滿了,就將這些三元組通通寫入一個臨時檔A中

blank

為什麼要這樣呢? 想想看,如果我們最後拿到了一個(單詞A,文檔A,單詞頻率),我們就可以很輕鬆的知道一個單詞對應哪個文檔,和對應的頻率,

也就是一個三元組告訴我們單詞A對應的文檔A,另一個三元組告訴我們單詞A對應文檔B......,這些三元組加起來我們就知道了單詞A對應的文檔集合,就可以知道他需要多少記憶體空間來填補這些文檔了

可能解析50個文檔後規定的記憶體就滿了,然後把這些三元組們寫入磁碟臨時檔A,就可以再讀下一篇50個文檔了,注意,詞典是不斷增加的,比如前50個文檔只有上面7個單詞,後50個文檔可能出現了別的單詞,此時要插入詞典中,詞典一直在記憶體

這樣,只用固定大小的記憶體就可以50一批的解析完所有文檔,寫入了一個個的臨時檔A,B,C,D,再將這些臨時文件合併,就是把他們分別讀入記憶體中的緩衝區,合成最終索引后再寫入磁碟,這樣通過最終索引就知道有哪些單詞對應多少文檔,還有頻率,然後根據這些開闢內存空間讀取進入內存返回給你即可

blank

排序法敘述起來比較複雜,但是其實理解起來很簡單,耐心讀一定能懂哦

限於篇幅,這裡只講了你輸入關鍵詞到他返回給你大致的網頁的過程,其實,百度如何爬取網頁? 如何保證網頁的時效性? 如何篩選垃圾網站? 如何分散式存儲海量網頁? 如何應對超長關鍵字查詢? 如何根據使用者歷史記錄精準分析用戶意圖?

等等都需要大量的篇幅詳解,一篇文章不可能講完,下次有機會再分析吧

————————————————

版權聲明:本文為CSDN博主「小松與蘑菇」的原創文章,遵循CC 4.0 BY-SA版權協議,轉載請附上原文出處連結及本聲明。

原文連結:騰訊面試題: 百度搜索為什麼那麼快?

What do you think?

Written by marketer

blank

seo快排技術核心原理-手機端百度快排優化

blank

超全|阿里、騰訊、百度… 這些大廠2020年薪資和職級一覽