彭雙和，圖爾貢·麥提薩比爾，周巧鳳

(北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044)

基于Simhash的中文文本去重技術(shù)研究

彭雙和，圖爾貢·麥提薩比爾，周巧鳳

(北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044)

隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，各領(lǐng)域存儲系統(tǒng)中的數(shù)據(jù)存儲量迅猛上升，而其中的冗余數(shù)據(jù)也呈不斷增加趨勢。以往的研究表明，某些存儲系統(tǒng)中的冗余數(shù)據(jù)已達(dá)60%，其存儲管理成本較高。處理冗余數(shù)據(jù)已成為目前存儲系統(tǒng)研究的熱點(diǎn)。為此，提出了一種基于Simhash的中文文本去重方案。該方案采用數(shù)據(jù)塊作為粒度對重復(fù)數(shù)據(jù)進(jìn)行去重處理，主要是將中文文本中的“。？！”等特殊字符作為分割點(diǎn)，對數(shù)據(jù)進(jìn)行相應(yīng)的分塊處理，并以Simhash作為唯一標(biāo)識，通過海明距離(Hamming Distance)來判斷其相似性并以此為依據(jù)進(jìn)行數(shù)據(jù)去重。對比驗(yàn)證實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)的hash去重技術(shù)，提出的基于Simhash的去重方案具有更高的去重率和準(zhǔn)確率，展現(xiàn)了較好的應(yīng)用價(jià)值和應(yīng)用前景。

重復(fù)數(shù)據(jù)刪除；Simhash；hash；數(shù)據(jù)分塊

0 引 言

隨著計(jì)算機(jī)與信息技術(shù)的不斷發(fā)展，信息存儲技術(shù)廣泛應(yīng)用于各個(gè)領(lǐng)域，導(dǎo)致數(shù)字化信息量迅猛增加。云存儲、云計(jì)算技術(shù)的出現(xiàn)對數(shù)據(jù)中心存儲能力也提出了更高要求。數(shù)據(jù)量出現(xiàn)指數(shù)級上升趨勢，已從TB級提高到EB級，而云數(shù)據(jù)流量在2013-2018年間以3.9倍的速度增長[1]。因此，企業(yè)在面臨龐大數(shù)據(jù)量的同時(shí)，更面臨著數(shù)據(jù)的備份、恢復(fù)、管理以及保存數(shù)據(jù)成本等一系列問題。研究表明，在應(yīng)用系統(tǒng)所保存的數(shù)據(jù)中，冗余數(shù)據(jù)約占60%左右[2]，數(shù)據(jù)量增長的同時(shí)冗余數(shù)據(jù)也不斷增多，為了確保數(shù)據(jù)保存的可靠持久，需要花費(fèi)更多空間來存儲并管理。因此，存儲系統(tǒng)中數(shù)據(jù)冗余問題成為信息存儲領(lǐng)域的研究重點(diǎn)。

重復(fù)數(shù)據(jù)刪除技術(shù)是處理這一類問題的常用技術(shù)，也稱為智能壓縮或單一實(shí)例存儲，是一種可自動(dòng)搜索重復(fù)數(shù)據(jù)，將相同的數(shù)據(jù)只保留一個(gè)副本，并使用指向單一副本的指針替換其他重復(fù)副本，以達(dá)到消除冗余數(shù)據(jù)、降低存儲容量需求的存儲技術(shù)。該技術(shù)[3]的執(zhí)行步驟為：利用分塊方法對輸入的大型數(shù)據(jù)進(jìn)行分塊，使用哈希(hash)算法給每一個(gè)塊分配唯一的值作為唯一標(biāo)識，新傳入的塊通過唯一標(biāo)識與已存儲的塊進(jìn)行比對，如果匹配將冗余數(shù)據(jù)刪除，不匹配則存儲新塊。分割技術(shù)作為重復(fù)數(shù)據(jù)刪除技術(shù)中的核心內(nèi)容分為定長分塊和變長分塊兩大類。假設(shè)一個(gè)文件中包含重復(fù)的數(shù)據(jù)塊，或者在某一個(gè)文件中加入或刪去部分內(nèi)容，文件的新版本中會包含大量的重復(fù)數(shù)據(jù)，因此應(yīng)用分塊技術(shù)以更小粒度分割文件能提高去重率。常用的定長分塊因其邊緣敏感，微小變化即會導(dǎo)致“雪崩現(xiàn)象”，并且在一個(gè)分割好的文件塊中的微小變化也會導(dǎo)致宏觀上較大的變化，因此，在較小的粒度上，通過相似性來判斷對數(shù)據(jù)塊的最后處理，以達(dá)到有效的重復(fù)數(shù)據(jù)刪除的目的。

為此,提出了一種基于動(dòng)態(tài)分塊和相似hash(Simhash)的文本文檔(txt，docx，pdf)有效去重方案,通過Simhash[4-5]判斷文件及文件塊的相似性,以獲得更高的重復(fù)數(shù)據(jù)刪除率和準(zhǔn)確率。

1 現(xiàn)有相關(guān)技術(shù)分析

隨著冗余數(shù)據(jù)的增多，刪除重復(fù)數(shù)據(jù)成為了該領(lǐng)域的研究熱點(diǎn)。去重技術(shù)按粒度的大小可分為文件級數(shù)據(jù)去重、塊級數(shù)據(jù)去重和比特級數(shù)據(jù)去重。重復(fù)數(shù)據(jù)刪除技術(shù)[6]目前比較常用的是小粒度的數(shù)據(jù)去重技術(shù)。不同粒度會呈現(xiàn)不同的去重效果，去重效果隨粒度變小而變好，但同時(shí)也導(dǎo)致了維護(hù)復(fù)雜度增高、性能降低等問題。如何平衡二者之間的關(guān)系，取決于企業(yè)的決策，也是企業(yè)控制成本的重要手段。

1.1文件級數(shù)據(jù)去重

文件級數(shù)據(jù)去重技術(shù)又稱WFD技術(shù)，即以文件為粒度查找重復(fù)數(shù)據(jù)的方法。此方法首先對整個(gè)文件進(jìn)行hash計(jì)算，然后將該值與已存儲的hash值進(jìn)行比對，如果檢測到相同的值，則僅將文件用指針替換，不進(jìn)行實(shí)際存儲，否則存儲新文件。目前Deep Store、TAPER、Foundation、Dedupvl[7]等重刪系統(tǒng)使用的是文件級去重技術(shù)。

1.2塊級數(shù)據(jù)去重

基于文件的數(shù)據(jù)去重不能對文件內(nèi)部進(jìn)行去重，因此研究者提出了更細(xì)粒度的去重技術(shù)。

1.2.1 固定大小分塊技術(shù)(FSP)

基于固定尺寸劃分去重的固定尺寸劃分算法是按固定大小將文檔分塊，再計(jì)算每個(gè)塊的hash值(常用MD5，SHA-1)得到一個(gè)指紋值作為這個(gè)塊的唯一標(biāo)識，該指紋與已存的指紋進(jìn)行比對，檢測到相同的指向索引不存儲，否則存儲相應(yīng)數(shù)據(jù)塊。DBLK中Tsuchiya等以4 KB作為一個(gè)粒度將數(shù)據(jù)分塊并對其進(jìn)行比對，獲得了較高的重刪率。目前Venti、Symantec、iDedup[7]等重刪系統(tǒng)采用的是固定尺寸劃分去重技術(shù)。該技術(shù)可以減少一定的存儲空間，節(jié)省一定的網(wǎng)絡(luò)帶寬，但是變化敏感度很高，一個(gè)字符的變化將對影響重刪效率產(chǎn)生極大影響，所以該技術(shù)比較適合更新少的數(shù)據(jù)，如圖片、音頻等文件。

1.2.2 基于內(nèi)容的分塊重刪檢測技術(shù)(CDC)

CDC[8]算法是用Rabin指紋將文件分割成大小長度不一樣的數(shù)據(jù)塊的策略。與固定大小分塊不同的是它對編輯及序列不敏感，變化只會影響兩個(gè)相鄰的數(shù)據(jù)塊，但是分塊完全取決于設(shè)定的期望塊的大小，設(shè)定會直接影響該方法的去重效果。CDC目前使用在REBL、SiLo、ChunkStash等重刪系統(tǒng)以及Pastiche備份系統(tǒng)上。

2 基于SimHash的數(shù)據(jù)去重技術(shù)

在不同的命名、網(wǎng)頁鏡像或相似數(shù)據(jù)等情況下，因其特征或參數(shù)的原因往往無法確定相似的數(shù)據(jù)[9]，雖然這些數(shù)據(jù)看似不同，但事實(shí)上存在很大的相似性。像重復(fù)數(shù)據(jù)刪除一樣，對于相似數(shù)據(jù)只想要存儲數(shù)據(jù)的一個(gè)版本來節(jié)省存儲空間?？墒腔诠Ｖ?hash value)的“數(shù)字指紋”特性，一個(gè)字符的不同將會導(dǎo)致整個(gè)哈希值的不同，因此相似數(shù)據(jù)的判斷不夠準(zhǔn)確[10]。為此，提出了基于Simhash的相似文本數(shù)據(jù)去重技術(shù)。該技術(shù)將中文文本文件(TXT,DOCX,PDF)的句子作為最小單位，自然段作為塊單位來對其進(jìn)行數(shù)據(jù)去重。文中提出的基于Simhash[11]的數(shù)據(jù)去重技術(shù)包含四個(gè)步驟：數(shù)據(jù)分塊、計(jì)算標(biāo)識、進(jìn)行比對、數(shù)據(jù)去重。

2.1數(shù)據(jù)分塊

目前數(shù)據(jù)分塊中常用的方法是FSP(Fixed-Size Partitsion)和CDC[12](Content-Defined Chunk)，雖然達(dá)到了不錯(cuò)的去重效果，可是對于一個(gè)數(shù)據(jù)塊來說少量字符的變化將會導(dǎo)致整個(gè)數(shù)據(jù)塊“標(biāo)識”的不同，從而影響去重效果[13]。

將中文文本中的標(biāo)點(diǎn)符號作為一個(gè)特征，對中文文本進(jìn)行分塊，按句子進(jìn)行劃分，且把一個(gè)自然段作為一個(gè)數(shù)據(jù)塊，其流程如圖1所示。

圖1 數(shù)據(jù)分塊流程

具體步驟如下：

(1)讀入整個(gè)文件；

(2)按字節(jié)讀入文件到臨時(shí)列表(list)中，當(dāng)讀入的字符是標(biāo)點(diǎn)符號，如“。？！”，停止讀入；

(3)將臨時(shí)列表(list)中的數(shù)據(jù)放入列表(List)中，清空list；

(4)返回第二步，繼續(xù)判斷。

最后可得若干List，每個(gè)List里面的元素是中文的句子，而一個(gè)List代表一個(gè)自然段。

2.2改進(jìn)計(jì)算策略

如果繼續(xù)使用Hash來對相似數(shù)據(jù)進(jìn)行處理，難達(dá)到對相似數(shù)據(jù)判斷的準(zhǔn)確性。對于相似數(shù)據(jù)來說，使用Simhash算法以達(dá)到理想去重效果。Simhash是一項(xiàng)數(shù)字指紋技術(shù)，基于一個(gè)文檔的指紋是它的hash特性和相似文件有相似hash值的兩個(gè)屬性，可以在hash算法的基礎(chǔ)上更準(zhǔn)確地判斷相似數(shù)據(jù)。

Simhash像傳統(tǒng)hash一樣，可以作為文件的標(biāo)識，因?yàn)閷τ谕耆嗤奈募梢运愠鐾耆粯拥腟imhash值，而對于類似的文件通過Simhash可以得到類似的Simhash值，通過Simhash值的比對，可以得出兩個(gè)文件的相似度。相對于傳統(tǒng)hash值，Simhash值更適合類似文件的比對。

2.3計(jì)算Simhash值

根據(jù)Charikar提出來的算法思路，將Simhash與上述數(shù)據(jù)分塊技術(shù)相結(jié)合，計(jì)算每個(gè)數(shù)據(jù)塊，即以自然段的Simhash值來計(jì)算整個(gè)文本文檔的唯一標(biāo)識—Simhash值。為了達(dá)到更高的計(jì)算速度，在原本的Simhash算法上做修改，首先不再選擇特征詞并計(jì)算其權(quán)重，而視每一個(gè)中文句子為一個(gè)特征量，然后不再根據(jù)特征詞的出現(xiàn)次數(shù)設(shè)定不同的權(quán)重，而視每個(gè)特征的權(quán)重為1。具體計(jì)算過程如圖2所示。

圖2 Simhash計(jì)算流程

結(jié)合圖2與文中方法，其計(jì)算步驟如下：

(1)確定指紋大??；

(2)創(chuàng)建一個(gè)m維向量，并初始化為0。m位的二進(jìn)制數(shù)S初始化為0；

(3)對List里每個(gè)元素(句子)使用MD5或者SHA-1，產(chǎn)生一個(gè)m位的簽名G。對i=1到m：如果G的第i位為1，則V的第i個(gè)元素加上該權(quán)重(默認(rèn)每個(gè)句子的權(quán)重為1)，否則，V的第i個(gè)元素減去該元素的權(quán)重；

(4)進(jìn)行縱向累加，累加每一個(gè)元素加完權(quán)重以后的值。如果V的第i個(gè)元素大于0，則S的第i位為1，否則為0；

(5)輸出S作為List的簽名；

(6)將計(jì)算出來的S作為這個(gè)數(shù)據(jù)塊(List—自然段)的唯一標(biāo)識，通過比較兩個(gè)文件S的海明距離(Hamming Distance)得出數(shù)據(jù)塊的相似度。

2.4數(shù)據(jù)去重

應(yīng)用上述方法對數(shù)據(jù)進(jìn)行分塊，再用Simhash計(jì)算每個(gè)數(shù)據(jù)塊的唯一標(biāo)識S后進(jìn)行數(shù)據(jù)去重處理。

數(shù)據(jù)進(jìn)行分塊后應(yīng)用Simhash算法進(jìn)行標(biāo)識，之后對得到的S與已存儲的S做比對(做異或運(yùn)算)得到相應(yīng)的Hamming Distance(兩個(gè)二進(jìn)制向量中不相同位的個(gè)數(shù))，比對二者相似程度，并通過預(yù)先設(shè)定的相似度閾值來判斷這個(gè)文件的相似性；當(dāng)?shù)玫降暮Ｃ骶嚯x等于0，則認(rèn)為其完全相同；當(dāng)小于預(yù)先設(shè)定的閾值，則認(rèn)為其相似度較大，需對其進(jìn)行進(jìn)一步的分塊，重新執(zhí)行數(shù)據(jù)去重操作；若大于閾值，則認(rèn)為其不相同，存儲相應(yīng)數(shù)據(jù)，當(dāng)作一個(gè)新的數(shù)據(jù)塊來處理。

基于Simhash算法的重復(fù)數(shù)據(jù)刪除的具體流程如圖3所示。

圖3 基于Simhash的重復(fù)數(shù)據(jù)刪除的具體流程

通過大量實(shí)驗(yàn)發(fā)現(xiàn)，對于一段中文文檔，當(dāng)其相似度為50%時(shí)，它們的海明距離一般會在50～70之間，所以設(shè)定70作為閾值。當(dāng)海明距離小于70時(shí)，表明這段數(shù)據(jù)相似度較高；如果高于70，默認(rèn)為不相同數(shù)據(jù)進(jìn)行處理(所用到的文本權(quán)重默認(rèn)為1，權(quán)重的設(shè)定會影響海明距離的大小)。

3 實(shí)驗(yàn)結(jié)果分析

以中文文本為實(shí)驗(yàn)對象，通過基于Simhash的數(shù)據(jù)去重方案，在可行性、去重率及準(zhǔn)確率方面與傳統(tǒng)去重技術(shù)進(jìn)行比對。第一組實(shí)驗(yàn)通過Simhash與傳統(tǒng)hash作對比證明其可行性；第二組實(shí)驗(yàn)通過新方案與現(xiàn)有的去重技術(shù)在去重率上進(jìn)行對比；第三組實(shí)驗(yàn)進(jìn)行準(zhǔn)確率對比。

首先，為了證明hash與Simhash在數(shù)據(jù)去重上的差別，修改了目標(biāo)文檔的字符串，分別計(jì)算其hash值和Simhash值，比較使用兩種標(biāo)識是否達(dá)到字符串相似率判斷的目的，結(jié)果如圖4所示。

圖4 修改簡單字符串后的hash值與Simhash值的對比

由圖4可知，當(dāng)字符串不發(fā)生任何變化時(shí)，通過hash值和Simhash值都能判斷字符串是否完全相似，可是當(dāng)字符串發(fā)生一個(gè)字節(jié)的變化，hash值判斷的相似率就會變成0%，而使用Simhash判斷的字符串，不會因?yàn)樽址兓谙嗨坡噬习l(fā)生過大的變化，隨著不同字符的增多，相似率會下降且呈直線趨勢，表明通過Simhash判斷文件相似率是一種更有效的策略。

在實(shí)驗(yàn)2中，對不同大小的目標(biāo)文件隨機(jī)插入一些干擾項(xiàng)，進(jìn)而應(yīng)用固定大小分塊(FS)去重算法、CDC去重算法以及基于Simhash的數(shù)據(jù)去重算法比較其優(yōu)劣，結(jié)果如圖5所示。

圖5 隨機(jī)插入干擾項(xiàng)的不同算法去重率對比

準(zhǔn)確率(準(zhǔn)確率=系統(tǒng)檢測出的正確重復(fù)數(shù)據(jù)/系統(tǒng)檢測出的重復(fù)數(shù)據(jù))是數(shù)據(jù)去重上較為重要的因素，準(zhǔn)確率高則表示此去重方法在重復(fù)數(shù)據(jù)刪除上更為有效。因此，在實(shí)驗(yàn)3中，應(yīng)用上述三種技術(shù)，處理不同大小的文檔，其準(zhǔn)確率比對結(jié)果如圖6所示。

圖6 不同算法的準(zhǔn)確率對比

由圖6可知，F(xiàn)S技術(shù)的準(zhǔn)確率隨著文件的增大呈下降趨勢，且準(zhǔn)確率一直偏低；CDC和Simhash去重技術(shù)隨著文件大小的變化準(zhǔn)確率都表現(xiàn)出一定的波動(dòng)，但Simhash算法始終保持相對較高的準(zhǔn)確率，證明了其優(yōu)越性。

4 結(jié)束語

針對存儲系統(tǒng)中的冗余數(shù)據(jù)處理問題，提出了基于Simhash的重復(fù)數(shù)據(jù)刪除技術(shù)，利用中文文本的特殊符號與Simhash結(jié)合達(dá)到了更高的去重率。實(shí)驗(yàn)結(jié)果表明，相較于其他去重技術(shù)，文中的技術(shù)方案在去重率、準(zhǔn)確率等方面均呈現(xiàn)出了一定的優(yōu)越性。

[1] 敖 莉,舒繼武,李明強(qiáng).重復(fù)數(shù)據(jù)刪除技術(shù)[J].軟件學(xué)報(bào),2010,21(5):916-929.

[2] Clements A T,Ahmad I,Vilayannur M,et al.Decentralized deduplication in SAN cluster file systems[C]//USENIX annual technical conference.[s.l.]:USENIX,2009:101-114.

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

[4] Charikar M S.Similarity estimation techniques from rounding algorithms[C]//Proceedings of the thirty-fourth annual ACMsymposium on theory of computing.[s.l.]:ACM,2002:380-388.

[5] Manku G S,Jain A,Sarma A D.Detecting near-duplicates for web crawling[C]//Proceedings of the 16th international conference on world wide web.[s.l.]:ACM,2007:141-150.

[6] Denehy T E,Hsu W W.Duplicate management for reference data[R].[s.l.]:[s.n.],2003.

[7] 謝 平.存儲系統(tǒng)重復(fù)數(shù)據(jù)刪除技術(shù)研究綜述[J].計(jì)算機(jī)科學(xué),2014,41(1):22-30.

[8] Bobbarjung D R,Jagannathan S,Dubnicki C.Improving duplicate elimination in storage systems[J].ACM Transactions on Storage,2006,2(4):424-448.

[9] 郭 穎，陳峰宏，周明輝.大規(guī)模代碼克隆的檢測方法[J].計(jì)算機(jī)科學(xué)與探索，2014,8(4):417-426.

[10] Kulkarni P,Douglis F,Lavoie J,et al.Redundancy elimination within large collections of files[C]//Proceedings of USENIX technical conference.Berkeley,CA,USA:USENIX Association,2004.

[11] 王 格,吳 釗,李 向.基于全文檢索的文本相似度算法應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程,2016,44(4):567-571.

[12] Policroniades C,Pratt I.Alternatives for detecting redundancy in storage systems data[C]//Proceedings of USENIX technical conference.Berkeley,CA,USA:USENIX Association,2004.

[13] Zamora J,Mendoza M,Allende H.Hashing-based clustering in high dimensional data[J].Expert Systems with Applications,2016,62:202-211.

[14] 尹美娟,陳庶民,劉曉楠,等.基于郵件正文的郵箱用戶別名抽取[J].計(jì)算機(jī)科學(xué),2011,38(12):182-186.

ResearchonDeduplicationTechniqueofChineseTextwithSimhash

PENG Shuang-he，Tuergong MAITISABIER，ZHOU Qiao-feng

(School of Computer and Information Technology，Beijing Jiaotong University,Beijing 100044，China)

With the rapid development of computer technology,the amount of data storage in various areas of storage systems has been increased rapidly,of which the redundant data also does.Previous studies shown that some storage system has achieved 60% of redundant data,which displays the higher cost of storage management,so processing of that has become a hot spot for storage system research.For this,a method to duplicate redundant data based on Simhash is proposed,which uses the data blocks as the granularity to deduplicate the data,in which the special characters in Chinese documents,such as “。？！”,are acted as split points for blocking.Simhash can be the only identifications and the similarity of those is judged by Hamming Distance for data duplication.Experimental results show that compared with the traditional hash deduplication technology,it has higher deduplication rate and accuracy,which displays good application value and application prospect.

data deduplication;Simhash;hash;data blocking

2016-11-16

2017-03-07 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-19

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2015JBM034)

彭雙和(1974-)，女，講師，研究方向?yàn)樾畔踩?；圖爾貢·麥提薩比爾(1989-)，男(維吾爾)，碩士研究生，研究方向?yàn)閿?shù)據(jù)去重。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170719.1111.064.html

TP311

A

1673-629X(2017)11-0137-04

10.3969/j.issn.1673-629X.2017.11.030