搜索引擎，可以通過關鍵詞使得人們在使用時更加的便利。但關鍵詞是怎確定的呢？不同的用戶是怎麼在頁面中找到他們需要的信息的？本文作者從一個實例出發，對搜索背後的故事進行了梳理闡述，與大家分享。

柳絮紛飛的四組團，一個金色的下午，小白打開電腦，鬼使神差地在百度搜索框裏輸入“杭亦白的公衆號”這幾個字。大約30毫秒以後，672個搜索結果展示在眼前。逐個往下翻看這些結果，三個疑惑逐漸湧上大腦：

1. 我要找哪些網頁，百度怎麼知道的？
2. 網頁這麼多，百度是根據什麼規則排列它們的？
3. 它返回的和我想要的，相關性如何？

搜索的數學本質——搜索詞對應索引表的布爾運算

剛剛經受畢業論文洗禮的我們，可能對摘要最後附帶的幾個“關鍵詞“還留有深刻的印象。不止是畢業論文，幾乎所有的學術雜誌都要求作者提供3~5個關鍵詞。

關鍵詞的歷史背景是什麼？原來，在半個多世紀以前，搜索引擎已經廣泛運用於文獻檢索了。爲了方便期刊的編輯、讀者查找文獻，搜索引擎開發者們巧妙地爲文獻圍繞的核心詞建立了索引，也就是傳承至今的關鍵詞。 如果你搜的詞出現在某篇文章的“關鍵詞“坑裏，搜索引擎就會迅速把這篇文章返回給你。

比如你搜“顯微鏡“，多半會看到光學領域裏顯微鏡相關的文獻，因爲這些文獻往往附帶着“顯微鏡”這個關鍵詞；同理，搜”浙江村“和”社區“這兩個詞，項飆的《跨越邊界的社區》很可能會出現在在顯著的位置。

“索引”這個概念的引入，使得搜索引擎真正具有了實時反饋結果的可能。

一開始，由於計算機速度和容量都十分有限，只能對最重要的3到5個主題詞建立索引。現在好了，計算機的性能已經不再是制約因素，還有了成熟的分佈式處理手段，對互聯網上所有網頁的所有詞建立索引理論上存在可能。

如果真的這麼搞，互聯網上就存在一張巨大的索引表，所有詞都能找到對應的網頁。 當你搜索一個詞組，搜索引擎把這個詞組當作鍵（key）放到表裏，取出對應的網頁作爲值（value）返回，理論上就初步完成了一次搜索行爲。

邏輯看起來非常簡單，數學上又是怎麼實現的呢？

原來，最簡單的索引結構就是一長串二進制數，來表示關鍵詞是否存在在每篇文獻中。有多少篇文獻，二進制數就有多少位，位上取0代表對應文獻裏不包含關鍵詞，取1則相反。

比方說，假設互聯網上只有16個網頁，搜索引擎首先對這16個網頁做一個排序（如有新增網頁，堆在隊尾，保證前方網頁序號固定），然後對網頁內的所有詞，分別建16位的二進制數，這些詞與對應的二進制數就構成了一張索引表。

對於我要搜索的“杭亦白的公衆號”，搜索引擎首先把這句話根據語意做分詞處理，分出“杭亦白”、“的”、“公衆號”這三個詞。

關鍵詞“杭亦白”對應的二進制數是0001 0000 0010 0011，表示第四、第十一、第十五、第十六個網頁上包含“杭亦白”這個詞。對“的”和“公衆號”做同樣處理，就得了三個二進制數。

對以上3個二進制數做布爾AND運算，結果是0001 0000 0010 0010，表示第四、第十一、第十五個網頁滿足搜索要求，搜索引擎向搜索者展示的就是這3個網頁。

原來，搜索的數學本質，就是搜索詞對應索引表的布爾運算，搜索引擎返回布爾“與”運算結果爲1的網頁。

這裏可以多提一句，布爾運算的元素只有1（TRUE，真）和0（FALSE,假）；基本運算只有“與”（AND）、或（OR）、非（NOT），十分簡單，卻爲數字電路奠定了理論（布爾元素真假對應着電路通斷），也對數學產生深遠影響：

“布爾代數對於數學的意義等同於量子力學對於物理學的意義， 它們將我們對世界的認識從連續狀態擴展爲離散狀態。在布爾代數的世界裏，萬物都是可以量子化的，從連續的變成一個個分離的 ，它們的運算“與、或、非”也就和傳統的代數運算完全不同了“

——《數學之美》

在實際情況中，網頁的數量不可能像上面假設的只有16個那麼少，很可能是上百億的量級，產生的詞組索引表更是爆炸，需要將索引通過分佈式的方式存儲在不同的服務器上，接受查詢時，查詢分發到各個服務器上並行處理，結果送到主服務器上合併處理，向用戶返回最後結果。

搜索返回網頁如何排序——PageRank投票表決

通過上面的布爾運算，搜索引擎向我們返回了三個網頁。那麼問題來了， 該按什麼順序排列這三個網頁呢？

Google在1998年給出了答案：表決式PageRank。核心思路只有一句話： 網頁之間會以互相之間鏈接錨文本（Anchor Text）的形式投票，獲得的票越多的網頁，排名越靠前。

比方說我們百度”錨文本“，搜索結果裏有一些藍色部分的可跳轉超鏈接，比如圖上的“超鏈接”、“關鍵詞”、“Anchor text”,這些部分就是指向其他網頁的錨文本。

如果某個網頁被其他網頁指向地越多，可以認定這個網頁人緣好，比較靠譜，可以放在前列。

當然，這麼說也並不十分嚴謹。因爲現實中，網頁質量本身存在差異，它們的票對排序結果的影響並不是等效的： 被越有權威的網站鏈接到，越有可能獲得靠前的排名。

在這麼一個邏輯下，PageRank具體是怎麼運作的呢？不妨用一個簡單的3層鏈接模型來模擬一下。

搜索引擎返回的3個網頁（序號爲第四、第十一、第十五），分別定義爲X1、X2、X3，它們分別被Y系列網頁鏈接，而Y系列網頁又被Z系列網頁鏈接。考慮到網頁質量良莠差異，排名越高的網站貢獻的鏈接權越大，網頁X的最終排名，取決於所有指向這個網頁的其他網頁的權重之和。

相加得到，

PR(X1) = 0.013+0.01+0.022+0.012=0.057，

同理，

PR(X2)=0.005+0.004+0.023+0.003=0.035，

PR(X3)=0.04。

根據結果，返回的搜索結果中，X1網頁放在搜索引擎最前列，接着是X3，最後是X2。

細心的朋友可能會問了，不對啊，這裏明顯預設了Z的權重，實際上X的權重由Y求和，Y的權重由Z求和，Z權重還得從外一層網頁計算… “計算搜索結果的網頁排名過程中，需要用到網頁本身的排名“，這不成了”先有雞還是先有蛋“的問題了嗎？

Google創始人之一布林解決了這個問題。先假設所有網頁的排名是相同的，根據初始值算出各網頁第一次迭代排名，在這基礎上迭代出第二次排名，一般經過10次迭代，結果就會收斂到網頁的真實排名上。

判別返回結果與用戶搜索的相關性

其實，搜索結果的最終排名，除了得看搜索結果中網頁質量高低（用PageRank鏈接權表徵），還取決於結果與用戶搜索的相關性。

你想想啊，我搜“杭亦白的公衆號”，如果搜索引擎給我返回“仙林野豬”或者“大衣哥和他的鄰居”這些莫名其妙的東西，我肯定不開心啊。哪怕是feed一些“公衆號寫作運營”弱相關的網頁，我也好受一些；如果能呈現在杭一白裏寫過的文章，那就圓滿了。心情一好，甚至要把百度設置成默認搜索引擎。

那麼，搜索引擎是怎麼保證返回結果與我搜索的相關性的呢？

經過十多年的搜索生涯，我把相關性泛化爲 “檢索準確性”，並且有以下兩個感性結論：

1. 搜索結果中，搜索詞出現的頻次越高，這個結果可能越準確；
2. 如果搜索結果包含專業詞彙，而不只有通用詞彙，這個結果可能越準確。

即“如果一個關鍵詞只在很少的網頁中出現，通過它就很容易鎖定目標，它的權重就應該大。反之，如果一個詞在大量的網頁中出現，看到它仍然不清楚要找什麼內容，它的權重就應該小。”

這兩個感性結論分別對應兩個量化指標： TF（Term Frequency，單文本詞頻） 和 IDF（Inversed Document Frequency，逆文本頻率指數） 。

首先講TF，還是拿“杭亦白的公衆號”爲例子。

搜索返回的X1網頁裏，共有1000個詞，其中“杭亦白”出現了1次，“的”出現了30次，“公衆號”出現了5次。那麼這三個詞的詞頻TF1、TF2、TF3分別是0.001、0.03、0.005，三數相加，其和0.036就是網頁X1和搜索“杭亦白的公衆號”的單文本詞頻TF(X1)。

同理，計算出TF(X2)和TF(X3)，根據計算值大小，對應感性結論1，就可以知道哪個網頁和搜索是最相關的。

就這？當然不是。如果只按照這個邏輯，“杭亦白”這個詞可能要有意見了。

首先是對“公衆號”不滿：我一個信息量這麼高的詞，權重居然比不上你一個爛大街的詞。差不多每10個網頁裏就有一次你的身影，說到對預測小白要搜索的主題的貢獻，你拿什麼和我比？引擎大哥，我認爲有失偏頗！

其次是對“的”這個虛詞：哪哪都有你，難怪數據這麼好看，但是對相關性判別沒有半毛錢貢獻啊。

搜索引擎聽了“杭亦白”的抱怨，默默引入IDF並更新了規則：

• “的”等虛詞列爲停止詞（Stop Word）；
• 專業詞比普通詞更能預測用戶搜索的主題，需要適當提高影響因子。

具體操作是，對以上3個詞，分別使用公式log（D/Dw）計算IDF，其中，D是全部網頁數，Dw表示關鍵詞w在多少個網頁裏出現過。

假設中文網頁數D=100億，專業詞“杭亦白”出現在其中2000萬個網頁中，IDF1=log（100億/2000萬）=8.96；停止詞“的”出現在所有網頁中，IDF2=log（100億/100億）=0；普通詞“公衆號”出現在1億個網頁裏，IDF3=log（100億/1億）=3.32.

因此網頁X1與搜索詞的相關性計算變成了以下的加權計算：

Relevance1=TF1*IDF1+TF2*IDF2+TF3*IDF3=0.002*8.96+0.03*0+0.005*3.32=0.02556。

即網頁X1與搜索“杭亦白的公衆號”之間的相關性係數爲0.02556.

同理分別計算出X2、X3和搜索之間的相關係數。 係數越大，證明網頁“越準確”，考慮排在越靠前的位置。

學到這，小白心裏又犯嘀咕了：好像都是一些上古時代PC端的知識，有沒有偏APP端的呢？想到這，小白關上電腦打開手機，開始了新的征程。

號外：新開“小白學搜索”系列，暫定分上中下三篇更新，用盡量直白的語言把搜索講明白。請搜索大佬不吝後臺賜教。

參考資料：

《數學之美》 吳軍人民郵電出版社

作者：杭亦白（微信號：xiehangfeng01）。互聯網產品新人，對搜索、產品、社交感興趣，座標上海；微信公衆號：杭一白（微信號：xiehangfeng02）

本文由 @杭亦白 原創發佈於人人都是產品經理。未經許可，禁止轉載

題圖來自Unsplash，基於CC0協議

相關文章