席曄文，楊金民

湖南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410082

基于雙布魯姆過濾器的數(shù)據(jù)排重技術(shù)

席曄文，楊金民

湖南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410082

1 引言

隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，數(shù)字信息量呈爆炸式的增長(zhǎng)，占用的儲(chǔ)存空間越來越多。有研究指出，一般系統(tǒng)中數(shù)據(jù)有60%是冗余的，這個(gè)數(shù)據(jù)還會(huì)隨著系統(tǒng)運(yùn)行時(shí)間的推移而繼續(xù)增長(zhǎng)。由此，重復(fù)數(shù)據(jù)刪除技術(shù)[1]得到了大量的關(guān)注：它使系統(tǒng)數(shù)據(jù)的存儲(chǔ)空間暴增問題得以緩解，對(duì)系統(tǒng)中已存在的資源進(jìn)行最大化利用；在網(wǎng)絡(luò)數(shù)據(jù)傳輸前將重復(fù)數(shù)據(jù)查找出來，減少對(duì)網(wǎng)絡(luò)帶寬的占用。

如何簡(jiǎn)潔地表示海量的數(shù)據(jù)信息，如何快速地在海量數(shù)據(jù)中快速查找重復(fù)數(shù)據(jù)，是排重技術(shù)應(yīng)用于大規(guī)模數(shù)據(jù)管理的關(guān)鍵。

現(xiàn)在流行的排重技術(shù)有Message Digest Algorithm MD5（MD5碼）[2]排重法，MD5碼是對(duì)任意長(zhǎng)度的明文輸入，通過函數(shù)計(jì)算，得出的只屬于該輸入的獨(dú)一無二的指紋值，所以可以通過比對(duì)MD5碼來驗(yàn)證2個(gè)文件是否相同。它的具體算法流程如下：將系統(tǒng)中所有文件計(jì)算MD5碼存儲(chǔ)到集合中并建立索引，稱為集合S。當(dāng)更新文件時(shí)，計(jì)算傳入文件MD5碼并在集合S中查找，若發(fā)現(xiàn)集合中存在相同的MD5碼，說明該傳入文件是重復(fù)文件，刪除該文件，就達(dá)到了數(shù)據(jù)排重的目的。在效率方面，其查找過程就是將傳入文件MD5碼與全集S的MD5碼元素按集合索引一條條比對(duì)，時(shí)間復(fù)雜度為O(n)，若傳入文件全為新文件，則每次查找都要將集合從頭查到尾，所以該算法的查找時(shí)間并不盡人意，沒有對(duì)MD5碼進(jìn)行任何處理直接進(jìn)行查找，對(duì)其利用率還處于原始階段。而通過使用布魯姆過濾器技術(shù)來處理MD5碼可以幫助減少查找重復(fù)數(shù)據(jù)的耗時(shí)。

2 相關(guān)技術(shù)

標(biāo)準(zhǔn)布魯姆過濾器（Bloom Filter）[3-5]是一種高效、快速、精簡(jiǎn)的信息表示查找技術(shù)，其應(yīng)用相當(dāng)廣泛，如P2P節(jié)點(diǎn)協(xié)作交互[6-7]和文件操作[8]等。Bloom Filter原理是將數(shù)據(jù)集合里的所有元素通過多個(gè)相互獨(dú)立的哈希函數(shù)映射到位串向量上，Bloom Filter所需存儲(chǔ)空間與元素自身大小和集合規(guī)模無關(guān)，使用一個(gè)共有m位的V向量來表示n個(gè)元素的集合，則每個(gè)元素平均只需要m n比特位，所以使用Bloom Filter表示數(shù)據(jù)可以極大地節(jié)約存儲(chǔ)空間。

布魯姆過濾器的具體原理如圖1：數(shù)據(jù)集合s= {x1，x2，…，xn}共n個(gè)元素分別代入到k個(gè)相互獨(dú)立的哈希函數(shù)，計(jì)算地址并映射到長(zhǎng)度為m位的位串向量V向量中，所以一個(gè)布魯姆過濾器由k個(gè)相互獨(dú)立的哈希函數(shù) {h1，h2，…，hk-1，hk}（它們值域?yàn)?{0，1，…，m}）和一個(gè)位串向量（它的向量初始值全為0）組成。

圖1 布魯姆過濾器結(jié)構(gòu)示意圖

對(duì)向量進(jìn)行插入元素操作時(shí)，當(dāng)一個(gè)向量地址多次被置為1，只有第一次會(huì)起作用，后面幾次將沒有任何效果。在圖2中，X1和 X2都映射到了同1個(gè)向量地址（從左邊數(shù)第五位）。這也是Bloom Filter出現(xiàn)假陽性誤判[9]（false positive）的原因。

圖2 插入元素

查詢 y是否屬于數(shù)據(jù)集合，將 y代入k個(gè)哈希函數(shù)，如果所有hi(y)的位置不全為1(1≤i≤k)，那么就判定y不是集合中的元素，否則說明 y可能是集合中的元素。每查詢一個(gè)元素只需比對(duì)向量相應(yīng)地址是否為1，這就是使用Bloom Filter排重遠(yuǎn)快于MD5碼排重的原因。圖3中 y1不是集合中的元素，y2或者屬于這個(gè)集合；或者剛好是一個(gè)假陽性誤判（把不屬于這個(gè)集合的元素誤判屬于這個(gè)集合），這是因?yàn)椴樵冊(cè)氐牡刂房赡苁怯善渌刂?的。

圖3 查詢?cè)?/p>

因?yàn)榧訇栃缘拇嬖?，Bloom Filter不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，Bloom Filter通過極少的錯(cuò)誤換取了存儲(chǔ)空間節(jié)省與耗時(shí)的極大縮短。因此，布魯姆過濾器是允許存在一定誤判的前提下，在查詢準(zhǔn)確率與存儲(chǔ)代價(jià)、算法耗時(shí)之間的折中。

3 雙布魯姆過濾器排重算法

3.1 算法設(shè)計(jì)思想

由于MD5碼排重算法對(duì)MD5碼沒有進(jìn)行任何處理，直接使用MD5碼進(jìn)行重復(fù)查詢，導(dǎo)致算法查找耗時(shí)過長(zhǎng)的缺點(diǎn)。使用布魯姆過濾器技術(shù)將文件MD5碼映射到一個(gè)位串向量上，查找時(shí)只需進(jìn)行位與操作即可判斷查詢?cè)厥欠褚汛嬖?，這極大地減少了查詢?cè)氐暮臅r(shí)。

但是使用布魯姆過濾器，若只按文件為單位計(jì)算MD5碼值排重，很可能一個(gè)大文件中已經(jīng)包含了另一個(gè)小文件中的全部?jī)?nèi)容，但由于這兩個(gè)文件大小都不相同，它們的MD5碼也是不同的，小文件作為重復(fù)數(shù)據(jù)得不到排重，這說明文件級(jí)單布魯姆過濾器排重粒度太大，無法滿足高精度的數(shù)據(jù)排重要求。

如果將文件分割成等大小的數(shù)據(jù)塊，對(duì)所有數(shù)據(jù)塊的MD5碼集合以布魯姆過濾器向量形式表示進(jìn)行排重。這種數(shù)據(jù)塊級(jí)單布魯姆過濾器排重雖然進(jìn)入文件內(nèi)部進(jìn)行數(shù)據(jù)排重，但文件的大量分塊，大大增加了重復(fù)元素查找的工作量，耗時(shí)也數(shù)倍增長(zhǎng)。

在保證高精度排重的前提下，提高排重速度，減少算法耗時(shí)，就是新算法設(shè)計(jì)的中心思想。數(shù)據(jù)塊級(jí)單布魯姆過濾器排重算法固然完成了高精度的排重，但在算法的排重過程中，有很多完全相同的文件被分割成了大量的數(shù)據(jù)塊后再一一排重，若在數(shù)據(jù)級(jí)排重前先進(jìn)行一次文件級(jí)MD5碼排重，將所有相同文件先排重掉，就可以為數(shù)據(jù)塊級(jí)排重減少相當(dāng)大的工作量，從而提高算法效率。

3.2 算法設(shè)計(jì)

新算法使用雙布魯姆過濾器對(duì)文件進(jìn)行2級(jí)排重。第一級(jí)采用文件級(jí)的重復(fù)數(shù)據(jù)刪除策略，計(jì)算文件MD5碼值，在預(yù)先映射好的文件級(jí)布魯姆過濾器向量上查詢，發(fā)現(xiàn)重復(fù)值則刪除文件；第二級(jí)采用數(shù)據(jù)塊級(jí)的重復(fù)數(shù)據(jù)刪除策略[10-11]，通過預(yù)先設(shè)定好的數(shù)據(jù)塊大小將第一級(jí)排重過濾后的文件分塊，計(jì)算數(shù)據(jù)塊MD5碼，通過映射到數(shù)據(jù)塊級(jí)布魯姆過濾器向量上比對(duì)，對(duì)數(shù)據(jù)塊排重。

該算法不同于數(shù)據(jù)塊級(jí)單布魯姆過濾器一開始就對(duì)文件進(jìn)行分割掃描，而是先進(jìn)行以文件為單位的重復(fù)數(shù)據(jù)查找，通過第一次排重對(duì)文件集合進(jìn)行過濾，減少第2級(jí)過濾器需要排重的文件數(shù)，再進(jìn)行數(shù)據(jù)塊級(jí)掃描排重，以提高數(shù)據(jù)排重的細(xì)粒度。在重復(fù)文件率高的場(chǎng)合，可以既達(dá)到數(shù)據(jù)級(jí)排重的效果，又有趨近于文件級(jí)排重的速度。

新算法的具體流程如下：

（1）將原有文件按文件級(jí)和數(shù)據(jù)塊級(jí)分別計(jì)算MD5碼值，并映射為相應(yīng)的布魯姆過濾器向量BF1，BF2。

（2）計(jì)算新傳入文件的MD5碼，在第一級(jí)布魯姆過濾器中查詢?cè)揗D5碼值。

（3）若有該MD5碼，說明該文件為重復(fù)文件，刪除文件，結(jié)束算法。

（4）若無該MD5碼，將該MD5映射到第一級(jí)布魯姆過濾器向量中。

（5）將該文件按設(shè)定的數(shù)據(jù)塊大小分割，并計(jì)算數(shù)據(jù)塊的MD5碼值。

（6）在第二級(jí)布魯姆過濾器中查詢數(shù)據(jù)塊MD5碼值。

（7）若有該MD5碼，說明該數(shù)據(jù)塊為重復(fù)，刪除數(shù)據(jù)塊，結(jié)束算法。

（8）若無該MD5碼，說明是新數(shù)據(jù)塊，存儲(chǔ)，將該MD5更新到第二級(jí)布魯姆過濾器向量中。

圖4 算法流程圖

3.3 算法誤判率分析

（1）假陰性誤判率 f-：該算法基于標(biāo)準(zhǔn)布魯姆過濾器實(shí)現(xiàn)，將數(shù)據(jù)MD5碼映射到對(duì)應(yīng)的BF向量上，向量對(duì)應(yīng)位不全為1則判定該數(shù)據(jù)不屬于集合，數(shù)據(jù)屬于集合則向量對(duì)應(yīng)位全為1，所以算法出現(xiàn)假陰性誤判率（將屬于集合的數(shù)據(jù)判斷為不屬于集合）為0%，這說明算法不會(huì)將重復(fù)文件判斷為新文件，對(duì)信息進(jìn)行重復(fù)儲(chǔ)存。

（2）假陽性誤判率 f+：設(shè)第一級(jí)布魯姆過濾器BF1假陽性誤判率為 f1，第二級(jí)布魯姆過濾器BF2假陽性誤判率為 f2，2級(jí)布魯姆過濾器采用的都是參數(shù)相同的標(biāo)準(zhǔn)布魯姆過濾器，它的假陽性誤判率為 fbf，所以2層布魯姆過濾器單獨(dú)的假陽性誤判率都為：

（3）設(shè)有查詢文件集合S，它與原始文件的重復(fù)率為r，在第二級(jí)排重中，BF2的文件集合S′是第一次排重中減去重復(fù)文件和第一級(jí)假陽性誤判文件剩下判為不重復(fù)的文件，這其中沒有誤判文件（布魯姆過濾器不存在假陰性誤判）：

設(shè)該算法誤判率為 f，為假陰性誤判文件加上假陽性誤判文件與全集合文件的大小之比。假陰性誤判率為0，則

從式（4）可知該算法誤判率只與選擇的布魯姆過濾器假陽性誤判率和查詢文件集合的重復(fù)文件率有關(guān)。在選定布魯姆過濾器參數(shù)后，理論上該算法對(duì)數(shù)據(jù)冗余越多的系統(tǒng)排重誤判率越低。

3.4 算法時(shí)間空間復(fù)雜度分析

3.4.1 算法時(shí)間復(fù)雜度

在初次運(yùn)行該算法時(shí)，需要把原系統(tǒng)中所有文件分別映射為文件級(jí)和數(shù)據(jù)塊級(jí)布魯姆過濾器向量，設(shè)T1為將原計(jì)算機(jī)里的文件映射到第一級(jí)布魯姆過濾器向量BF1的時(shí)間；T2為將原計(jì)算機(jī)里的文件按分割塊大小映射到第二級(jí)布魯姆過濾器向量BF2的時(shí)間，使用標(biāo)準(zhǔn)布魯姆過濾器插入一個(gè)元素，需要進(jìn)行k次哈希運(yùn)算，所以一個(gè)元素插入操作的時(shí)間復(fù)雜度為O(k)。這2個(gè)耗時(shí)只在初次運(yùn)行時(shí)出現(xiàn)，不計(jì)入一般排重時(shí)間開銷，設(shè)本算法的耗時(shí)為T：

（1）Tmd5為算法對(duì)查詢集合文件和第一次過濾后不重復(fù)文件分割的數(shù)據(jù)塊計(jì)算MD5碼的時(shí)間。

（2）T3為文件MD5碼代入 BF1中查詢的時(shí)間，T4為數(shù)據(jù)塊MD5碼代入BF2中查詢的時(shí)間。當(dāng)查詢?cè)厥欠裨诩现袝r(shí)，只需進(jìn)行k次哈希計(jì)算。這也是使用布魯姆過濾器查詢優(yōu)于MD5碼直接索引查詢的地方，它使得快速匹配成為可能，因?yàn)椴剪斈愤^濾器的查詢操作是在位向量上進(jìn)行，按位與操作。

（3）S的文件個(gè)數(shù)不會(huì)改變，而S和S′之間的關(guān)系由式（2）可知，當(dāng)新算法在面對(duì)重復(fù)率相當(dāng)大的數(shù)據(jù)集的時(shí)候，留給BF2排重的文件數(shù)也大幅減少，所以在實(shí)際應(yīng)用中設(shè)定好布魯姆過濾器誤判率 fbf后，算法耗時(shí)將隨著查詢集合的重復(fù)率的增大而減少。

3.4.2 算法空間復(fù)雜度

作為一種精簡(jiǎn)的信息表示方案，對(duì)于n個(gè)元素的集合，只需要m位向量V，其空間復(fù)雜度為O(m)。同時(shí)在分布式系統(tǒng)的文件排重中，排重算法將BF1和BF2傳送到待傳輸機(jī)器上，比傳輸占用空間更大的MD5值集合，也可以幫助節(jié)省網(wǎng)絡(luò)帶寬。

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

在實(shí)際測(cè)試中，使用的操作系統(tǒng)為Windows XP，機(jī)器的配置如表1。

表1 實(shí)驗(yàn)配置

實(shí)驗(yàn)具體為：在一個(gè)目錄中存放有8 000個(gè)待傳輸文件的集合B，將集合B傳輸?shù)搅硪粋€(gè)目錄A下。改變集合B中的文件使之與目錄A中的文件有不同的重復(fù)文件率r，文件分割塊設(shè)定為0.5 MB。分別使用MD5排重、文件級(jí)單布魯姆過濾器排重、數(shù)據(jù)塊級(jí)單布魯姆過濾器排重、雙層布魯姆過濾器排重新算法將集合B傳輸?shù)侥夸汚下。圖5～圖7、表2從各方面比較了4種不同算法的性能：（1）數(shù)據(jù)集重復(fù)文件率與數(shù)據(jù)排重率關(guān)系（r-p見圖5）。（2）數(shù)據(jù)集重復(fù)文件率與算法耗時(shí)關(guān)系（r-t見圖6）。（3）數(shù)據(jù)集重復(fù)文件率與實(shí)驗(yàn)重復(fù)文件誤判率關(guān)系（r-f見圖7）。（4）4種排重算法的理論誤判率與實(shí)際誤判率（見表2）。

圖5 集合重復(fù)文件率與數(shù)據(jù)排重率的關(guān)系

（1）圖5發(fā)現(xiàn)，對(duì)同一數(shù)據(jù)集，采用相同參數(shù)的布魯姆過濾器，雙層排重新算法在4種排重算法里的排重效果是最好的，對(duì)4個(gè)數(shù)據(jù)集的排重率分別達(dá)到61.62%、66.07%、70.12%、72.83%，其他3種算法里只有數(shù)據(jù)級(jí)單布魯姆過濾器排重率與之接近。

圖6 集合重復(fù)文件率與算法耗時(shí)關(guān)系

圖7 集合重復(fù)文件率與算法誤判率關(guān)系

（2）圖6得出，同排重率相近的數(shù)據(jù)塊級(jí)單布魯姆過濾器相比，雙布魯姆過濾器排重算法最少減少了43%耗時(shí)，其他3種算法耗時(shí)與文件重復(fù)率參數(shù)無關(guān)，算法時(shí)間基本保持不變，而雙布魯姆過濾器排重算法隨著r的提高耗時(shí)繼續(xù)保持下降，當(dāng)重復(fù)率達(dá)到60%時(shí)，新算法比數(shù)據(jù)塊單布魯姆過濾器減少了68%耗時(shí)，這是因?yàn)樾滤惴ㄔ?級(jí)排重中已經(jīng)將重復(fù)文件進(jìn)行了排重，減少了2級(jí)排重的工作量，所以新算法對(duì)于重復(fù)率高的數(shù)據(jù)集有著良好的耗時(shí)表現(xiàn)，隨著重復(fù)率的提升，耗時(shí)逐漸向文件級(jí)單布魯姆過濾器排重算法靠近。

（3）圖7得出，實(shí)驗(yàn)中MD5碼排重算法保持0誤判率；布魯姆排重算法使用的標(biāo)準(zhǔn)布魯姆過濾器的參數(shù)取值分別為n=8 000；m=131 072；k=4，2種單層布魯姆過濾器排重算法誤判率基本保持不變，稍有上下浮動(dòng)，說明重復(fù)文件比例對(duì)單層布魯姆過濾器排重算法誤判率沒有影響；而雙層布魯姆過濾器排重算法同理論分析的一樣，隨著實(shí)驗(yàn)數(shù)據(jù)集重復(fù)文件比例的增加，誤判率呈減少趨勢(shì)，向單層布魯姆過濾器排重算法誤判率靠攏。

表2 4種算法排重誤判率

（4）表2得出，當(dāng)布魯姆排重算法使用的標(biāo)準(zhǔn)布魯姆過濾器的參數(shù)取值分別為n=8 000；m=131 072；k=8時(shí)，使用雙布魯姆過濾器排重算法，平均每10 000個(gè)文件出現(xiàn)7個(gè)誤刪除，相比單層布魯姆過濾器平均每10 000個(gè)文件出現(xiàn)5個(gè)誤刪除差別不大，對(duì)于絕大多數(shù)排重系統(tǒng)，該算法是穩(wěn)定可靠的。并且隨著排重系統(tǒng)中冗余數(shù)據(jù)的增多，新算法不管是耗時(shí)還是誤判率都會(huì)有更好的表現(xiàn)。

5 結(jié)束語

雙布魯姆過濾器排重算法的文件級(jí)和數(shù)據(jù)塊級(jí)的雙重排重結(jié)構(gòu)是算法的優(yōu)勢(shì)所在。通過文件級(jí)排重減少了第2級(jí)排重的工作量，減少了算法耗時(shí)，通過數(shù)據(jù)塊級(jí)的排重獲得了數(shù)據(jù)塊級(jí)的排重細(xì)粒度。實(shí)驗(yàn)表明，雙布魯姆過濾器排重算法在保持低假陽性誤判率的前提下，對(duì)4個(gè)數(shù)據(jù)集的排重率分別達(dá)到61.62%、66.07%、70.12%、72.83%，雖然數(shù)據(jù)塊級(jí)單布魯姆過濾器排重率與新算法接近，但是耗時(shí)上新算法比之提高了43%、55%、62%、68%。隨著數(shù)據(jù)集重復(fù)率的繼續(xù)增加，新算法將呈現(xiàn)出越來越好的排重判斷率，所需的時(shí)間也將隨之減少。

本算法還有可進(jìn)一步提高的空間，如采用改進(jìn)型布魯姆過濾器[12-13]滿足集合動(dòng)態(tài)增長(zhǎng)問題，使用CDC檢測(cè)技術(shù)[14]、滑動(dòng)塊分割技術(shù)[15]根據(jù)文件自身內(nèi)容的特征和變化對(duì)文件進(jìn)行分割。

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

[2]廖海生，趙躍龍.基于MD5算法的重復(fù)數(shù)據(jù)刪除技術(shù)的研究與改進(jìn)[J].計(jì)算機(jī)測(cè)量與控制，2010，18（3）：635-638.

[3]謝鯤，文吉?jiǎng)?，張大方，?布魯姆過濾器查詢算法[J].軟件學(xué)報(bào)，2009，20（1）：96-108.

[4]謝鯤，張大方，文吉?jiǎng)偅?布魯姆過濾器布爾代數(shù)探討[J].電子學(xué)報(bào)，2008，36（5）：869-874.

[5]謝鯤，閔應(yīng)驊，張大方.分檔布魯姆過濾器的查詢算法[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（4）：597-607.

[6]Jonathan L，Jacob M T，Laura S，et al.Self-organization in peer-to-peer systems[C]//Proc of the 10th Workshop onACM SIGOPS European Workshop.Saint-Emilion：ACM，2002：125-132.

[7]謝鯤，張大方，謝高崗，等.基于軌跡標(biāo)簽的無結(jié)構(gòu)P2P副本一致性維護(hù)算法[J].軟件學(xué)報(bào)，2007，18（1）：105-116.

[8]Gremillion L L.Designing a bloom filter for differential file access[J].Communications of the ACM，1982，25（9）：600-604.

[9]Mitzenmacher M.Compressed bloom filters[J].ACM Trans on Networking，2002，10（5）：604-612.

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

[11]馬建庭，楊頻.基于重復(fù)數(shù)據(jù)刪除的多用戶文件備份系統(tǒng)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（11）：3586-3589.

[12]AlmeidaP S，BaqueroC，Pregui?aN，et al.Scalable bloom filters[J].Information Processing Letters，2007，101：255-261.

[13]肖明忠，代亞非，李曉明.拆分型Bloom filter[J].電子學(xué)報(bào)，2004，32（2）：241-245.

[14]Bobbarjung D R，Jagannathan S，Dubnicki C.Improving duplicate elimination in storage systems[J].ACM Trans on Storage，2006，2（4）：424-448.

[15]Jain N，Dahlin M，Tewari R.Taper：tiered approach for eliminating redundancy in replicasynchronization[C]// Procofthe4th Usenix Confon Fileand Storage Technologies（FAST 2005）.Berkeley：USENIX Association，2005：281-294.

XI Yewen,YANG Jinmin

School of Information Science and Technology,Hunan University,Changsha 410082,China

Aiming at the disadvantage of file level single bloom filter duplicate data delete algorithm deletes duplicate data only at file size,block level single bloom filter duplicate data delete algorithm’s time-consuming is too much.In this paper, it uses 2 bloom filter,creates a 2 level duplicate data delete algorithm structure-file level and block level.The experimental results show that,double bloom filter duplicate data delete algorithm could delete duplicate data at block level,keep false positive error rate at a low level,time-consuming gets 43%～68%shorter compared with block level single bloom filter duplicate data delete algorithm.

duplicate data delete;query elements;bloom filter;MD5;false positive error rate

針對(duì)文件級(jí)單布魯姆過濾器排重算法只能以文件為單位進(jìn)行數(shù)據(jù)排重，數(shù)據(jù)塊級(jí)單布魯姆過濾器排重算法耗時(shí)過多的缺點(diǎn)，采用2個(gè)布魯姆過濾器，創(chuàng)建文件級(jí)和數(shù)據(jù)塊級(jí)2級(jí)數(shù)據(jù)排重的算法結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，雙布魯姆過濾器排重算法可以以數(shù)據(jù)塊為單位對(duì)數(shù)據(jù)排重，在保持低假陽性誤判率的同時(shí)，相比數(shù)據(jù)塊級(jí)單布魯姆過濾器排重算法耗時(shí)縮短了43%～68%。

重復(fù)數(shù)據(jù)刪除；集合元素查詢；布魯姆過濾器；MD5；假陽性誤判率

A

TP311.13

10.3778/j.issn.1002-8331.1301-0141

XI Yewen,YANG Jinmin.Duplicate data delete technology based on double bloom filter.Computer Engineering and Applications,2014,50（23）：198-202.

國(guó)家自然科學(xué)基金（No.61272401，No.61173167）；“973”子項(xiàng)目（No.2012CB315801）。

席曄文（1987—），男，碩士研究生，研究方向?yàn)閿?shù)據(jù)處理；楊金民（1967—），男，博士，教授，研究領(lǐng)域?yàn)楣收匣謴?fù)與系統(tǒng)容錯(cuò)、系統(tǒng)可靠性、軟件工程。E-mail：402595164@qq.com

2013-01-14

2013-03-22

1002-8331（2014）23-0198-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1646.008.html