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

1. Shingle方法(1997年)

a. 特征抽取

Shingle方法:所謂Shingle類似于自然語(yǔ)言處理中常用的N-GRAM方法,就是將相互連續(xù)出現(xiàn)窗口大小為N的單詞串作為一個(gè)Shingle,兩者的不同點(diǎn)在于Shingle是這些串的集合,相同的串會(huì)合并為一個(gè),而N-GRAM則由于考慮的是文本線性結(jié)構(gòu),所以沒(méi)有相同合并步驟.每個(gè)Shingle就是文檔的一個(gè)特征,一篇文檔就是由所有這些Shingle構(gòu)成的.

b. 壓縮編碼

40 bit長(zhǎng)度 Rabin FingerPrint方法;至于存儲(chǔ)方式則類似于傳統(tǒng)信息檢索領(lǐng)域的倒排文檔技術(shù),存儲(chǔ)Shingle,ID>信息以記錄某個(gè)特征在哪些文檔中出現(xiàn)過(guò),然后進(jìn)一步計(jì)算文檔的相似性;

c. 文檔相似度計(jì)算

(1) 相似度:任意兩個(gè)文檔A和B,相似度指的是兩者相同的Shingle數(shù)目占兩者Shingle數(shù)目總和的比例;

(2) 包含度:指的是兩者相同的Shingle數(shù)目占某篇文檔Shingle數(shù)目的比例;

d. 優(yōu)化措施:

(1) 分布計(jì)算然后合并;

(2) 拋棄超高頻出現(xiàn)Shingle,分析發(fā)現(xiàn)這些Shingle是無(wú)意義的片斷;

(3) 完全相同文檔保留一份進(jìn)行聚類;(文檔是否完全相同根據(jù)壓縮編碼后數(shù)值是否相同判斷)

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

2. Google可能采取的方法

a. 特征抽取

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

b. 壓縮編碼

FingerPrint方法;對(duì)于組成文檔的LIST進(jìn)行FingerPrint方法計(jì)算;

c. 文檔相似度計(jì)算

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

d. 聚類方法

首先對(duì)FingerPrint,Doc ID>按照Doc ID進(jìn)行排序;然后采取Union Find聚類方法,聚類結(jié)果就是相似文檔集合;

e. 優(yōu)化措施

3. HP實(shí)驗(yàn)室方法(2005年)

a. 特征抽取

基于內(nèi)容的Chunk方法:變長(zhǎng)而非定長(zhǎng)的Chunk算法(TTTD算法);將一篇文檔分解為若干個(gè)長(zhǎng)度不同的Chunk,每個(gè)Chunk作為文本的一個(gè)特征.與shingle方法相比這種變長(zhǎng)Chunk方法能夠增加系統(tǒng)招回率;

b. 壓縮編碼

128bit MD5 HASH方法;每篇文章壓縮編碼后由若干 Chunk 長(zhǎng)度, 定長(zhǎng)HASH編碼>二元組構(gòu)成;

c. 文檔相似度計(jì)算

(1) 構(gòu)建所有文檔和Chunk構(gòu)成的二分圖;

(2) 找到文檔A包含的所有CHUNK,計(jì)算這些CHUNK還被哪些其它文檔包含;

(3) 計(jì)算這些文檔和A的相似性;



d. 聚類方法:Union Find 算法

e. 優(yōu)化措施:Bipartite 劃分,本質(zhì)上是將大規(guī)模數(shù)據(jù)分成小規(guī)模數(shù)據(jù)進(jìn)行識(shí)別然后再合并結(jié)果.相當(dāng)于分布計(jì)算;


4．bloom filter(2005年)

(1).特征抽取方法

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

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

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

（3）相似度計(jì)算方法

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

（4）優(yōu)勢(shì)

1．文檔編碼形式簡(jiǎn)潔，便于存儲(chǔ)。

2．由于計(jì)算相似性是BIT邏輯運(yùn)算，所以速度快。

3．相對(duì)Shingling 方式來(lái)說(shuō)便于判斷文檔包含關(guān)系。（某個(gè)文檔包含另外一個(gè)短小的文檔）


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

1．特征抽取方法

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

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

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

2．相似度計(jì)算方法

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

3．效果

只采取內(nèi)容精度達(dá)到90%，兩者結(jié)合精度達(dá)到93%。從中看出，鏈接的作用并不明顯。這可能跟這個(gè)方法的鏈接使用方法有關(guān)，因?yàn)橥ㄟ^(guò)鏈接計(jì)算的還是內(nèi)容的情況。


6．I-Match方法（2002年）

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

（2）使用SHA1作為Hash函數(shù)，因?yàn)樗乃俣群芸於疫m用于任何長(zhǎng)度。SHA-1生成一個(gè)20-byte 或者160-bit 的hash值并且使用一個(gè)安全的沖突消解算法，使得不同的標(biāo)志串(token streams)生成相同的hash值的概率非常低。.把docid, hashvalue>元組插入樹(shù)結(jié)構(gòu)的時(shí)間復(fù)雜度是(O(d log d))，其他的如檢索數(shù)據(jù)結(jié)構(gòu)（hash表）需要(O(d))。對(duì)重復(fù)(duplicate)的識(shí)別是在將數(shù)據(jù)插入hash數(shù)組或是樹(shù)結(jié)構(gòu)中進(jìn)行的，任何的hash值的沖突就表示檢測(cè)到一個(gè)重復(fù)內(nèi)容。

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