搜索引擎對重復頁面算法分析

搜索引擎判斷復制網頁一般都基于這么一個思想：為每個網頁計算出一組信息指紋（Fingerprint），若兩個網頁有一定數量相同的信息指紋，則認為這兩個網頁的內容重疊性很高，也就是說兩個網頁是內容復制的。

 

很多搜索引擎判斷內容復制的方法都不太一樣，主要是以下兩點的不同：

 

1、計算信息指紋（Fingerprint）的算法； 

2、判斷信息指紋的相似程度的參數。

 

在描述具體的算法前，先說清楚兩點： 

1、什么是信息指紋？信息指紋就是把網頁里面正文信息，提取一定的信息，可以是關鍵字、詞、句子或者段落及其在網頁里面的權重等，對它進行加密，如MD5加密，從而形成的一個字符串。信息指紋如同人的指紋，只要內容不相同，信息指紋就不一樣。

 

2、算法提取的信息不是針對整張網頁，而是把網站里面共同的部分如導航條、logo、版權等信息（這些稱之為網頁的“噪音”）過濾掉后剩下的文本。

 

分段簽名算法

 

這種算法是按照一定的規則把網頁切成N段，對每一段進行簽名，形成每一段的信息指紋。如果這N個信息指紋里面有M個相同時（m是系統定義的闕值），則認為兩者是復制網頁。

 

這種算法對于小規模的判斷復制網頁是很好的一種算法，但是對于像google這樣海量的搜索引擎來說，算法的復雜度相當高。

 

基于關鍵詞的復制網頁算法

 

像google這類搜索引擎，他在抓取網頁的時候都會記下以下網頁信息：

 

1、網頁中出現的關鍵詞（中文分詞技術）以及每個關鍵詞的權重（關鍵詞密度）； 

2、提取meta descrīption或者每個網頁的512個字節的有效文字。 

關于第2點，baidu和google有所不同，google是提取你的meta descrīption，如果沒有查詢關鍵字相關的512個字節，而百度是直接提取后者。這一點大家使用過的都有所體會。

 

在以下算法描述中，我們約定幾個信息指紋變量：

 

Pi表示第i個網頁； 

該網頁權重最高的N個關鍵詞構成集合Ti={t1,t2,...tn}，其對應的權重為Wi={w1,w2,...wi} 

摘要信息用Des(Pi)表示，前n個關鍵詞拼成的字符串用Con(Ti)表示，對這n個關鍵詞排序后形成的字符串用Sort(Ti)表示。

 

以上信息指紋都用MD5函數進行加密。

 

基于關鍵詞的復制網頁算法有以下5種： 

1、MD5(Des(Pi))=MD5(Des(Pj)),就是說摘要信息完全一樣，i和j兩個網頁就認為是復制網頁； 

2、MD5(Con(Ti))=MD5(Con(Tj)),兩個網頁前n個關鍵詞及其權重的排序一樣，就認為是復制網頁； 

3、MD5(Sort(Ti))=MD5(Sort(Tj)),兩個網頁前n個關鍵詞一樣，權重可以不一樣，也認為是復制網頁。 

4、MD5(Con(Ti))=MD5(Con(Tj))并且Wi-Wj的平方除以Wi和Wj的平方之和小于某個闕值a，則認為兩者是復制網頁。 

5、MD5(Sort(Ti))=MD5(Sort(Tj))并且Wi-Wj的平方除以Wi和Wj的平方之和小于某個闕值a，則認為兩者是復制網頁。

 

關于第4和第5的那個闕值a,主要是因為前一個判斷條件下，還是會有很多網頁被誤傷，搜索引擎開發根據權重的分布比例進行調節，防止誤傷。

 

 

這個是北大天網搜索引擎的去重算法（可以參考：《搜索引擎--原理、技術與系統》一書），以上5種算法運行的時候，算法的效果取決于N，就是關鍵詞數目的選取。當然啦，選的數量越多，判斷就會越精確，但是誰知而來的計算速度也會減慢下來。所以必須考慮一個計算速度和去重準確率的平衡。據天網試驗結果，10個左右關鍵詞最恰當。 

 

后記