張 敏

(河南理工大學(xué) 測繪與國土信息工程學(xué)院，河南 焦作 454003)

0 引 言

隨著數(shù)字信息量的幾何式增長，數(shù)據(jù)占用空間越來越大。在過去的幾年里，存儲系統(tǒng)容量從數(shù)十GB發(fā)展到數(shù)百TB，甚至數(shù)PB[1]。隨著數(shù)據(jù)指數(shù)級增長，管理保存數(shù)據(jù)成本及數(shù)據(jù)中心空間和能耗也變得越來越嚴(yán)重。研究發(fā)現(xiàn)，保存的數(shù)據(jù)中有六成以上是冗余的，而且隨著時間的推移，這種問題會更加嚴(yán)重。為了緩解存儲系統(tǒng)的空間增長問題，最大程度地利用已有資源，重復(fù)數(shù)據(jù)查找刪除技術(shù)已成為一個熱門的研究課題。一方面，重復(fù)數(shù)據(jù)查找可以對存儲空間進(jìn)行優(yōu)化，消除分布在存儲系統(tǒng)中的相同文件或者數(shù)據(jù)塊。另一方面，可以減少在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量，進(jìn)而降低能量消耗和網(wǎng)絡(luò)成本，并為數(shù)據(jù)復(fù)制大量節(jié)省網(wǎng)絡(luò)帶寬。

1 相關(guān)工作

相似重復(fù)記錄的檢測主要有排序合并法、建索引法、機器學(xué)習(xí)法和基于特定領(lǐng)域知識法，其中排序合并和建索引的方法是不依賴于特定應(yīng)用領(lǐng)域的通用方法；文獻(xiàn)[2]采用排序合并的方法，根據(jù)用戶選定的若干個屬性字符串合并作為鍵進(jìn)行排序后，采用固定大小的滑動窗口進(jìn)行聚類來識別相似重復(fù)記錄；文獻(xiàn)[3]介紹的根據(jù)不同的屬性進(jìn)行多路排序合并，并采用優(yōu)先隊列取代固定大小的滑動窗口來進(jìn)行聚類。這兩種方法之主要不足在于大數(shù)據(jù)量記錄及排序引起大量IO操作，成為算法運行效率的瓶頸；另一方面由于字符串排序?qū)ψ址恢妹舾?，所以不能保證將相似的重復(fù)記錄放在鄰近的位置，因而決定了后來的聚類操作不一定能將相似記錄識別出來。采用R樹建索引的方法[4]中首先依據(jù)Fastmap方法選取若干個記錄作為軸(Pivot)，各個記錄依據(jù)這若干個軸計算它本身在多維空間中的坐標(biāo)，然后采用R樹進(jìn)行多維空間相似性連接來實現(xiàn)相似記錄的識別。但是由于Fastmap方法本身不可收縮性(Contractive)，因此這種映射方法會造成大量的數(shù)據(jù)丟失，且由于維度災(zāi)難，也就決定了維度不能過高，使得這種方法不具有通用性。文獻(xiàn)[5]針對的是數(shù)據(jù)在線去重問題，它是在有干凈參照表的條件下進(jìn)行數(shù)據(jù)清洗的方法。

通過向量空間模型(Vector Space Model,VSM)計算相似度，但這種方法存在的問題是需要對文本兩兩進(jìn)行相似度比較，無法擴(kuò)展到海量文本的處理。因此，若能結(jié)合海量數(shù)據(jù)的計算模型和VSM，先對文本進(jìn)行分詞預(yù)處理，然后建立文本向量，把相似度的計算轉(zhuǎn)換成某種特征向量距離的計算(如Jaccard相似系數(shù)等)，則可以實現(xiàn)海量數(shù)據(jù)相似度檢測，從而解決海量數(shù)據(jù)的去重問題。

2 Simhash算法與云計算

2.1 Jaccard相似度

集合S和T之間的Jaccard相似度是指集合S和T的交集和并集之間的比值，即Jaccard_Sim(S,T)=|S∩T|/|S∪T|。例如：S={a,d}，T={a,c,d}，則Jaccard_Sim(S,T)=|{a,d}|/|{a,c,d}|=2/3。一篇文檔可能包含上成千上萬個元素，對大量的文檔，保存這些元素需要很大的空間，通過一種方法來減少元素個數(shù)，并且通過少量元素依然可以得到原來的Jaccard相似度，過程如下：

假設(shè)對元素集E={a,b,c,d,e}上的集合S1={a,d}，S2={a,c,d}，其特征矩陣為

定義f為E上的一個映射關(guān)系，將f作用于S1，S2上，其特征矩陣為

取m1為f(S1)中的最小值，即m1=min{f(a),f(d)}，m2為f(S2)中的最小值，即m2=min{f(a),f(c),f(d)}，則m1與m2相等的概率為：P(m1=m2)=P(min{f(a),(b)}=min{f(a),f(c),f(d)})=|{f(a),f(d)}|/|{f(a),f(c),f(d)}|=|{a,d}|/|{a,c,d}|=Jaccard_Sim(S1,S2)。

因此，令m1為S1的一個簽名，m2為S2的一個簽名，通過少量的簽名，能夠得Jaccard_Sim(S1,S2) 的一個近似值。將上面的映射關(guān)系f替換為一個E上的隨機哈希函數(shù)，這個結(jié)論依然成立。所以，對一篇文檔使用n個隨機哈希函數(shù)可以得到n個簽名，稱為文檔的最小哈希簽名，并且通過比較最小哈希簽名可以得到兩篇文檔間的Jaccard相似度。

對兩篇文檔[9]，如果它們相似，則它們的哈希值有較高的概率是相同的。有了文檔的最小哈希簽名，就能實現(xiàn)這種哈希方法，將包含b×r個值最小哈希簽名分為b等份，每份r個，對兩個文檔，定義P為兩個文檔至少含有1個相同份的概率，顯然，文檔間的Jaccard相似度越高，哈希簽名具有相同值的位數(shù)就越多，概率P就越大。

2.2 Simhash算法

SimHash通過產(chǎn)生簽名用來檢測原始內(nèi)容的相似度。假設(shè)輸入的是一個文檔的特征集合，每個特征有一定的權(quán)重。特征可以是文檔中的詞，其權(quán)重可以是這個詞出現(xiàn)的次數(shù)，SimHash能夠?qū)⑵溆成涞揭粋€低維向量空間，并根據(jù)該低維向量產(chǎn)生一個很小的指紋；算法過程如下：

(1) 將一個f維的向量V初始化為0；f位的二進(jìn)制數(shù)S初始化為0；

(2) 對每一個特征:用傳統(tǒng)的hash算法對該特征產(chǎn)生一個f位的簽名b。對i=1到f,如果b的第i位為1，則V的第i個元素加上該特征的權(quán)重；否則，V的第i個元素減去該特征的權(quán)重；

(3) 如果V的第i個元素大于0，則S的第i位為1，否則為0；

(4) 輸出S作為簽名。

與傳統(tǒng)的加密型哈希函數(shù)相比，SimHash擁有一個顯著特征，即越相似的原始信息會生成越相似的哈希值，也就是哈希值的海明距離越小。而傳統(tǒng)的哈希函數(shù)，為兩個不同的原始信息生成哈希值時，即使它們實際上很相近，計算得出的哈希值之間漢明距離也可能非常大，無法用于度量原始信息的相似度。

2.3 MapReduce

MapReduce[6]是一種高效的分布式編程模型，其工作機制如圖2所示,用于處理和生成大規(guī)模數(shù)據(jù)集的實現(xiàn)方式[7]。MapReduce中兩項核心操作為Map和Reduce操作，其Map操作獨立地對每個元素進(jìn)行操作；Reduce操作對N個Map結(jié)果進(jìn)行排序收集，也就是Map[1，2，…，N]的結(jié)果是Reduce操作的參數(shù)。在MapReduce編程模型中，只要沒有函數(shù)修改或依賴于全局變量，N個Map操作的執(zhí)行順序可以是無序的；而且，Map和Reduce都以其他的函數(shù)作為輸入?yún)?shù)，正是因為可以同其他函數(shù)相結(jié)合，所以只要把Map和Reduce這兩個函數(shù)進(jìn)行并行化處理，就無需面面俱到地把所有的函數(shù)全部考慮到，這樣便形成了一個以Map和Reduce為基礎(chǔ)的編程模型。該模型為用戶提供編寫與具體應(yīng)用相關(guān)的函數(shù)的編程接口，用戶把計算需求歸結(jié)為Map和Reduce操作，通過這個接口提交到MapReduce系統(tǒng)上就可以獲得并行處理的能力，所以，這種特性使MapReduce模型非常適合于對大規(guī)模數(shù)據(jù)進(jìn)行并行處理。

圖2 MapReduce工作機制

3 MapReduce下相似文檔查找流程及算法

根據(jù)MapReduce工作機制，提出MapReduce下以Simhash算法查找近似文本檢測流程，如圖3所示。海量文檔集存儲在Hadoop分布式文件系統(tǒng)(HDFS)中，術(shù)語集和文本-術(shù)語關(guān)系集存儲在分布式key-value系統(tǒng)HBase中，特征提取算法和相似度計算算法采用分布式計算模型Map/Reduce。此外，由于海量文檔集的文本數(shù)量眾多并且大小相對較小[9-10]，使用HDFS提供的SequenceFile InputFormat方法[11]，將文件名作為key、文件作為value，以key-value的形式將文本存儲在Sequence File。同樣，對提取出特征向量或指紋也以key-value的形式存儲在另外的Sequence File[12]。

(1) 預(yù)處理。主要包括: 預(yù)處理文本文件、存儲術(shù)語集和文本-術(shù)語對應(yīng)關(guān)系[13]。由于文本文件的格式多樣性，為求統(tǒng)一，將各種格式的文本轉(zhuǎn)化為TXT文件。對術(shù)語集和文本-術(shù)語對應(yīng)關(guān)系，使用HBase提供的應(yīng)用程序接口將其存儲。

圖3 基于MapReduce的文本近似檢測流程

(2) 特征提取。首先將文本表示成詞頻向量，然后計算詞頻向量指紋。由于學(xué)習(xí)資源存在領(lǐng)域術(shù)語的特征，文本將表示為一個高維術(shù)語詞頻向量，然后再使用SimHash算法生成指紋。為提高特征提取算法的效率，用Map/Reduce模型提取文檔集特征。對給定的文檔集，特征提取Map/Reduce任務(wù)只需運行1次，輸入是文檔集，輸出是Sequence File，其中文件名作為key，文件的指紋作為value。

特征提取過程包括提取詞頻向量、生成SimHash指紋和生成Sequence File。提取詞頻向量提取詞頻向量是將文本轉(zhuǎn)換為一個n維詞頻向量；SimHash使用SimHash算法計算該詞頻向量的64 b SimHash指紋；生成SequenceFile得到文本的指紋后，將文件名作為key，其64 b SimHash指紋作為value，寫入Sequence File中。

(3) 相似度計算。用于比較待測文本和文檔集文本之間的相似度。它使用待測文本的指紋和文檔集特征提取輸出的SequenceFile作為輸入，采用各種相似度度量方法(例如對SimHash指紋則采用海明距離)，進(jìn)行近似檢測[14]，算法的偽代碼如下所示：

Class Mapper{

method map(〈label,txtid〉,Vector)

write(〈label,txtid〉,Vector)

}

Class Reducer{

Matrix matrix;//每一行對應(yīng)一個類別的向量和

int i=0;

String[]labels;

void setup(){

int i=0;

SequenceFile.Reader reader=new

SequenceFile.Reader(“exameDataSet”);

While(reader.next(key.value)){

matrix.assignRow(i,value);

labels[i]=key;

}

}

void map(〈label,txtid〉,vector){

double sim=0;//最大相似度值

String testLabel;//測試類標(biāo)

for(int i=0;i〈ma.numRows;i++){

double cos=cos_sim(Vector,ma.getRow(i));

if(max〈cos)max=cos;

testLable=Lables[i];

write(lable,〈testLable,txtid〉;

}

4 實驗結(jié)果與驗證

本實驗基于河南理工大學(xué)高性能計算平臺進(jìn)行，該平臺由曙光刀片機構(gòu)建，共有共34個節(jié)點：1個管理節(jié)點，1個IO節(jié)點，32個計算節(jié)點，千兆存儲網(wǎng)絡(luò)。系統(tǒng)采用RedHat Linux構(gòu)建高計算集群。單節(jié)點配置Intel Xeon E5504 2.00 GHz CPU，8 GB內(nèi)存，120 GB硬盤。軟件配有J2SE 6.0，Hadoop 0.20.2，HBase-0.20.6等。在該環(huán)境下，選擇1個為NameNode作為控制節(jié)點、 6個DataNode參與計算任務(wù)。

為驗證近似文本檢測算法能夠適用于海量數(shù)據(jù)，算法將在兩個中文數(shù)據(jù)集上做實驗，第一是譚松波(TanCorp-10)等搜集的文檔[15]，共14 150篇、29.5 MB、包含10個類別，如表1所示；第二個數(shù)據(jù)集是搜狗新聞2008年上半年(SogouCS)國內(nèi)外18個頻道[16]，提供URL和正文信息，共2 101 582篇文檔、3.33 GB、包含15個類別如表1、2所示。

表1 TanCorp-10數(shù)據(jù)集分布

表2 SogouCS數(shù)據(jù)集分布

4.1 執(zhí)行時間對比

實驗分別在單機和Hadoop的全分布式環(huán)境下進(jìn)行，采用90%作為訓(xùn)練集，10%為測試集，執(zhí)行時間如圖4所示。

圖4 單機和全分布式執(zhí)行時

從上圖可知，對于小數(shù)據(jù)集(TanCorp)在分布式環(huán)境效果不明顯，其原因是：在小數(shù)據(jù)集下，Hadoop對數(shù)據(jù)是分塊處理的，默認(rèn)64 MB為一個數(shù)據(jù)塊，如果存在大量小數(shù)據(jù)文件，這樣的小數(shù)據(jù)文件達(dá)不到Hadoop默認(rèn)數(shù)據(jù)塊的大小時，就要按一個數(shù)據(jù)塊來進(jìn)行處理。這樣處理帶來結(jié)果是：存儲大量小文件占據(jù)存儲空間，致使存儲效率不高、檢索速度也比大文件慢；而且進(jìn)行MapReduce運算時，小文件消費計算能力。對于大數(shù)據(jù)集，設(shè)計的算法優(yōu)勢明顯突出。

4.2 相似度計算時間對比

分別在上述兩個數(shù)據(jù)集使用Map/Reduce進(jìn)行實驗，對比歐氏距離、余弦相似度、相關(guān)系數(shù)、SimHash的相似度計算的執(zhí)行時間，其執(zhí)行時間如表3所示。

表3 相似度時間對比表

從上表可知，在TanCorp-10中，相對于歐氏距離、余弦相似度和相關(guān)系數(shù)的相似度計算執(zhí)行時間，SimHash的相似度計算的執(zhí)行時間分別減少了137.5%、137.5%、143.8%；在SogouCSS中，執(zhí)行時間分別減少了355.8%、381.4%、406.9%。這驗證了基于SimHash指紋的海明距離比較在時間上優(yōu)于經(jīng)典的文本相似度計算方法；也印證5.1節(jié)中，在處理大數(shù)據(jù)集上，MapReduce優(yōu)勢明顯突出。

5 結(jié) 語

相對于以往相似重復(fù)記錄的檢測方法，本文提出了基于MapReduce的文本近似檢測流程，并設(shè)計了SimHash相似度算法，最后在實驗環(huán)境下進(jìn)行了驗證。通過實驗可知，SimHash相似度的算法應(yīng)用在MapReduce下，非常適合海量數(shù)據(jù)集的文檔相似度計算，極大降低了時間開銷，為解決海量數(shù)據(jù)去重問題提供一定的參考價值。

[1] Agrawal D, Bernstenin P, Bertino E,etal. Challenges and opportunities with big data-A community white paper developed by leading researchers across the United States[R/OL]. [2012-10-02]. http://cra.org/ccc/docs/init/bigdata/whitepaper.pdf

[2] 付印金, 肖 儂, 劉 芳. 重復(fù)數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進(jìn)展[J]. 計算機研究與發(fā)展, 2012,49(1):12-20.

FU Yin-jin, XIAO Nong, LIU Fang. Key technology research progress of duplicate data de-duplication [J]. Computer Research and Progress, 2012,49(1):12-20.

[3] 敖 莉, 舒繼武, 李明強,等. 重復(fù)數(shù)據(jù)刪除技術(shù)[J].電子學(xué)報, 2010,21(5): 916-918.

AO Li, SHU Ji-wu, LI Ming-qiang,etal. Duplicate data de-duplication technology [J]. Journal of electronic, 2010,21(5): 916-918.

[4] 韓京宇, 徐立臻. 一種大數(shù)據(jù)量的相似記錄檢測方法[J].計算機研究與發(fā)展, 2005,42(12):2207-2209.

HAN Jing-yu, XU Li-zhen. A kind of detection approach of duplicate recorder for massive data [J]. Computer Research and Progress, 2005,42(12):2207-2209.

[5] 李星毅,包從劍. 數(shù)據(jù)倉庫中的相似重復(fù)記錄檢測方法[J].電子科技大學(xué)學(xué)報, 2007,36(6):1273-1276.

LI Xing-yi, BAO Cong-jian. Detecting approach for similar duplicate recorder in data warehouse [J]. Journal of electronic technology university, 2007,36(6):1273-1276.

[6] 李建江,崔 健. MapReduce并行編程模型研究綜述[J].電子學(xué)報,2011,39(11): 2639-2645.

LI Jian-jiang, CUI Jian. Research review of parallel programming model [J]. Journal of electronic, 2011,39(11): 2639-2645.

[7] 陳 康,鄭緯民.云計算:系統(tǒng)實例與研究現(xiàn)狀[J].軟件學(xué)報,2009,20(5):1337-1348.

CHEN Kang, ZHENG Wei-min. Cloud computing: System instance and research situation [J]. Journal of software, 2009,20(5):1337-1348.

[8] 張組斌， 徐 欣， 龍 君,等. 文本相似度檢測的參數(shù)關(guān)聯(lián)和優(yōu)化[J] 中文計算機系統(tǒng), 2011, 32(5): 983-988.

ZHANG Zu-ping, XU Xin, LONG Jun,etal．Parameters correlation and optimization in text similarity measurement[J]．Journal of Chinese Computer Systems, 2011, 32(5): 983-988.

[9] 程國達(dá), 蘇杭麗. 一種檢測漢語相似重復(fù)記錄的有效方法[J]. 計算機應(yīng)用, 2005, 25(6): 1361-1365.

CHENG Gou-da, SU Hang-li. A kind of valid method of detecting Chinese similar recorder [J]. Computer application, 2005, 25(6): 1361-1365.

[10] Nature. Big Data [EB/OL]. [2012-10-02]. http://www.nature.com/news/specials/bigdata/index.html

[11] Shahri H H. Eliminating duplicates in information integration: an adaptive, extensible framework [J].IEEE Intelligent Systems, 2006, 12(5): 63-71.

[12] A Verma,N Zea,etal. Breaking the Mapreduce Stage Barrier. Proc of IEEE International Conference on Cluster Computing[C].Los Alamitos: IEEE Computer Society,2010:235-244.

[13] 朱恒民,王寧生.一種改進(jìn)的相似重復(fù)記錄檢測方法[J].控制與決策, 2006, 21(7): 805-808.

ZHU Hen-min, WANG Ning-sheng. A kind of improved detecting method for similar duplicate recorder [J]. Control and decision, 2006, 21(7): 805-808.

[14] Paul S, Saravanan D V. Hash Partitioned Apriori in Parallel and Distribute Data Mining Environment with Dynamic Data Allocation Approach [C] //ICCSIT'08 Proceedings of the 2008 International Conference on Computer Science and Information Technology. 2008.