搜索引擎重復網(wǎng)頁(yè)發(fā)現技術(shù)分析
中科院軟件所 張俊林
TIMESTAMP:2006年6月1日
一. 介紹
統計結果表明，近似鏡像網(wǎng)頁(yè)數占總網(wǎng)頁(yè)數的比例高達全部頁(yè)面的29%,而完全相同的頁(yè)面大約占全部頁(yè)面的22%。這些重復網(wǎng)頁(yè)有的是沒(méi)有一點(diǎn)改動(dòng)的拷貝，有的在內容上稍作修改，比如同一文章的不同版本，一個(gè)新一點(diǎn)，一個(gè)老一點(diǎn)，有的則僅僅是網(wǎng)頁(yè)的格式不同（如 HTML, Postscript）,文獻[Models and Algorithms for Duplicate Document Detection 1999年]將內容重復歸結為以下四個(gè)類(lèi)型:
1.如果2篇文檔內容和格式上毫無(wú)差別，則這種重復叫做full-layout duplicate。
2.如果2篇文檔內容相同，但是格式不同，則叫做full-content duplicates
3.如果2篇文檔有部分重要的內容相同，并且格式相同，則稱(chēng)為partial-layout duplicates
4.如果2篇文檔有部分重要的內容相同，但是格式不同，則稱(chēng)為partial-content duplicates
近似重復網(wǎng)頁(yè)發(fā)現技術(shù)就是通過(guò)技術(shù)手段快速全面發(fā)現這些重復信息的手段.如何快速準確地發(fā)現這些內容上相似的網(wǎng)頁(yè)已經(jīng)成為提高搜索引擎服務(wù)質(zhì)量的關(guān)鍵技術(shù)之一。發(fā)現重復或者近似網(wǎng)頁(yè)對于搜索引擎有很多好處:
1. 首先，如果我們能夠找出這些重復網(wǎng)頁(yè)并從數據庫中去掉，就能夠節省一部分存儲空間，進(jìn)而可以利用這部分空間來(lái)存放更多的有效網(wǎng)頁(yè)內容，同時(shí)也提高了web檢索的質(zhì)量。
2. 其次，如果我們能夠通過(guò)對以往搜集信息的分析，預先發(fā)現重復網(wǎng)頁(yè)，在今后的網(wǎng)頁(yè)搜集過(guò)程中就可以避開(kāi)這些網(wǎng)頁(yè)，從而提高有效網(wǎng)頁(yè)的搜集速度。有研究表明重復網(wǎng)頁(yè)隨著(zhù)時(shí)間級別不發(fā)生太大變化,所以這種從重復頁(yè)面集合中選擇部分頁(yè)面進(jìn)行索引是有效的.
3. 另外，如果某個(gè)網(wǎng)頁(yè)的鏡像度較高，也就預示著(zhù)該網(wǎng)頁(yè)相對重要，在搜集網(wǎng)頁(yè)時(shí)應賦予它較高的優(yōu)先級，而當搜索引擎系統在響應用戶(hù)的檢索請求并對輸出結果排序時(shí)，應該賦予它較高的權值。
4. 從另外一個(gè)角度看,如果用戶(hù)點(diǎn)擊了一個(gè)死鏈接,那么可以將用戶(hù)引導到一個(gè)相同頁(yè)面,這樣可以有效的增加用戶(hù)的檢索體驗.因而近似鏡像網(wǎng)頁(yè)的及時(shí)發(fā)現有利于改善搜索引擎系統的服務(wù)質(zhì)量。
二. 基本處理流程
通過(guò)分析現有技術(shù),可以歸納出以下幾個(gè)解決該問(wèn)題的核心技術(shù)點(diǎn),每個(gè)不同的技術(shù)基本上是由這幾個(gè)技術(shù)點(diǎn)構成,無(wú)非是具體采納的技術(shù)不同而已:
1. 文檔對象的特征抽取:將文檔內容分解,由若干組成文檔的特征集合表示,這一步是為了方面后面的特征比較計算相似度.
2. 特征的壓縮編碼:通過(guò)HASH編碼等文本向數字串映射方式以方便后續的特征存儲以及特征比較.起到減少存儲空間,加快比較速度的作用.
3. 文檔相似度計算:根據文檔特征重合比例來(lái)確定是否重復文檔.
4. 聚類(lèi)算法:通過(guò)疊代計算算出哪些文檔集合是根據相似度計算是相近的;
5. 工程化問(wèn)題:出于海量數據計算速度的考慮,提出一些速度優(yōu)化算法以使得算法實(shí)用化.
我們可以從幾個(gè)不同的角度對于現有的方法進(jìn)行分類(lèi):
l 按照利用的信息，現有方法可以分為以下三類(lèi)
1．只是利用內容計算相似
2．結合內容和鏈接關(guān)系計算相似
3．結合內容，鏈接關(guān)系以及url文字進(jìn)行相似計算
評價(jià):現有絕大部分方法還是利用文本內容進(jìn)行相似識別,其它兩種利用鏈接關(guān)系以及URL文字的方法還不是很成熟,而且從效果看引入其它特征收效并不明顯,所以從實(shí)際出發(fā)還是選擇利用內容進(jìn)行相似計算的算法.
l 按照特征提取的粒度現有方法可以分為以下三類(lèi)
1. 按照單詞這個(gè)級別的粒度進(jìn)行特征提取.
2. 按照SHINGLE這個(gè)級別的粒度進(jìn)行特征提取.SHNGLE是若干個(gè)連續出現的單詞,級別處于文檔和單詞之間,比文檔粒度小,比單詞粒度大.
3. 按照整個(gè)文檔這個(gè)級別的粒度進(jìn)行特征提取
評價(jià):
目前這個(gè)領(lǐng)域里面很多工作借鑒類(lèi)似于信息檢索的方法來(lái)識別相似文檔,其本質(zhì)和SHINGLE等是相同的，都是比較兩個(gè)文檔的重合程度，但是區別是SHINGLE是將若干單詞組成片斷，粒度比較大，而信息檢索類(lèi)方法其實(shí)是用單詞作為比較粒度，粒度比較小，粒度越大計算速度越快，而粒度越小計算速度越慢，所以信息檢索類(lèi)方法是不實(shí)用的，而且對SHINGLE的改進(jìn)以及新提出的方法的發(fā)展趨勢也是粒度越來(lái)越大，這樣才能解決實(shí)際使用中速度的問(wèn)題。粒度最大的極端情況是每個(gè)文檔用一個(gè)HASH函數編碼（比如MD5），這樣只要編碼相同就說(shuō)明文檔完全相同，但是粒度太大帶來(lái)的問(wèn)題是對于細微的變化文檔無(wú)法判別，只能判斷是否完全相同，至于部分相同以及相同的程度無(wú)法判斷.
所以，現有方法也可以從以下角度分類(lèi)：粒度。最小粒度：?jiǎn)卧~；中等粒度：SHINGLE；最大粒度：整個(gè)文檔；可見(jiàn)SHINGLE類(lèi)方法其實(shí)是在速度和精確程度上的一種折中方法?？梢蕴接懖煌６鹊男Ч?，比如以句子為單位進(jìn)行編碼，以段落為單位編碼等不同粒度的編碼單位，還可以考慮動(dòng)態(tài)的編碼：首先以自然段落編碼進(jìn)行判別，如果發(fā)現部分相似，然后針對不同的部分再以細小粒度比如句子甚至單詞級別的比較 所謂SUPER SHINGLE就是將粒度放大得到的。粒度越大，好處是計算速度越快（對于MD5整個(gè)文檔來(lái)說(shuō)，每個(gè)文檔一個(gè)HASH編碼，然后排序，將相同的找出，是速度最快的），缺點(diǎn)是會(huì )遺漏很多部分相似的文檔；粒度越小，好處是招回率比較高，缺點(diǎn)是計算速度減慢。
l 按照去處重復的級別進(jìn)行分類(lèi),去處重復三個(gè)級別:
1. 鏡像站點(diǎn):根據站點(diǎn)內相似頁(yè)面多少進(jìn)行判斷.實(shí)現相對簡(jiǎn)單.
2. 完全相同網(wǎng)頁(yè):實(shí)現相對簡(jiǎn)單并且速度比較塊,可以根據頁(yè)面MD5整個(gè)文檔來(lái)說(shuō)，每個(gè)文檔一個(gè)HASH編碼，然后排序，將相同的找出.
3. 部分相同頁(yè)面:實(shí)現相對負責,目前大多工作在這個(gè)部分.
評價(jià):
三個(gè)級別應該從最高級別到較低級別分別進(jìn)行,因為有很大比例(22%)的內容是完全相同的,這個(gè)部分實(shí)現起來(lái)相對簡(jiǎn)單,而且如果這個(gè)部分已經(jīng)識別,那么針對部分相同頁(yè)面的計算量會(huì )大量減少,這樣應該可以減少總體的計算時(shí)間..
l 按照去重的時(shí)機,可以分為以下三類(lèi)
（1） 抓取頁(yè)面的時(shí)候去重，這樣可以減少帶寬以及減少存儲數量；
（2） 索引之后進(jìn)行去重；
（3） 用戶(hù)檢索時(shí)候進(jìn)行再次去重；增加準確性，耗費時(shí)間；
評價(jià):
可以結合三個(gè)時(shí)機某個(gè)或者所有都結合,對于GOOGLE來(lái)說(shuō),很可能是結合了2和3兩種方法, GOOGLE的很多思路建立在后臺計算和實(shí)時(shí)計算聯(lián)合，比如相關(guān)度計算，后臺計算重要性得分，在用戶(hù)輸入查詢(xún)后得到初始數據集合，然后根據這個(gè)數據集合之間文檔的關(guān)系重新調整順序；比如去處重復，首先在后臺進(jìn)行重復發(fā)現，為了增加精確度，在返回查詢(xún)結果后，在返回文檔集合內，又根據“描述”部分重新計算哪些文檔是重復的，這樣增加了準確性，估計其它很多相關(guān)算法也采取這種聯(lián)合策略，為了加快速度，實(shí)時(shí)計算部分可以和CACHE部分結合進(jìn)行計算。
l 按照不同的特征選擇方法,有幾種方式:
1. 完全保留特征
2. 特征選擇,設置不同的選擇策略來(lái)保留部分特征,拋棄其它特征
a. 比如對于單詞級別的拋棄權重小的單詞(I-MATCH)
b. 對于SHINGLE方法,可以保留部分SHINGLE拋棄其它SHINGLE
(1) 一種是保留FINGERPRINT第I個(gè)位置為0的SHINGLE,其它拋棄;
(2) 一種是每隔I個(gè)SHINGLE進(jìn)行抽樣保留,其它拋棄;這兩種得到的文檔SHINGLE數目是變長(cháng)的;
(3) 一種是選擇最小的K個(gè)SHINGLE,這種得到定長(cháng)的SHINGLE數目;
(4) 用84個(gè)RABIN FINGERPRINT函數對于每個(gè)SHINGLE進(jìn)行計算,保留數值最小的84個(gè)FINGERPRINT,這個(gè)方法是定長(cháng)的.
對于SHINGLE類(lèi)方法來(lái)說(shuō),還可以區分為:定長(cháng)的和變長(cháng)的block切分算法
定長(cháng)算法：速度快，但是如果內容有稍微變化（比如插入或者刪除一個(gè)字符或者單詞），其影響會(huì )比較大。比如Shingle及其改進(jìn)方法（Super-Shingle），CSC及其改進(jìn)方法（CSC-SS）。
變長(cháng)算法：速度相對慢，但是內容變化只是造成局部影響。比如CDC,TTTD等算法。
評價(jià): 為了提高計算速度,一種策略是在特征提取的時(shí)候,拋棄部分特征,保留部分特征,通過(guò)減少特征數目來(lái)加快計算速度.另外一個(gè)策略是粒度盡可能加大,比如SUPER-SHINGLE,MEGA-SHINGLE甚至是文檔基本;為了提高算法效果,策略是采取變長(cháng)的內容切割算法比如CSC算法等;這三種策略是方法加快速度和準確性的發(fā)展方向.
一些初步的結論:
1. 對于信息檢索類(lèi)型的方法來(lái)說(shuō),由于其特征選擇是基于單詞的,所以計算速度是個(gè)根本的問(wèn)題,所以基本上是不實(shí)用的;
2. 從利用的信息來(lái)看,實(shí)用的系統還是應該立足于只是利用文本內容來(lái)判別相似性,排除掉利用鏈接信息等方法;
3. 從算法特征抽取粒度來(lái)看,應該立足于SHINLGE類(lèi)的粒度甚至是文檔級別的粒度算法;而SHINGLE類(lèi)別的算法又應該優(yōu)先選擇拋棄部分特征的算法以及變長(cháng)的算法;
4. 從去重級別角度考慮,應該將完全相同的文檔和部分相同的文檔識別分開(kāi)進(jìn)行,而且首先進(jìn)行完全相同文檔的識別,這樣會(huì )有效加快計算速度;
5. 從去重時(shí)機考慮,可以考慮結合后臺去重以及實(shí)時(shí)去重,這樣增加去重的效果;
6. 從壓縮編碼方法來(lái)看,最有效的方式可能是RABIN FINGERPRINT變體算法;
7. 從聚類(lèi)方法來(lái)看,最有效的方式可能是UNION FIND算法,目前比較快的算法基本上都采用這個(gè)方法;
8. 從整體方法選擇來(lái)看,應該選擇改進(jìn)的SHINLGE方法,在此基礎上進(jìn)行進(jìn)一步的改進(jìn);
三. 方法效率比較
1. SHINGLING 方法:時(shí)間效率O((mn)2) ,其中 m是SHINGLE的大小,n是文檔數目.計算時(shí)間為:3千萬(wàn)文檔,10臺機器算一天,或者一臺機器算10天;
2. 改進(jìn)的SHINGLE方法(On the Evolution of Clusters of Near-Duplicate Web Pages.):時(shí)間效率接近于線(xiàn)性的O(n),計算時(shí)間為:1億5千萬(wàn)網(wǎng)頁(yè)計算3個(gè)小時(shí);
3. IMACH方法: 最壞的情況下時(shí)間復雜度是(O(d log d))，速度比較快
4. BLOOM FILTER方法:10k數據花費大約66ms;
從計算效率考慮,速度排序為:
1. 改進(jìn)的SHINGLE方法;
2. IMATCH方法;
3. BLOOM FILTER方法;
4. SHINGLE方法;
四. 目前代表性解決方法分析
1. Shingle方法(1997年)
a. 特征抽取
Shingle方法:所謂Shingle類(lèi)似于自然語(yǔ)言處理中常用的N-GRAM方法,就是將相互連續出現窗口大小為N的單詞串作為一個(gè)Shingle,兩者的不同點(diǎn)在于Shingle是這些串的集合,相同的串會(huì )合并為一個(gè),而N-GRAM則由于考慮的是文本線(xiàn)性結構,所以沒(méi)有相同合并步驟.每個(gè)Shingle就是文檔的一個(gè)特征,一篇文檔就是由所有這些Shingle構成的.
b. 壓縮編碼
40 bit長(cháng)度 Rabin FingerPrint方法;至于存儲方式則類(lèi)似于傳統信息檢索領(lǐng)域的倒排文檔技術(shù),存儲<Shingle,ID>信息以記錄某個(gè)特征在哪些文檔中出現過(guò),然后進(jìn)一步計算文檔的相似性;
c. 文檔相似度計算
(1) 相似度:任意兩個(gè)文檔A和B,相似度指的是兩者相同的Shingle數目占兩者Shingle數目總和的比例;
(2) 包含度:指的是兩者相同的Shingle數目占某篇文檔Shingle數目的比例;
d. 優(yōu)化措施:
(1) 分布計算然后合并;
(2) 拋棄超高頻出現Shingle,分析發(fā)現這些Shingle是無(wú)意義的片斷;
(3) 完全相同文檔保留一份進(jìn)行聚類(lèi);(文檔是否完全相同根據壓縮編碼后數值是否相同判斷)
(4) Super Shingle:關(guān)于Shingle的Shingle,從更大結構上計算相似性以節省存儲空間;
2. Google可能采取的方法
a. 特征抽取
類(lèi)似于Shingle方法,不同點(diǎn)在于:對于每個(gè)單詞根據HASH函數決定屬于哪個(gè)LIST,這樣每個(gè)文檔由若干個(gè)這樣的LIST構成;
b. 壓縮編碼
FingerPrint方法;對于組成文檔的LIST進(jìn)行FingerPrint方法計算;
c. 文檔相似度計算
編輯距離(Edit Distance):如果兩個(gè)文檔有任何一個(gè)FingerPrint相似就判斷為內容接近.
d. 聚類(lèi)方法
首先對<FingerPrint,Doc ID>按照Doc ID進(jìn)行排序;然后采取Union Find聚類(lèi)方法,聚類(lèi)結果就是相似文檔集合;
e. 優(yōu)化措施
3. HP實(shí)驗室方法(2005年)
a. 特征抽取
基于內容的Chunk方法:變長(cháng)而非定長(cháng)的Chunk算法(TTTD算法);將一篇文檔分解為若干個(gè)長(cháng)度不同的Chunk,每個(gè)Chunk作為文本的一個(gè)特征.與shingle方法相比這種變長(cháng)Chunk方法能夠增加系統招回率;
b. 壓縮編碼
128bit MD5 HASH方法;每篇文章壓縮編碼后由若干 <Chunk 長(cháng)度, 定長(cháng)HASH編碼>二元組構成;
c. 文檔相似度計算
(1) 構建所有文檔和Chunk構成的二分圖;
(2) 找到文檔A包含的所有CHUNK,計算這些CHUNK還被哪些其它文檔包含;
(3) 計算這些文檔和A的相似性;
d. 聚類(lèi)方法:Union Find 算法
e. 優(yōu)化措施:Bipartite 劃分,本質(zhì)上是將大規模數據分成小規模數據進(jìn)行識別然后再合并結果.相當于分布計算;
4．bloom filter(2005年)
(1).特征抽取方法
基于內容的語(yǔ)塊（Content-defined chunking CDC）：CDC將文檔切分為變長(cháng)的內容片斷，切分邊界由rabin fringerprint和預先制定的maker數值匹配來(lái)進(jìn)行判斷。
(2)編碼（構造 bloom filter集合元素）
對于切分的片斷進(jìn)行編碼。bloom filter的編碼方式如下：整個(gè)文檔是由片斷構成的，文檔由長(cháng)為m的二值數組表示。在將一個(gè)元素（內容片斷）進(jìn)行編碼插入集合的時(shí)候，利用k個(gè)不同的hash函數進(jìn)行編碼，每個(gè)hash函數設置m個(gè)位置的某個(gè)位置為1。這種技術(shù)以前主要用來(lái)進(jìn)行判斷某個(gè)元素是否被集合包含。
（3）相似度計算方法
bloom filter方法：對于兩個(gè)已經(jīng)編碼的文檔（兩個(gè)長(cháng)度為m的二值數組），通過(guò)bit邏輯運算AND計算，如果兩者很多位置都同時(shí)為1，那么兩個(gè)文檔被認為是近似的。
（4）優(yōu)勢
1．文檔編碼形式簡(jiǎn)潔，便于存儲。
2．由于計算相似性是BIT邏輯運算，所以速度快。
3．相對Shingling 方式來(lái)說(shuō)便于判斷文檔包含關(guān)系。（某個(gè)文檔包含另外一個(gè)短小的文檔）
5．內容+鏈接關(guān)系（2003年）
1．特征抽取方法
這個(gè)方法在抽取特征的時(shí)候同時(shí)考慮了文檔的內容因素以及鏈接關(guān)系因素。
內容因素：通過(guò)Random Projection技術(shù)將文檔內容從高維空間映射到低維空間，并且由實(shí)數表示，如果兩個(gè)文檔映射后的數字越接近則表明兩者內容越相似。
鏈接因素：通過(guò)考慮類(lèi)似于PAGERANK的連接關(guān)系，將某個(gè)網(wǎng)頁(yè)的內容因素計算獲得的分值通過(guò)鏈接傳播到其他網(wǎng)頁(yè)（傳播關(guān)系見(jiàn)下列公式），多次疊代計算后得到每個(gè)頁(yè)面的鏈接得分。
2．相似度計算方法
每個(gè)文檔由二元組<RP,HM>構成，RP代表內容部分的數值，HM代表鏈接關(guān)系代表的數值。如果兩個(gè)文檔每個(gè)項之間的差值都小于指定值，則判斷兩個(gè)文檔是相似的。
3．效果
只采取內容精度達到90%，兩者結合精度達到93%。從中看出，鏈接的作用并不明顯。這可能跟這個(gè)方法的鏈接使用方法有關(guān)，因為通過(guò)鏈接計算的還是內容的情況。
6．I-Match方法（2002年）
（1）I-Match不依賴(lài)于完全的信息分析，而是使用數據集合的統計特征來(lái)抽取文檔的主要特征，將非主要特征拋棄。輸入一篇文檔，根據詞匯的IDF值過(guò)濾出一些關(guān)鍵特征，并且計算出這篇文檔的唯一的Hash值，那些Hash值相同的文檔就是重復的。
（2）使用SHA1作為Hash函數，因為它的速度很快而且適用于任何長(cháng)度。SHA-1生成一個(gè)20-byte 或者160-bit 的hash值并且使用一個(gè)安全的沖突消解算法，使得不同的標志串(token streams)生成相同的hash值的概率非常低。.把<docid, hashvalue>元組插入樹(shù)結構的時(shí)間復雜度是(O(d log d))，其他的如檢索數據結構（hash表）需要(O(d))。對重復(duplicate)的識別是在將數據插入hash數組或是樹(shù)結構中進(jìn)行的，任何的hash值的沖突就表示檢測到一個(gè)重復內容。
（3）最壞的情況下時(shí)間復雜度是(O(d log d))，速度比較快。
聯(lián)系客服
