四. 目前代表性解決方法分析

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)信息檢索領域的倒排文檔技術,存儲<Shingle,ID>信息以記錄某個特征在哪些文檔中出現(xià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ù)壓縮編碼后數(shù)值是否相同判斷)

(4) Super Shingle:關于Shingle的Shingle,從更大結(jié)構(gòu)上計算相似性以節(jié)省存儲空間;

2. Google可能采取的方法

a. 特征抽取

類似于Shingle方法,不同點在于:對于每個單詞根據(jù)HASH函數(shù)決定屬于哪個LIST,這樣每個文檔由若干個這樣的LIST構(gòu)成;

b. 壓縮編碼

FingerPrint方法;對于組成文檔的LIST進行FingerPrint方法計算;

c. 文檔相似度計算

編輯距離(Edit Distance):如果兩個文檔有任何一個FingerPrint相似就判斷為內(nèi)容接近.

d. 聚類方法

壹 先對<FingerPrint,Doc ID>按照Doc ID進行排序;然后采取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ù)進行識別然后再合并結(jié)果.相當于分布計算;


4．bloom filter(2005年)

(1).特征抽取方法

基于內(nèi)容的語塊（Content-defined chunking CDC）：CDC將文檔切分為變長的內(nèi)容片斷，切分邊界由rabin fringerprint和預先制定的maker數(shù)值匹配來進行判斷。

(2)編碼（構(gòu)造 bloom filter集合元素）

對于切分的片斷進行編碼。bloom filter的編碼方式如下：整個文檔是由片斷構(gòu)成的，文檔由長為m的二值數(shù)組表示。在將一個元素（內(nèi)容片斷）進行編碼插入集合的時候，利用k個不同的hash函數(shù)進行編碼，每個hash函數(shù)設置m個位置的某個位置為1。這種技術以前主要用來進行判斷某個元素是否被集合包含。

（3）相似度計算方法

bloom filter方法：對于兩個已經(jīng)編碼的文檔（兩個長度為m的二值數(shù)組），通過bit邏輯運算AND計算，如果兩者很多位置都同時為1，那么兩個文檔被認為是近似的。

（4）優(yōu)勢

1．文檔編碼形式簡潔，便于存儲。

2．由于計算相似性是BIT邏輯運算，所以速度快。

3．相對Shingling 方式來說便于判斷文檔包含關系。（某個文檔包含另外一個短小的文檔）


5．內(nèi)容 鏈接關系（2003年）

1．特征抽取方法

這個方法在抽取特征的時候同時考慮了文檔的內(nèi)容因素以及鏈接關系因素。

內(nèi)容因素：通過Random Projection技術將文檔內(nèi)容從高維空間映射到低維空間，并且由實數(shù)表示，如果兩個文檔映射后的數(shù)字越接近則表明兩者內(nèi)容越相似。

鏈接因素：通過考慮類似于PAGERANK的連接關系，將某個網(wǎng)頁的內(nèi)容因素計算獲得的分值通過鏈接傳播到其他網(wǎng)頁（傳播關系見下列公式），多次疊代計算后得到每個頁面的鏈接得分。

2．相似度計算方法

每個文檔由二元組<RP,HM>構(gòu)成，RP代表內(nèi)容部分的數(shù)值，HM代表鏈接關系代表的數(shù)值。如果兩個文檔每個項之間的差值都小于定向 值，則判斷兩個文檔是相似的。

3．效果

只采取內(nèi)容精度達到90%，兩者結(jié)合精度達到93%。從中看出，鏈接的作用并不明顯。這可能跟這個方法的鏈接使用方法有關，因為通過鏈接計算的還是內(nèi)容的情況。


6．I-Match方法（2002年）

（1）I-Match不依賴于完全的信息分析，而是使用數(shù)據(jù)集合的統(tǒng)計特征來抽取文檔的主要特征，將非主要特征拋棄。輸入一篇文檔，根據(jù)詞匯的IDF值過濾出一些關鍵特征，并且計算出這篇文檔的 的Hash值，那些Hash值相同的文檔就是重復的。

（2）使用SHA1作為Hash函數(shù)，因為它的速度很快而且適用于任何長度。SHA-1生成一個20-byte 或者160-bit 的hash值并且使用一個安全的沖突消解算法，使得不同的標志串(token streams)生成相同的hash值的概率非常低。.把<docid, hashvalue>元組插入樹結(jié)構(gòu)的時間復雜度是(O(d log d))，其他的如檢索數(shù)據(jù)結(jié)構(gòu)（hash表）需要(O(d))。對重復(duplicate)的識別是在將數(shù)據(jù)插入hash數(shù)組或是樹結(jié)構(gòu)中進行的，任何的hash值的沖突就表示檢測到一個重復內(nèi)容。

（3）更 壞的情況下時間復雜度是(O(d log d))，速度比較快。