搜索引擎设计实用教程(4)-以百度为例
/*版權聲明：可以任意轉載，轉載時請務必標明文章原始出處和作者信息 .*/
搜索引擎設計實用教程(4)-以百度為例
?????????????????????????? 之四:相關提示功能
?
??????????????????????? ?? 中科院軟件所 malefactor
2005年11月
?
?? 相關提示也是幾乎所有搜索引擎提供的一個附加功能,所謂相關提示,就是對于用戶提交的查詢進行分析,然后根據其它用戶相似的查詢給予用戶提示,比如我輸入查詢”大長今”,檢索系統會提示其它象”大長今主題曲”,”大長今下載”等等相關的一些其它用戶查詢.
?? 那么搜索引擎是根據什么原則對于其它用戶的查詢進行選擇來提示用戶相關查詢呢?我們還是以百度為例子來看看怎么實現這個功能.要實現這個功能主要解決如下三個問題:
? 問題一.從哪里獲得其它用戶的查詢信息?這個問題對于搜索引擎來說不是難事,因為搜索引擎都有用戶查詢LOG的功能,在一段時間內每一個用戶提交給搜索引擎的查詢都被記錄在LOG文件里面,所以從這個文件里面可以獲得其它用戶的查詢信息.這個LOG還可以用作其它功能的基本素材,比如搜索排行榜或者搜索風云榜,就是根據這個LOG文件,對用戶查詢歸類,相同的歸為一類,然后統計一段時間內這個類別的出現次數,按照降序排列,選擇前列K個作為輸出即可.
?? 問題二.搜索引擎拿到用戶的查詢比如”大長今”,用戶查詢LOG里面有成千上萬的不同查詢,那么選擇哪些作為提示呢?這里面牽涉到一個字符串相似性計算的過程.
?? 問題三.假設已經從查詢LOG里面選擇了一批用戶相關查詢信息,按照什么順序輸出呢?為什么”大長今主題曲”排列在”大長今下載”前面呢?這里面牽涉到排序原則的問題.
?? 我們一步步分析看看百度是如何解決上面的第二和第三個問題的.
?? 首先,百度在計算字符串相似性的計算過程是首先對于用戶查詢進行分詞,然后對于分詞后的結果來進行相似性計算的.怎么證明這一點? 第一個證明:首先用”新聞”作為查詢,看看百度提示的相關詞匯是什么,然后將查詢修改為”新聞新聞新聞”,再看看提示的相關詞匯是什么,提示是完全一樣的,基本說明是分詞后進行計算的. 第二個證明: 首先用”娛樂新聞報道”作為查詢,看看百度提示的相關查詢是什么,然后人工分好詞”娛樂 新聞 報道”,再看看提示的相關查詢是什么.,提示仍然是完全一樣的,我們再顛倒一下詞匯順序,用”新聞娛樂報道”作為查詢,再看看相關查詢是什么,完全沒有變化.所以得出結論:百度在計算字符串相似性之前首先要對用戶查詢進行分詞,當然查詢LOG里面的查詢也要首先進行分詞.
第二步,怎么計算相似性并排序輸出呢? 如果用戶輸入查詢只有一個單詞,那么處理起來好像比較簡單,只要用戶查詢LOG里面包含這個單詞的字符串都被糾出來,然后根據用戶總共查詢這個字符串的次數進行排序,選擇前列K個作為相關提示就可以了. 好像很簡單,但是問題真的這么簡單就被解決了么? 并非如此.
??? 如果用戶輸入的查詢比較長,問題就出來了,比如我們用“清脆的鳥叫聲”作為查詢，百度返回的相關提示中，前列1－35個相關查詢包含“鳥”和“叫聲”，這幾個查詢排序原則是按照用戶查詢次數多少排列的，在36－40的相關查詢僅僅包含“清脆”一個單詞,排列順序和用“清脆”查詢時候順序相同,說明也是按照用戶查詢次數多少排列的；41－100的相關查詢僅僅包含“叫聲”，第41個查詢”動物的叫聲”是所有100個查詢用戶查詢次數最多的一個. 為什么包含”清脆”的查詢排列在包含”叫聲”的查詢前面而不是反過來呢?
?? 在給個例子,用“咆哮小老鼠”作為查詢，排在最前面的是匹配了“咆哮，小，老鼠”三個詞匯的相關查詢，次之是匹配了“咆哮，老鼠”的相關查詢，再次是匹配“咆哮，小”的相關查詢，最次是匹配“小，老鼠”的相關查詢，總共輸出92個相關查詢，對于只有一個匹配的查詢沒有輸出。那么為什么是“咆哮，老鼠”》“咆哮，小”》“小,老鼠”呢？原則是什么呢？
?? 多次實驗后,發現里面其實有一個匹配單詞的權重設置問題,拿”咆哮小老鼠”做例子,切分后是<咆哮,小,老鼠>, 假設用戶查詢LOG里面有兩個查詢,一個是”咆哮老鼠論壇”,切分后是<咆哮,老鼠,論壇>.匹配的有兩個單詞(咆哮,老鼠), 另一個查詢是”咆哮小”,切分后是<咆哮,小>,匹配的也有兩個單詞(咆哮,小),怎么給這兩個查詢排序呢? 假設每個單詞都有一個權重設置,比如 Weight(咆哮)=a? Weight(小)=b? Weight(老鼠)=c . 我們計算”咆哮小老鼠”和”咆哮老鼠論壇”的相似性等于重復單詞權重之和,也就是等于a+c,而另外一個查詢的相似性等于a+b,然后按照順序輸出就行了.所以這里面關鍵是如何設置單詞的權重.
那么單詞權重怎么衡量呢，作為搜索引擎很容易獲得的一個單詞權重評價因素是IDF，所謂IDF,就是說如果一個單詞如果在很多文檔中都出現,那么這個單詞重要性就很低,比如說”的”,幾乎在每個中文網頁都出現,那么這個單詞的IDF值就非常低.具體計算IDF的公式是
IDF(word)＝log(N/DF(word)),
這里,DF(word)指的是包含單詞word的文檔數目個數，N指的是文檔集合的總的文件個數，我們假設百度索引了6億個網頁,那么這里N=600000000.
我們用IDF來解釋百度的相關查詢排序因子.首先來解釋“清脆的鳥叫聲”這個查詢的相關查詢排序，我們分別用“清脆”“鳥”“叫聲”來作為查詢，看看有多少網頁包含這些詞,百度返回結果是：
??? 清脆：找到相關網頁約2,390,000篇??????
??? 鳥： 找到相關網頁約14,000,000篇
??? 叫聲：到相關網頁約3,370,000篇
?? 把這些數值帶入上面的公式計算得出IDF權重 IDF(清脆)＝2.39975335 》IDF(叫聲)=2.25052135 》IDF(鳥)=1.63202321. 所以前列匹配了“鳥”和“叫聲”的權重最大，都包含這兩個查詢按照用戶查詢數目多少輸出，其他的按照包含”清脆”或者”叫聲”的順序輸出.
??? 對于查詢“咆哮小老鼠”來說，我們看看是否成立：
??? 百度返回結果：
???? 咆哮：找到相關網頁約2,090,000篇
???? 小：找到相關網頁約29,600,000篇
???? 老鼠：找到相關網頁約11,900,000篇
?
???? IDF(咆哮)=2.45800496
???? IDF(小)=1.30685954
???? IDF(老鼠)=1.70260429
?? 所以權重是 咆哮>老鼠>小
?? 我們看到前面分析輸出順序是： <咆哮,老鼠> > <咆哮，小> > <小，老鼠>
?? 我們根據上面單詞的權重可以看出：<咆哮,老鼠>＝IDF(咆哮)＋IDF(老鼠)＝4.15
????????????????????????? ?????????<咆哮，小>=IDF(咆哮)+IDF(小)=3.75
?????????????????????????????????? <小，老鼠>=IDF(小)+IDF(老鼠)=3.01
? 所以百度的順序按照這個順序輸出。
? 再看個例子：查詢“娛樂新聞報道”百度返回結果：
???? 娛樂：找到相關網頁約31,600,000篇
???? 新聞：找到相關網頁約93,500,000篇
???? 報道：找到相關網頁約17,000,000篇
?
???? IDF(娛樂)=1.27846417?
???? IDF(新聞)= 0.80733964?
???? IDF(報道)=1.54770233
??? 我們可以預測：
???? 包含《娛樂，新聞，報道》的相關查詢排名最高，次之是《娛樂，報道>,再次是《新聞，報道》,可以看出百度的排序果然是如此。所以我們的推理基本上是正確的.
最后歸納一下相關查詢的算法流程:
(1)??? 用戶輸入查詢，分詞;
(2)??? 計算用戶查詢和歷史用戶查詢的相似性，相似性計算是通過計算兩者重復單詞的權重之和來計算的
(3)??? 每個單詞的權重用單詞的IDF來計算，大的排序原則根據這個權重進行排序輸出，如果兩個歷史查詢包含相同的重復詞匯集合，那么查詢權重相同，則按照用戶查詢次數有高到低排序輸出。
?
?? 后臺作業：為了加快查詢反映速度，搜索引擎不會每次用戶查詢都重新計算相關查詢，可以在后臺算好以后存儲在數據庫里面，用戶查詢的時候直接查找數據庫輸出，那么后臺如何處理呢？
?? （1）對于最近一段時間（比如一個月或者一個星期）用戶查詢LOG進行統計分析，選擇列在前列比如1千萬條最頻繁的用戶查詢，
??? （2）然后對于每個查詢分詞，按照倒排文檔進行存儲，比如“新聞報道 10000”，則在索引里面登錄?? “新聞－－》新聞報道? 10000” “報道－－>新聞報道 10000”，其他查詢都是如此處理進入索引。
??? （3）對于用戶查詢，在索引里面查找最相似的歷史查詢，并按照上面介紹的方法計算權重，按照權重輸出；
???? （4）當然，為了更加加快查詢速度，第三步驟的工作也可以預先算好，存儲在數據庫里面，用戶查詢直接在數據庫里面存取。這個數據庫可以每隔一段時間更新一次以反映最新的情況。
???????
?
總結
以上是生活随笔為你收集整理的搜索引擎设计实用教程(4)-以百度为例的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 搜索引擎设计实用教程(3)-以百度为例
- 下一篇： 爱你就是爱自己