搜索引擎，可以通過(guò)關(guān)鍵詞使得人們?cè)谑褂脮r(shí)更加的便利。但關(guān)鍵詞是怎確定的呢？不同的用戶是怎么在頁(yè)面中找到他們需要的信息的？本文作者從一個(gè)實(shí)例出發(fā)，對(duì)搜索背后的故事進(jìn)行了梳理闡述，與大家分享。

柳絮紛飛的四組團(tuán)，一個(gè)金色的下午，小白打開電腦，鬼使神差地在百度搜索框里輸入“杭亦白的公眾號(hào)”這幾個(gè)字。大約30毫秒以后，672個(gè)搜索結(jié)果展示在眼前。逐個(gè)往下翻看這些結(jié)果，三個(gè)疑惑逐漸涌上大腦：

1. 我要找哪些網(wǎng)頁(yè)，百度怎么知道的？
2. 網(wǎng)頁(yè)這么多，百度是根據(jù)什么規(guī)則排列它們的？
3. 它返回的和我想要的，相關(guān)性如何？

搜索的數(shù)學(xué)本質(zhì)——搜索詞對(duì)應(yīng)索引表的布爾運(yùn)算

剛剛經(jīng)受畢業(yè)論文洗禮的我們，可能對(duì)摘要最后附帶的幾個(gè)“關(guān)鍵詞“還留有深刻的印象。不止是畢業(yè)論文，幾乎所有的學(xué)術(shù)雜志都要求作者提供3~5個(gè)關(guān)鍵詞。

關(guān)鍵詞的歷史背景是什么？原來(lái)，在半個(gè)多世紀(jì)以前，搜索引擎已經(jīng)廣泛運(yùn)用于文獻(xiàn)檢索了。為了方便期刊的編輯、讀者查找文獻(xiàn)，搜索引擎開發(fā)者們巧妙地為文獻(xiàn)圍繞的核心詞建立了索引，也就是傳承至今的關(guān)鍵詞。如果你搜的詞出現(xiàn)在某篇文章的“關(guān)鍵詞“坑里，搜索引擎就會(huì)迅速把這篇文章返回給你。

比如你搜“顯微鏡“，多半會(huì)看到光學(xué)領(lǐng)域里顯微鏡相關(guān)的文獻(xiàn)，因?yàn)檫@些文獻(xiàn)往往附帶著“顯微鏡”這個(gè)關(guān)鍵詞；同理，搜”浙江村“和”社區(qū)“這兩個(gè)詞，項(xiàng)飆的《跨越邊界的社區(qū)》很可能會(huì)出現(xiàn)在在顯著的位置。

“索引”這個(gè)概念的引入，使得搜索引擎真正具有了實(shí)時(shí)反饋結(jié)果的可能。

一開始，由于計(jì)算機(jī)速度和容量都十分有限，只能對(duì)最重要的3到5個(gè)主題詞建立索引?，F(xiàn)在好了，計(jì)算機(jī)的性能已經(jīng)不再是制約因素，還有了成熟的分布式處理手段，對(duì)互聯(lián)網(wǎng)上所有網(wǎng)頁(yè)的所有詞建立索引理論上存在可能。

如果真的這么搞，互聯(lián)網(wǎng)上就存在一張巨大的索引表，所有詞都能找到對(duì)應(yīng)的網(wǎng)頁(yè)。當(dāng)你搜索一個(gè)詞組，搜索引擎把這個(gè)詞組當(dāng)作鍵（key）放到表里，取出對(duì)應(yīng)的網(wǎng)頁(yè)作為值（value）返回，理論上就初步完成了一次搜索行為。

邏輯看起來(lái)非常簡(jiǎn)單，數(shù)學(xué)上又是怎么實(shí)現(xiàn)的呢？

原來(lái)，最簡(jiǎn)單的索引結(jié)構(gòu)就是一長(zhǎng)串二進(jìn)制數(shù)，來(lái)表示關(guān)鍵詞是否存在在每篇文獻(xiàn)中。有多少篇文獻(xiàn)，二進(jìn)制數(shù)就有多少位，位上取0代表對(duì)應(yīng)文獻(xiàn)里不包含關(guān)鍵詞，取1則相反。

比方說(shuō)，假設(shè)互聯(lián)網(wǎng)上只有16個(gè)網(wǎng)頁(yè)，搜索引擎首先對(duì)這16個(gè)網(wǎng)頁(yè)做一個(gè)排序（如有新增網(wǎng)頁(yè)，堆在隊(duì)尾，保證前方網(wǎng)頁(yè)序號(hào)固定），然后對(duì)網(wǎng)頁(yè)內(nèi)的所有詞，分別建16位的二進(jìn)制數(shù)，這些詞與對(duì)應(yīng)的二進(jìn)制數(shù)就構(gòu)成了一張索引表。

對(duì)于我要搜索的“杭亦白的公眾號(hào)”，搜索引擎首先把這句話根據(jù)語(yǔ)意做分詞處理，分出“杭亦白”、“的”、“公眾號(hào)”這三個(gè)詞。

關(guān)鍵詞“杭亦白”對(duì)應(yīng)的二進(jìn)制數(shù)是0001 0000 0010 0011，表示第四、第十一、第十五、第十六個(gè)網(wǎng)頁(yè)上包含“杭亦白”這個(gè)詞。對(duì)“的”和“公眾號(hào)”做同樣處理，就得了三個(gè)二進(jìn)制數(shù)。

對(duì)以上3個(gè)二進(jìn)制數(shù)做布爾AND運(yùn)算，結(jié)果是0001 0000 0010 0010，表示第四、第十一、第十五個(gè)網(wǎng)頁(yè)滿足搜索要求，搜索引擎向搜索者展示的就是這3個(gè)網(wǎng)頁(yè)。

原來(lái)，搜索的數(shù)學(xué)本質(zhì)，就是搜索詞對(duì)應(yīng)索引表的布爾運(yùn)算，搜索引擎返回布爾“與”運(yùn)算結(jié)果為1的網(wǎng)頁(yè)。

這里可以多提一句，布爾運(yùn)算的元素只有1（TRUE，真）和0（FALSE,假）；基本運(yùn)算只有“與”（AND）、或（OR）、非（NOT），十分簡(jiǎn)單，卻為數(shù)字電路奠定了理論（布爾元素真假對(duì)應(yīng)著電路通斷），也對(duì)數(shù)學(xué)產(chǎn)生深遠(yuǎn)影響：

“布爾代數(shù)對(duì)于數(shù)學(xué)的意義等同于量子力學(xué)對(duì)于物理學(xué)的意義，它們將我們對(duì)世界的認(rèn)識(shí)從連續(xù)狀態(tài)擴(kuò)展為離散狀態(tài)。在布爾代數(shù)的世界里，萬(wàn)物都是可以量子化的，從連續(xù)的變成一個(gè)個(gè)分離的，它們的運(yùn)算“與、或、非”也就和傳統(tǒng)的代數(shù)運(yùn)算完全不同了“

——《數(shù)學(xué)之美》

在實(shí)際情況中，網(wǎng)頁(yè)的數(shù)量不可能像上面假設(shè)的只有16個(gè)那么少，很可能是上百億的量級(jí)，產(chǎn)生的詞組索引表更是爆炸，需要將索引通過(guò)分布式的方式存儲(chǔ)在不同的服務(wù)器上，接受查詢時(shí)，查詢分發(fā)到各個(gè)服務(wù)器上并行處理，結(jié)果送到主服務(wù)器上合并處理，向用戶返回最后結(jié)果。

搜索返回網(wǎng)頁(yè)如何排序——PageRank投票表決

通過(guò)上面的布爾運(yùn)算，搜索引擎向我們返回了三個(gè)網(wǎng)頁(yè)。那么問(wèn)題來(lái)了，該按什么順序排列這三個(gè)網(wǎng)頁(yè)呢？

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

比方說(shuō)我們百度”錨文本“，搜索結(jié)果里有一些藍(lán)色部分的可跳轉(zhuǎn)超鏈接，比如圖上的“超鏈接”、“關(guān)鍵詞”、“Anchor text”,這些部分就是指向其他網(wǎng)頁(yè)的錨文本。

如果某個(gè)網(wǎng)頁(yè)被其他網(wǎng)頁(yè)指向地越多，可以認(rèn)定這個(gè)網(wǎng)頁(yè)人緣好，比較靠譜，可以放在前列。

當(dāng)然，這么說(shuō)也并不十分嚴(yán)謹(jǐn)。因?yàn)楝F(xiàn)實(shí)中，網(wǎng)頁(yè)質(zhì)量本身存在差異，它們的票對(duì)排序結(jié)果的影響并不是等效的：被越有權(quán)威的網(wǎng)站鏈接到，越有可能獲得靠前的排名。

在這么一個(gè)邏輯下，PageRank具體是怎么運(yùn)作的呢？不妨用一個(gè)簡(jiǎn)單的3層鏈接模型來(lái)模擬一下。

搜索引擎返回的3個(gè)網(wǎng)頁(yè)（序號(hào)為第四、第十一、第十五），分別定義為X1、X2、X3，它們分別被Y系列網(wǎng)頁(yè)鏈接，而Y系列網(wǎng)頁(yè)又被Z系列網(wǎng)頁(yè)鏈接?？紤]到網(wǎng)頁(yè)質(zhì)量良莠差異，排名越高的網(wǎng)站貢獻(xiàn)的鏈接權(quán)越大，網(wǎng)頁(yè)X的最終排名，取決于所有指向這個(gè)網(wǎng)頁(yè)的其他網(wǎng)頁(yè)的權(quán)重之和。

相加得到，

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。

根據(jù)結(jié)果，返回的搜索結(jié)果中，X1網(wǎng)頁(yè)放在搜索引擎最前列，接著是X3，最后是X2。

細(xì)心的朋友可能會(huì)問(wèn)了，不對(duì)啊，這里明顯預(yù)設(shè)了Z的權(quán)重，實(shí)際上X的權(quán)重由Y求和，Y的權(quán)重由Z求和，Z權(quán)重還得從外一層網(wǎng)頁(yè)計(jì)算…“計(jì)算搜索結(jié)果的網(wǎng)頁(yè)排名過(guò)程中，需要用到網(wǎng)頁(yè)本身的排名“，這不成了”先有雞還是先有蛋“的問(wèn)題了嗎？

Google創(chuàng)始人之一布林解決了這個(gè)問(wèn)題。先假設(shè)所有網(wǎng)頁(yè)的排名是相同的，根據(jù)初始值算出各網(wǎng)頁(yè)第一次迭代排名，在這基礎(chǔ)上迭代出第二次排名，一般經(jīng)過(guò)10次迭代，結(jié)果就會(huì)收斂到網(wǎng)頁(yè)的真實(shí)排名上。

判別返回結(jié)果與用戶搜索的相關(guān)性

其實(shí)，搜索結(jié)果的最終排名，除了得看搜索結(jié)果中網(wǎng)頁(yè)質(zhì)量高低（用PageRank鏈接權(quán)表征），還取決于結(jié)果與用戶搜索的相關(guān)性。

你想想啊，我搜“杭亦白的公眾號(hào)”，如果搜索引擎給我返回“仙林野豬”或者“大衣哥和他的鄰居”這些莫名其妙的東西，我肯定不開心啊。哪怕是feed一些“公眾號(hào)寫作運(yùn)營(yíng)”弱相關(guān)的網(wǎng)頁(yè)，我也好受一些；如果能呈現(xiàn)在杭一白里寫過(guò)的文章，那就圓滿了。心情一好，甚至要把百度設(shè)置成默認(rèn)搜索引擎。

那么，搜索引擎是怎么保證返回結(jié)果與我搜索的相關(guān)性的呢？

經(jīng)過(guò)十多年的搜索生涯，我把相關(guān)性泛化為 “檢索準(zhǔn)確性”，并且有以下兩個(gè)感性結(jié)論：

1. 搜索結(jié)果中，搜索詞出現(xiàn)的頻次越高，這個(gè)結(jié)果可能越準(zhǔn)確；
2. 如果搜索結(jié)果包含專業(yè)詞匯，而不只有通用詞匯，這個(gè)結(jié)果可能越準(zhǔn)確。

即“如果一個(gè)關(guān)鍵詞只在很少的網(wǎng)頁(yè)中出現(xiàn)，通過(guò)它就很容易鎖定目標(biāo)，它的權(quán)重就應(yīng)該大。反之，如果一個(gè)詞在大量的網(wǎng)頁(yè)中出現(xiàn)，看到它仍然不清楚要找什么內(nèi)容，它的權(quán)重就應(yīng)該小?！?/p>

這兩個(gè)感性結(jié)論分別對(duì)應(yīng)兩個(gè)量化指標(biāo)：TF（Term Frequency，單文本詞頻）和IDF（Inversed Document Frequency，逆文本頻率指數(shù)）。

首先講TF，還是拿“杭亦白的公眾號(hào)”為例子。

搜索返回的X1網(wǎng)頁(yè)里，共有1000個(gè)詞，其中“杭亦白”出現(xiàn)了1次，“的”出現(xiàn)了30次，“公眾號(hào)”出現(xiàn)了5次。那么這三個(gè)詞的詞頻TF1、TF2、TF3分別是0.001、0.03、0.005，三數(shù)相加，其和0.036就是網(wǎng)頁(yè)X1和搜索“杭亦白的公眾號(hào)”的單文本詞頻TF(X1)。

同理，計(jì)算出TF(X2)和TF(X3)，根據(jù)計(jì)算值大小，對(duì)應(yīng)感性結(jié)論1，就可以知道哪個(gè)網(wǎng)頁(yè)和搜索是最相關(guān)的。

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

首先是對(duì)“公眾號(hào)”不滿：我一個(gè)信息量這么高的詞，權(quán)重居然比不上你一個(gè)爛大街的詞。差不多每10個(gè)網(wǎng)頁(yè)里就有一次你的身影，說(shuō)到對(duì)預(yù)測(cè)小白要搜索的主題的貢獻(xiàn)，你拿什么和我比？引擎大哥，我認(rèn)為有失偏頗！

其次是對(duì)“的”這個(gè)虛詞：哪哪都有你，難怪?jǐn)?shù)據(jù)這么好看，但是對(duì)相關(guān)性判別沒有半毛錢貢獻(xiàn)啊。

搜索引擎聽了“杭亦白”的抱怨，默默引入IDF并更新了規(guī)則：

• “的”等虛詞列為停止詞（Stop Word）；
• 專業(yè)詞比普通詞更能預(yù)測(cè)用戶搜索的主題，需要適當(dāng)提高影響因子。

具體操作是，對(duì)以上3個(gè)詞，分別使用公式log（D/Dw）計(jì)算IDF，其中，D是全部網(wǎng)頁(yè)數(shù)，Dw表示關(guān)鍵詞w在多少個(gè)網(wǎng)頁(yè)里出現(xiàn)過(guò)。

假設(shè)中文網(wǎng)頁(yè)數(shù)D=100億，專業(yè)詞“杭亦白”出現(xiàn)在其中2000萬(wàn)個(gè)網(wǎng)頁(yè)中，IDF1=log（100億/2000萬(wàn)）=8.96；停止詞“的”出現(xiàn)在所有網(wǎng)頁(yè)中，IDF2=log（100億/100億）=0；普通詞“公眾號(hào)”出現(xiàn)在1億個(gè)網(wǎng)頁(yè)里，IDF3=log（100億/1億）=3.32.

因此網(wǎng)頁(yè)X1與搜索詞的相關(guān)性計(jì)算變成了以下的加權(quán)計(jì)算：

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

即網(wǎng)頁(yè)X1與搜索“杭亦白的公眾號(hào)”之間的相關(guān)性系數(shù)為0.02556.

同理分別計(jì)算出X2、X3和搜索之間的相關(guān)系數(shù)。系數(shù)越大，證明網(wǎng)頁(yè)“越準(zhǔn)確”，考慮排在越靠前的位置。

學(xué)到這，小白心里又犯嘀咕了：好像都是一些上古時(shí)代PC端的知識(shí)，有沒有偏APP端的呢？想到這，小白關(guān)上電腦打開手機(jī)，開始了新的征程。

號(hào)外：新開“小白學(xué)搜索”系列，暫定分上中下三篇更新，用盡量直白的語(yǔ)言把搜索講明白。請(qǐng)搜索大佬不吝后臺(tái)賜教。

參考資料：

《數(shù)學(xué)之美》 吳軍人民郵電出版社

作者：杭亦白（微信號(hào)：xiehangfeng01）?；ヂ?lián)網(wǎng)產(chǎn)品新人，對(duì)搜索、產(chǎn)品、社交感興趣，坐標(biāo)上海；微信公眾號(hào)：杭一白（微信號(hào)：xiehangfeng02）

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

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