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

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

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

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

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

關(guān)鍵詞的歷史背景是什么？原來，在半個(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ī)速度和容量都十分有限，只能對最重要的3到5個(gè)主題詞建立索引?，F(xiàn)在好了，計(jì)算機(jī)的性能已經(jīng)不再是制約因素，還有了成熟的分布式處理手段，對互聯(lián)網(wǎng)上所有網(wǎng)頁的所有詞建立索引理論上存在可能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

經(jīng)過十多年的搜索生涯，我把相關(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)頁中出現(xiàn)，通過它就很容易鎖定目標(biāo)，它的權(quán)重就應(yīng)該大。反之，如果一個(gè)詞在大量的網(wǎng)頁中出現(xiàn)，看到它仍然不清楚要找什么內(nèi)容，它的權(quán)重就應(yīng)該小?！?/p>

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

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

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

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

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

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

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

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

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

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

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

因此網(wǎng)頁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)頁X1與搜索“杭亦白的公眾號”之間的相關(guān)性系數(shù)為0.02556.

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

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

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

參考資料：

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

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

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

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