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