張 玥,俞昊旻,張 奇,黃萱菁

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院,上海201203)

1 引言

在互聯(lián)網(wǎng)中存在大量內(nèi)容重復(fù)的相似網(wǎng)頁。根據(jù)Broder等人1997年統(tǒng)計的結(jié)果,大約有41%的網(wǎng)頁是重復(fù)的[1],在Fetterly等人2003年統(tǒng)計的結(jié)果中這個比例大約是29.2%[2]。很多Web應(yīng)用,例如文本聚類[1],網(wǎng)頁去重[3],抄襲檢測[4],社區(qū)發(fā)現(xiàn)[5],協(xié)同過濾[6]等任務(wù),都依賴于高效的文本拷貝檢測。

為了減少比較次數(shù),提升性能,倒排索引是拷貝檢測任務(wù)中常用的數(shù)據(jù)結(jié)構(gòu)。但隨著文檔集規(guī)模的增大,基于單臺電腦的索引結(jié)構(gòu)已經(jīng)不能有效處理大規(guī)模文檔集上的拷貝檢測任務(wù)。為此需要采用分布式索引,通過并行計算提高處理能力。同時,因為數(shù)據(jù)集的規(guī)模將一直增大,一個好的分布式索引,不僅要能提升拷貝檢測算法的效率,而且還必須具有良好的可擴展性。

Map-Reduce是一種并行編程范式,基于此范式可以實現(xiàn)具有良好可擴展性的算法[7]。本文中,我們采用Map-Reduce范式,對基于索引的文本拷貝檢測進行如下幾個方面的研究：

?第一,分析比較了兩種分布式索引結(jié)構(gòu)：Term-Split索引和Doc-Split索引,并給出了Map-Reduce范式下的建立這兩種索引的算法。

?第二,基于上述兩種索引結(jié)構(gòu),分別給出了Map-Reduce范式下的拷貝檢測算法。并且通過實驗,比較了兩種算法性能上的差異。

?第三,探討了Map-Reduce范式下,中間結(jié)果數(shù)量對整個算法性能的影響,并進一步討論如何更好的利用Map-Reduce范式實現(xiàn)算法的并行化。

本文的其余部分將按如下方式進行組織：第2節(jié)中,將說明基于索引的拷貝檢測方法的基本思想。第3節(jié)中,將簡要介紹Map-Reduce范式的相關(guān)內(nèi)容。第4節(jié)將具體闡述如何在Map-Reduce范式下實現(xiàn)基于索引的拷貝檢測方法。第5節(jié)和第6節(jié)分別介紹實驗和結(jié)論。

2 基于索引的拷貝檢測方法

給定一個文檔集,在其之上進行文檔間兩兩比較的拷貝檢測,需要對n(n-1)/2個文檔對進行相似度計算。這是一個O(n2)的算法。因此拷貝檢測算法中,一般會采用倒排索引來減少所需比較的次數(shù)。因此索引結(jié)構(gòu)的實現(xiàn)對拷貝檢測算法的性能有至關(guān)重要的影響。不同的索引結(jié)構(gòu)還會直接決定拷貝檢測算法的實現(xiàn)。

另一方面可以看出,傳統(tǒng)的單機索引結(jié)構(gòu)已經(jīng)難以適應(yīng)越來越大的數(shù)據(jù)規(guī)模,需要引入分布式索引,以適應(yīng)并行處理的需求。為此本文中將比較兩種分布式索引結(jié)構(gòu),在此基礎(chǔ)上,提出了兩種基于分布式Index的拷貝檢測算法。

為了方便討論,本文中將整個算法分成三步：

?第一步,Tokenize：遍歷文檔集中所有文檔,對每個文檔抽取特征。

?第二步,建立分布式索引：在Tokenize基礎(chǔ)上,建立分布式索引。

?第三步,基于索引的拷貝檢測：基于分布式索引,進行文檔兩兩之間的相似度計算,得到內(nèi)容重復(fù)的文檔對。

2.1 文本特征與相似度計算

進行有效的文本拷貝檢測,首先必須考慮兩個問題,第一,從文本中抽取何種的特征來表征一個文檔;第二,采用何種相似度的度量來表征兩篇文檔間的相似程度。本文中采用 Theobald等人提出的SpotSig算法對文檔進行特征抽取,將文檔表示成SpotSig(Si)的集合[8]。此外本文中將采用J accard相似度來表征文檔的相似度。給定兩個集合 A和B,集合 A、B的J accard相似度定義為[9]：

2.2 分布式索引

完整的索引一般包括兩個部分：由詞(Term)組成的詞典和包含某個詞的所有文檔(Doc)的ID列表(Posting List)[10]。要實現(xiàn)分布式索引,就需要按照某種方式將一個完整的索引分割開來。有兩種基本的分割方法,一種是按照詞分割(Term-Split),另一種是按照文檔分割(Doc-Split)。

圖1 一般索引結(jié)構(gòu)

如圖1所示,一個索引可以看成一個二維表格,表格的行表示不同的詞,表格的列表示不同的文檔。Term-Split相當(dāng)于將表格“按行橫向分割”,首先將詞典中的詞劃分為若干子集,每個節(jié)點只保存一個詞子集以及相應(yīng)的Posting List。Doc-Split則相當(dāng)于將表格“按列縱向分割”,將整個文檔集劃分為若干個子集,對每個子集分別建立獨立的索引,存儲在不同節(jié)點上。

2.3 基于索引的拷貝檢測方法

Lin提出了Map-Reduce范式下進行兩兩文檔間相似度計算的算法Postings Cartesian Product(PCP)[11]。本文中將基于此思想提出基于Term-Split索引的拷貝檢測方法。此外,本文將提出另外一種基于Doc-Split索引的拷貝檢測方法。

2.3.1 Term-Split方法

對于Term-Split索引,每個索引分塊中包含詞典中的一部分詞以及這些詞所對應(yīng)的Posting List。因此 Term-Split方法,首先從每個詞的 Posting List出發(fā),計算兩篇文檔在這個詞上的“部分相似度”(partial contributions)[11],再對這些“部分相似度”進行綜合,得出兩篇文檔間完整的相似度。在Lin的方法中采用的是向量點積作為相似度。而本文中采用J accard相似度。

如公式(1)所示,已知|A|、|B|,是兩個文檔的長度,所以只需要計算 A,B的交集大小,|A∩B|。亦即 A,B兩篇文檔共有的詞數(shù)量即可。結(jié)合Term-Split索引,若兩篇文檔出現(xiàn)在同一個Posting List中,表明這兩篇文檔在該詞上的“部分交集大小”為1。遍歷所有詞后,對所有文檔對的“部分交集大小”進行綜合,得到兩篇文檔的完整相似度,再與相似度閾值進行比較,決定是否為“拷貝”。

如圖2(a)所示,對于每一個詞所對應(yīng)的Posting List,將Posting List中的Id兩兩組合,作為一個可能相似的候選文檔對(candidate_pair)。考慮到兩篇文檔之間,每出現(xiàn)一個相同詞,就會產(chǎn)生一個這樣的文檔對。因此只需要對于每一個候選文檔對維護一個計數(shù)器(accumulator),統(tǒng)計該文檔對出現(xiàn)的次數(shù),得到的結(jié)果就是這兩篇文檔共有的詞數(shù)量。最后根據(jù)計數(shù)器的值,計算所有候選文檔對的相似度。

2.3.2 Doc-Split方法

對于Doc-Split索引,每個索引分塊中包含一部分文檔的完整索引。因此基于Doc-Split索引的方法,是把每一篇文檔作為一次查詢,在所有的索引分塊中查找與其相似的文檔。因為索引分塊和文檔內(nèi)容都分別分散在不同的節(jié)點上,具體實現(xiàn)時可以有兩種解決方式。一種方式是每次把作為查詢的文檔分發(fā)到各個節(jié)點上,在該節(jié)點上的索引中進行查重,另一種方式是每次把一個索引分塊分發(fā)到各個節(jié)點上,把該節(jié)點上的所有文檔作為查詢進行查重。考慮到索引比文檔本身更容易壓縮,且壓縮后體積較小,本文中采用后一種實現(xiàn)方式。

如圖2(b)所示,每次首先將一個索引分塊復(fù)制到所有節(jié)點上。然后在每個節(jié)點上,將該節(jié)點中的所有文檔作為查詢,在索引分塊中查找拷貝。對每個作為查詢的文檔(doc_q)維護一組計數(shù)器,記錄所有索引分塊中文檔(doc_i)與 doc_q的交集大小。每當(dāng)doc_q與doc_i有一個相同詞時,就將 doc_i對應(yīng)的計數(shù)器加1。最后根據(jù)計數(shù)器的值,計算doc_q與所有doc_i的相似度。

圖2 基于索引的拷貝檢測方法

3 Map-Reduce范式

Map-Reduce范式是J.Dean等人在2004年提出的分布式編程范式[7]。它通過面向函數(shù)的抽象使得分布式程序的開發(fā)變得簡單。在Map-Reduce編程范式下,數(shù)據(jù)被抽象為＜key,value＞的形式。而針對數(shù)據(jù)的操作被抽象為Map和Reduce兩個操作。用戶只需要提供自定義的兩個函數(shù)實現(xiàn)Map和Reduce。剩余的工作,諸如數(shù)據(jù)分發(fā),任務(wù)調(diào)度,容錯,任務(wù)同步等工作可以交由框架處理。

如圖3所示,一個Map-Reduce的任務(wù)包括兩個階段。第一個階段為Map操作,首先將輸入分割為小塊,每一個小塊都包含若干個＜key,value＞對。在這些數(shù)據(jù)分塊上執(zhí)行map操作,得到中間結(jié)果。中間結(jié)果同樣以＜key,value＞的形式表示。接著,中間結(jié)果按照key進行sort和group,使key相同的結(jié)果合并在一起。第二階段為Reduce操作,對相同key的中間結(jié)果進行合并得到最終結(jié)果,以＜key,value＞的形式輸出。

圖3 M ap-Reduce范式

4 實現(xiàn)細節(jié)

本節(jié)中將詳細介紹本文所述方法在Map-Reduce范式下的實現(xiàn)細節(jié)。本節(jié)共分為三部分,分別討論基于索引的拷貝檢測方法的三步。

4.1 Tokenize

第一步,Tokenize所有文檔。對于每個文檔的操作可以完全并行,實現(xiàn)起來相對簡單,僅需Map操作即可。如圖4所示,每個Map任務(wù)接受一批文檔作為輸入,其中文檔Id為key,文檔內(nèi)容為Value,對每個文檔,抽取SpotSigs特征,將文檔Id作為key,特征集合作為Value輸出。

4.2 建立分布式索引

第二步,對文檔建立索引。本文中分別給出兩種分布式索引在Map-Reduce范式下的實現(xiàn)。

如圖5(a)所示,Term-Split索引需要Map、Reduce兩步操作。在Map過程中以文檔 Id(Di)為Key,文檔的SpotSigs特征(Si)集合為Value輸入,輸出的中間結(jié)果以Si為Key,Di為Value。在Reduce過程中,將相同Si的中間結(jié)果收集在一起,將對應(yīng)的Di合并成列表。

如圖5(b)所示,Doc-Split索引相對簡單,只需一步Map即可。每個Map任務(wù)在整個文檔集的一個子集上迭代,只對子集中的文檔建立索引,不考慮其他子集中的文檔。

4.3 基于索引的拷貝檢測

第三步是基于索引的拷貝檢測。針對 Term-Split索引和 Doc-Split索引將分別給出Map-Reduce范式下的實現(xiàn)。

圖4 Tokenize文檔

圖5 建立分布式索引

Term-Split方法如圖6所示,在Map操作中,接收以 Term(Si)為 Key,Posting List(D1,D2,…)為Value的輸入,將Posting List中的文檔Id(D1,D2,…)兩兩組合作為中間結(jié)果輸出,其中文檔Id對(Di_Dj)作為Key,Value為該pair出現(xiàn)的次數(shù)。在Reduce操作中,將相同的Di_Dj收集在一起,將出現(xiàn)的次數(shù)相加得到文檔Di和文檔Dj之間相同的Term數(shù)量,再根據(jù)公式(1)計算得到Di與Dj之間的相似度,如果相似度超過閾值,則將結(jié)果以Dj_Dj作為Key,相似度作為Value輸出。

Doc-Split方法如圖7所示,初始化Map任務(wù)時,將這次迭代所需的索引分塊讀入內(nèi)存。Map操作以文檔Id(Di)為key,以文檔的SpotSigs特征(Si)集合為 Value,將輸入的文檔作為“Query”(Dq)在Index中查找拷貝。具體的做法是,根據(jù)文檔中的 Term在索引分塊中找到同樣包含這個Term的其他文檔(D1,D2,…)。然后統(tǒng)計這些文檔與(Dq)共有的Term數(shù),之后使用公式(1)計算相似度。最后,將相似度超過某個閾值的文檔對(Dq_Di)作為Key,相似度作為Value輸出。

圖6 Term-Split方法

圖7 Doc-Split方法

5 實驗

實驗使用了開源的 Map-Reduce框架 Hadoop①http：//hadoop.apache.org/。實驗將使用由10個節(jié)點構(gòu)成的集群。每個節(jié)點配置2個單核主頻為2.8GHz的4核CPU和32GB的內(nèi)存。本文將使用WT10G作為實驗數(shù)據(jù)。WT10G包含約160萬個文本文件,總大小約為10GB。本節(jié)中,將首先考察兩種文本拷貝檢測算法的精度,以確定算法的參數(shù)。然后在最優(yōu)精度的參數(shù)下,對兩種算法的性能進行比較。

5.1 精度

在文本拷貝檢測算法中,相似度閾值(τ)對結(jié)果的精度有比較大的影響。此外,在通過索引進行相似度計算時,往往會設(shè)置IDF值限制條件,忽略掉IDF值過高或過低的Term,這也會對精度產(chǎn)生影響。本實驗的主要目的是,在不同的IDF限制條件下,找出使得精度最好的τ。為此,本實驗將在人工標(biāo)注的Golden Set上進行。該文檔集是從WT10G中隨機抽取出來,經(jīng)過人工標(biāo)注得到的,包含1000篇文檔。此外,試驗中所采用的IDF值是在整個WT10G文檔集上統(tǒng)計的結(jié)果?？紤]到本文所述兩種算法的實現(xiàn)在精度方面具有完全一致的特性。因此,在下面論述中對這兩種算法不作區(qū)分。

如圖8所示,當(dāng)IDF值為0.0～1.0以及 0.1～0.95時,τ取 0.4可以使F1 Score達到最大,均為0.953。τ過小會導(dǎo)致Precision值的下降,τ過大會導(dǎo)致Recall值急劇下降。當(dāng)IDF值為0.2～0.85時,因為更多的詞在計算時被忽略,因此需要將τ設(shè)得略低一些,當(dāng)τ取0.3時,F1 Score達到最大,為0.954。該實驗結(jié)果與 Theobald等人報告的τ取0.44時,F1 Score為0.94的結(jié)果基本相符[8]。

圖 8 算法精度 V.S.相似度閾值(τ)

5.2 效率

通過前面的實驗已經(jīng)得到在不同IDF值設(shè)定下使得精度最優(yōu)的τ：IDF為[0.0,1.0]時,τ取0.4;IDF為[0.1,0.95]時,τ取 0.4;IDF為[0.3,0.85]時,τ取0.3。在本實驗中,將在上述三種不同參數(shù)配置下,對Term-Split和Doc-Split拷貝檢測方法進行比較。本實驗使用WT10G的八分之一作為測試集合,約包含20萬篇文檔。

由表1可見,Doc-Split方法的效率要明顯好于Term-Split的方法。這主要是因為在Term-Split索引中,每個節(jié)點只包含一部分詞信息,只能計算文檔對之間的“部分交集大小”,在最終匯總前不能確定兩個文檔是否相似。為此必須維護大量的計數(shù)器,產(chǎn)生大量的中間結(jié)果。

表1 Term-Split V.S.Doc-Split

5.3 可擴展性

在本實驗中,將驗證兩種拷貝檢測算法的可擴展性。首先,將考察數(shù)據(jù)集規(guī)模與運行時間的關(guān)系。以檢驗兩種算法在數(shù)據(jù)集規(guī)模不斷增加的情況下的適應(yīng)性。然后,將考察集群中CPU數(shù)量與運行時速度的關(guān)系。以檢驗兩種算法的加速性能。實驗中IDF取[0.3,0.85],τ取0.3。

如圖9(a)所示,當(dāng)文檔數(shù)量達到 80萬時,Term-Split方法在本次實驗的硬件條件下已經(jīng)無法進行(因為128GB的硬盤被中間數(shù)據(jù)耗光,算法在運行了4個多小時后終止)。因為中間數(shù)據(jù)的數(shù)量太大,當(dāng)數(shù)據(jù)集規(guī)模很大時,Term-Split方法只能通過Lin提出的近似方法[11]計算非精確解。而相比之下 Doc-Split方法則表現(xiàn)出良好的性能。使用Doc-Split方法對整個WT10G數(shù)據(jù)集進行實驗的時間為5627.457秒。同時如圖9(b)所示,在加速性方面Doc-Split方法也優(yōu)于Term-Split方法。在CPU數(shù)量增加4倍的情況下,達到了2.56倍的速度提升。這是因為Map-Reduce范式下的程序,具有天然的可擴展性,可以通過增加節(jié)點數(shù)量提高處理能力。

圖9 可擴展性實驗

6 結(jié)論

本文對Term-Split和Doc-Split兩種不同的分布式索引結(jié)構(gòu)進行了比較,并分別給出了Map-Reduce范式下建立這兩種索引的算法,以及基于這兩種索引的拷貝檢測算法。最后通過實驗比較了上述兩種算法的性能。

實驗表明Doc-Split方法在進行拷貝檢測任務(wù)時更有效,而Term-Split方法因為產(chǎn)生了大量中間結(jié)果使得效率大大降低。因此中間結(jié)果數(shù)量的多少,直接影響了采用兩步并行(Map,Reduce)的Map-Reduce程序的運行效率。當(dāng)中間結(jié)果數(shù)量過多時,對中間結(jié)果進行排序,分組以及分發(fā)的操作代價已經(jīng)遠遠超出了兩步并行的好處。因此不適合采用兩步并行,應(yīng)該改為一步并行。比如本文所述的Doc-Split方法,沒有采用Reduce操作,而是每次將一部分索引分塊復(fù)制到所有節(jié)點上。因為僅憑單個節(jié)點上的信息已經(jīng)可以得到結(jié)果,就無需進行Reduce操作,也回避了中間結(jié)果的問題。

綜合來看,Map-Reduce范式可以有效地解決算法并行化的問題。但因為不同算法的差異性,在實現(xiàn)并行化時,需要結(jié)合算法本身的特性進行考慮,才能最大限度的發(fā)揮Map-Reduce范式的好處。

[1]A.Z.Broder,S.C.Glassman,M.S.Manasse et al.Syntactic clustering of the web[J].Computer Networks,1997,29(8-13)：1157-1166.

[2]D.Fetterly,M.Manasse,and M.Najork.On the E-volution of Clusters of Near-DuplicateWeb Pages[C]//Proceedings of the 1st Latin American Web Congress.Washington,DC,USA：IEEE Computer Society,2003：37.

[3]J.Cho,N.Shivakumar,and H.Garcia-Molina.Finding replicated web collections[C]//ACM SIGMOD Record.New York,NY,USA：ACM,2000：355-366.

[4]T.C.Hoad and J.Zobel.Methods for identifying versioned and plagiarized documents[J].JASIST,2003,54(3)：203-215.

[5]E.Spertus,M.Sahami,and O.Buyukkokten.Evaluating similarity measures：a large-scale study in the orkut social network[C]//Proceedings of the 11th ACM SIGKDD.New York,NY,USA：ACM,2005：678-684.

[6]R.J.Bayardo,Y.Ma,and R.Srikant.Scaling up all pairs similarity search[C]//Proceedings of the 16th WWW.New York,NY,USA：ACM,2007：131-140.

[7]J.Dean and J.Ghemawat.Map-Reduce：Simplified Data Processing on Large Clusters[J].Communications of the ACM,2004,51(1)：107-113.

[8]M.Theobald,J.Siddharth,and A.Paepcke.Spotsigs：robust and efficient near duplicate detection in large web collections[C]//Proceeding of 31th SIGIR,New York,NY,USA ：ACM,2008：563-570.

[9]Pang-Ning Tan,Michael Steinbach,Vipin Kumar.Introduction to Data Mining[M].Addison-Wesley,2005.

[10]C D Manning,P Raghavan,H Schutze,An Introduction to Information Retriveval[M].Cambridge University Press,2008.

[11]J.Lin.Brute force and indexed approaches to pairwise document similarity comparisons with mapreduce[C]//Proceedings of 32th SIGIR,New York,NY,USA ：ACM,2009：155-162.