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