Winnowing指紋串匹配的重復數據刪除算法

王青松，葛 慧

(遼寧大學 信息學院，沈陽 110036)

0 引言

目前數據激增問題使數據中心處理的數據量呈現爆炸式增長，數據存儲、備份和恢復所需的時間和容量也隨之增大，給存儲系統帶來了沉重的負擔。由于數據來源不同，許多數據被反復存儲，造成了大量的數據冗余，尤其在備份系統中更加突出[1]。重復數據刪除技術[2-3]的出現引起了研究者的關注，它不僅能夠減少存儲和處理的數據量，節約數據的管理和存儲成本，同時提高了網絡通信的速度，成為降低數據中心冗余數據量的有效手段。

為了在存儲系統中充分利用重復數據刪除技術，減少數據的最終積累量，縮短消除冗余數據的時間，許多經典的重復數據刪除算法被提出。EB(Extreme Binning)算法[4]利用文件相似性，使用最小塊簽名作為文件的特征，只在內存中保存文件的代表塊ID，有效減小了內存占用。然而，最小塊ID作為主索引，一方面重刪率相對較低，另一方面數據分塊算法影響最小塊簽名，不同的分塊算法所產生的最小塊可能不同，從而影響重刪的準確性。Bloom filter算法[5]利用K個Hash函數將數據塊MD5值映射到m位的向量V中，減少頻繁的I/O操作，但存在假正例(False Positives)誤識別率，并且無法從Bloom Filter集合中刪除元素，在需要數據修改的場景下不能使用。張滬寅等[6]提出了用戶感知的重復數據刪除算法，根據用戶相關度，以用戶為單位，減少了數據空間局部性，但對于非人為產生的數據，其相似性計算準確度較低。

以上算法在數據分塊時均采用了可變長度分塊(Content-Defined Chunking, CDC)算法，相對于以文件為粒度，數據塊級粒度能夠檢測到文件內部的重復數據，因此，目前大多數重復數據刪除算法均采用數據塊為粒度。然而，在現有的許多塊級重復數據刪除算法中，存在著數據分塊效果較差[7]的問題。數據的分塊大小很難控制，并且需要預先設置大量的參數，指紋計算和對比的開銷較大，分塊邊界條件也難以滿足，而這些問題往往會影響重刪操作的性能和準確性。因此，目前大多數數據分塊算法都不能使重復數據刪除算法達到理想的效果。

本文針對分塊算法中以上幾點不足，提出了一種Winnowing指紋串匹配的重復數據刪除算法(Deduplication algorithm based on Winnowing Fingerprint Matching, DWFM)，對基于內容的可變長度分塊(CDC)算法進行了改進。實驗結果表明，本文算法能夠對數據流進行合理分塊，指紋計算和對比開銷較小，克服了現有許多分塊算法中的不足。

1 可變長度分塊算法

數據分塊[8]是重復數據刪除算法的前提，其性能的優劣直接影響將來重復數據刪除算法的好壞。數據分塊通常有兩種類型：固定長度分塊(Fixed-Sized Partitioning, FSP)[9]和可變長度分塊(CDC)[10]。FSP將數據分成長度固定的數據塊，以同樣大小的數據塊為單位進行重刪，FSP算法對數據修改很敏感，在數據經常變化時效果較差；而CDC根據Rabin指紋算法[11]通過一個特殊大小的滑動窗口依次分割數據，其分塊大小隨著數據內容的變化而變化，并且修改只會影響到修改數據周圍的少量數據，適用于數據經常修改的情況[10]。

CDC算法使用一個特定寬度w的滑動窗口，從數據的開始處以字節長度滑動，當w大小的數據被裝載完畢后，計算其指紋(Hash)。算法預先給定兩個參數D和r,且r

然而，應用場景不同，待檢測的源數據有很大的區別[12]：可能是文本數據或圖像數據，也可能是結構化數據或非結構化數據，還可能是壓縮數據或無壓縮數據等；并且源數據中重復部分的數量和分布也有很大差別，不重復內容、少量重復的內容和大量重復的內容共存，使分塊大小難以選擇；而且目前的大多數分塊算法對所有場景均使用相同的分塊策略，使其在面對大規模復雜類型數據時性能往往不理想，通常表現出以下幾點不足：

1)滑動窗口w的大小難以選擇。w的大小直接影響分塊的大小，由于重復數據刪除的數量和所需的時間與塊大小呈負相關，在實際的應用環境中，使用較小分塊大小來提高重刪率是不可行的。

2)需要預先人工設定參數D和r,選取不當將導致分塊效果較差。

3)指紋計算和對比開銷較大。CDC算法使用Rabin算法進行數據分塊時，滑動窗口每滑動一字節，需要復雜多項式取模一次來計算指紋，邊界條件取模一次來確定塊邊界，并且產生大量的無用指紋，嚴重影響了重復數據刪除的性能。

4)分塊邊界條件難以滿足。fmodD=r的分塊邊界條件會因為參數設定和待檢測數據的特征而出現很難滿足條件的情況，直接造成分塊過大而使用硬分塊，嚴重時甚至退化為FSP，或者出現大量細碎分塊，加大元數據和索引的開銷。

2 算法設計

本文算法針對CDC算法的以上不足，首先利用分塊大小預測模型，得出最佳分塊大小；然后設計了編碼指紋代替Rabin指紋；最后，在確定分塊邊界條件時，提出了指紋字符串匹配的分塊算法來代替CDC算法中利用參數邊界條件的方式，并使用Winnowing算法計算文件整體指紋時的方法快速選擇指紋對比模式串。算法不僅解決了分塊大小難以控制的問題，同時不用設置參數，計算開銷較小，本文算法的結構如圖1所示。

圖1 本文算法整體框架 Fig. 1 Framework of the proposed algorithm

2.1 分塊大小預測模型

本文針對CDC算法分塊大小的局限性，引入了預測模型。許多研究發現，現有的眾多分塊技術在選擇平均分塊大小時都是基于幾何分布[13]的。王龍翔等[14]論證了內容分塊算法中預期分塊長度對重復數據刪除率的影響。Hirsch等[15]提出了一種以自然方式控制塊大小分布的方法。實驗結果證明，該算法的均值和標準偏差非常接近于常數變化，對于變量概率，標準偏差要小得多，大多數值均接近平均值。應用于不同截止條件的分布圖呈刺猬形，并且帶有一個基本的高斯鐘形曲線。因此算法能夠較準確地預測平均分塊大小，本文算法使用該分塊模型預測預期分塊大小，過程如下。

1)設L表示給定塊的長度，是一個隨機變量，它的期望值即為預期分塊大小。得到塊大小L(L≥M)的概率是第一次M實驗失敗的概率，l表示指數范圍內當前塊大小M的上界，M滿足以下關系：

(1)

2)當L≥M時的概率可以用以下公式求出：

(2)

3)從中可以得到當L=M時的概率：

Pr(L=M)=Pr(L≥M)-Pr(L≥M-1)

(3)

4)則使用以下公式來計算給定條件時的預期塊大小w:

(4)

通過該分塊預測模型獲得的預期大小w,避免了參數設置的人為干涉，一定程度上解決了CDC算法中分塊大小難以控制的問題。

2.2 Winnowing指紋算法

針對CDC算法使用Rabin算法計算數據塊指紋時的計算開銷較大等問題，引入了Winnowing算法[16]。該算法在2003年由Schleimer等提出，經常用于檢測文件或網頁中的相同內容，來判斷抄襲[17]等行為。本文使用Winnowing算法來計算指紋是因為該算法以數字ASCII/文字Unicode編碼作為指紋，計算開銷非常小，并且指紋的構成簡單，便于以后的指紋對比操作。DWFM中在映射指紋時，使用w單位大小對待檢測數據進行分組，其中w是由2.1節中分塊預測模型計算所得到的預期分塊大小，使用Winnowing算法計算數據塊指紋的過程如下。

1)設待檢測數據流D(D中含有n個字符)，使用預測大小w對D中所有長度為w的塊進行指紋映射，如塊C1(C1包含字符1至w)可映射為Hash(C1)，同樣地，C2(C2包含字符2至w+1)可映射為Hash(C2)，則共產生了n-w+1個指紋，Hash(C1),Hash(C2),…,Hash(Cn-w+1)。其中指紋Hash(Ci)(i=1,2,…,n-w+1)與塊Ci{i,i+1,…,s+w-1}相對應。

2)將n-w+1個子塊用以a為基數的整數表示，映射為以a為參數的整數x(0≤x≤bk)，設Code(C1)是數據塊C1的ASCII/Unicode編碼值，即為C1的指紋值Hash(C1)，則數據塊C1的指紋值Hash(C1)可用以下公式計算：

Hash(C1)=Code(C[1])aw-1+Code(C[2])aw-2+…+Code(C[w])=Hash(C[1])+Hash(C[2])+…+Hash(C[w])

(5)

3)C2的指紋值Hash(C2)可以通過以下公式由C1的指紋值直接求得：

Hash(C2)=(Hash(C1)-C[1]aw-1)a+

Code(C[w+1])

(6)

4)將n-w+1個指紋Hash(C1),Hash(C2),…,Hash(Cn-w+1)組成指紋序列Hc,通過公式可發現，后一個塊的Hash值與前一塊的Hash值的相似性較大。這是由于后一塊的指紋值是由前一塊向后滑動一個字節得到的，且僅需要在前一塊Hash值的基礎上通過兩次加法和兩次乘法得到。相比Rabin算法通過兩個復雜多項式取模運算來得到Hash指紋，Winnowing算法使用ASCII/Unicode作為指紋較好地降低了計算開銷。

2.3 模式串Pw的設計

本文算法設計了底層指紋字符串匹配的分塊算法確定塊邊界，代替了CDC算法中利用Rabin參數取模來進行分塊的方式，因此需要設置模式串Pw。由于Winnowing算法確定全文件指紋的過程是基于文件內容的，并且是從指紋組合中選擇指紋信息，其選擇結果體現了數據的本身特性，有利于將來的分塊與檢測。因此將此過程引入到模式串選取的過程中，設計了模式串Pw的選取規則，使Pw的選擇更加符合重復數據刪除算法的要求。在選擇Pw過程中對Hc進行分組時，使用預期分塊大小w為分組大小基數，使Pw的選擇遵從最佳分塊場景，具體的選取規則如圖2所示。

圖2 模式串Pw的選取過程 Fig. 2 Selection of pattern string Pw

1)對于待檢測數據流D{1,2,…,n}的Hash值序列Hc,以w大小的滑動窗口長度沿著Hc滑動，得到指紋分組h1,h2,…,hi；

2)對于每一個指紋組hm(m=1,2,…,i,i為指紋組個數)，取其組內最小的哈希值作為該組的代表，若連續的多個塊具有相同的最小值，則選擇最右側的一組；

3)將最小值組成長度為w的序列，作為下一步分塊時的模式串Pw,算法描述如下。

算法1 模式串選取算法(Pattern String Selection Algorithm, PSSA)。

輸入 待檢測數據流D;

輸出 模式串Pw。

1)

BEGIN

2)

將D使用預測分塊大小w進行分塊

3)

FOR eachCido

//對于每一個字塊Ci

4)

Hash(Ci)=getCode(Ci);

//對每個長度為w的塊取其編碼值作為Hash值

5)

Hc=add(Hash(Ci));

//生成指紋字符串序列Hc

6)

將Hc使用w大小進行分組;

7)

FOR eachHashwdo

//對每個指紋分組Hashw

8)

hmin(i)=getMinhi();

//找出每組指紋Hashw中的最小值hmin(i)

9)

Pw=add(hmin(i));

//將所有最小值指紋組合形成長度為w模式串

10)

END

2.4 Winnowing指紋串匹配分塊算法

CDC算法進行數據分塊時，基本原理和最大的弊端都是需要預先設定參數D和r,當指紋值f與D進行模運算后結果等于r時才建立分塊。然而，一方面參數選擇依據和準確性很難確定；另一方面邊界條件在實際應用中常常會因為參數選擇不當等問題出現長時間不能滿足的情況，只能在最大可容忍范圍Cmax處進行硬分塊，甚至退化成FSP算法。且應用場景不同，其數據的特性也相差很多，為不同類型的數據使用相同的參數選取策略是不嚴謹的。

而Rabin指紋算法尋找分塊邊界時最底層原理是字符串匹配問題[18]。因此本文算法從其底層原理出發，摒棄設置參數和分塊條件等，將數據分塊問題轉化為指紋字符串的匹配問題，設計了指紋串匹配分塊算法。結合上述求出的數據塊指紋Hash(Ci)(i=1,2,3,…,n-w+1)，使用模式串Pw,進行塊指紋和模式串Pw的匹配。DWFM在映射指紋、選擇Pw和滑動窗口大小時均使用預測大小w作為基準，是為了使分塊大小和結果都體現最佳分塊大小時的特性。

當某一塊Ci(i=1,2,3,…,n-w+1)的指紋Hash(Ci)與模式串Pw的指紋值Hash(Pw)匹配成功時，在此塊的右側邊界創建一個分塊。若超過分塊大小上界Cmax都未能匹配成功，則在Cmax處創建分塊。

在匹配過程中，可以使用Sunday[19]等字符串匹配算法來加速匹配，當匹配失敗時，能夠盡量多地跳過不可能匹配的字符，Sunday匹配過程如圖3所示。

圖3 Sunday算法匹配過程 Fig. 3 Matching process of Sunday algorithm

Rabin算法在分塊時每滑動一字節需要模運算判斷一次，不滿足分塊條件時也不能跳過數據；相比之下，本文的分塊算法不僅無需設置參數，而且處理速度較快。指紋串匹配分塊算法描述如下。

算法2 指紋串匹配分塊算法(Chunking Algorithm based on Fingerprint Matching, CAFM)。

輸入 數據塊指紋序列Hc;

輸出 分塊序列Cki。

1)

BEGIN

2)

d=0；

//d代表當前滑動窗口所滑過的字符長度

3)

WHILE(d≤Cmax&&窗口內的字符長度等于w)

//當d的長度小于分塊上界Cmax

//w代表滑動窗口的大小即預期分塊大小

4)

sliding window, matching fingerprints use Sunday;

//使用Sunday算法進行指紋串匹配

5)

IFHash(Ci) ==Hash(Pw) THEN;

//當數據塊Ci的指紋等于模式串Pw的指紋

6)

create a new chunkCki;

//若塊指紋與模式串指紋匹配成功，則建立分塊

7)

window come toCkinext position;

//滑動窗口來到塊Cki的下一個位置

8)

d=0;

//將d的長度置為零

9)

ELSE

10)

skip characters not possible to match;

//向右滑過盡可能多的不匹配字節

11)

d=d+skip.length;

//d的長度變化為d的長度加上滑過的長度skip.length

12)

IFd>CmaxTHEN;

13)

Ci==Cmax;

//Cmax范圍內沒有匹配成功，則在Cmax處進行硬分塊

14)

creatCki

//其中i=1,2,…,k,k代表分塊個數

15)

window come toCkinext position;

16)

d=0;

17)

END

2.5 指紋串匹配的重復數據刪除算法

對待檢測數據D使用CAFM算法進行分塊后，設計了Winnowing指紋串匹配的重復數據刪除算法(DWFM)。使用MD5算法[20]為每一個數據塊生成一個獨一無二的指紋，由于MD5指紋具有唯一性，且無論任何人對數據作了任何修改，即使是很小的改動，其MD5值也會發生很大變化，因此MD5值能夠準確檢測數據塊是否重復，保證重復數據塊檢測結果的正確性。

在進行重復數據刪除時，將每一個待檢測塊的指紋值MD5(Di)(i=1,2,…,k)與存儲或備份系統中的數據塊進行指紋對比。若待檢測數據塊Di的指紋與系統中某一塊的指紋完全相同，則說明Di為重復數據塊，直接刪除不予存儲，并更新索引表，將該塊的引用次數加1；否則，說明系統中沒有與Di內容重復的數據塊，則將Di存儲到系統中，并在元數據表中維護一條Di的信息。

3 算法實驗分析和結果

實驗使用Java語言實現了DWFM，測試在Windows環境下進行，操作系統為Windows 7 Ultimate，硬件環境為Intel Pentium CPU G3200 @ 3.00 GHz處理器，4 GB內存容量，500 GB的SAS硬盤，千兆以太網。實驗模擬構建了一個客戶端和一個服務器節點，為了檢驗對不同的文件類型采用不同的分塊策略下的算法性能，實驗采用了多種類型的真實數據集，包括：TXT、DOC、HTML、PPT、PDF、VMDK等。其中，TXT、DOC、PPT、PDF類型數據由AWS、Google以及Twitter數據平臺獲取，包括大量的用戶狀態、影評和公開信息；HTML數據集從微博中爬取，信息的多次轉發具有重復性；VMDK數據集采用ubuntu8.04與14.04兩個版本。獲取的不同類型數據集的大小和數量相近，方便對實驗結果進行統一化分析。另外，同一類型數據的內容為同一領域，保證了數據之間具有相似性和重復性。實驗數據集如表1所示。

表1 實驗數據集Tab. 1 Datasets of experiment

實驗具體內容：在服務器端存放由表1中數據集組成的文件集合A,每次實驗分別使用FSP、CDC和CAFM分塊算法對A進行分塊，形成原始數據。改變A的內容存放在客戶端，使其與A有重復率r,形成待檢測數據集B。隨機連續地從客戶端向服務器端發送文件，并采用與服務器端相同的分塊算法分塊后進行重復數據刪除。實驗驗證了不同分塊算法對不同類型數據重刪率的影響，以及不同重復率r時的算法時間。

為了驗證重復數據刪除算法的效果，實驗設置了重復刪除率：R=重復刪除數據量/原始數據總量，重刪率實驗結果如圖4所示。無論采用哪種分塊的重復數據刪除算法都能在一定程度上減少數據的最終存儲量；除VMDK類型外，對于所有類型的文件，DWFM的重刪率都要高于FSP與CDC算法。例如對TXT數據，DWFM重刪率高于FSP算法13.557%，高于CDC算法10.289%。由于DWFM對數據進行分塊預測，根據數據自身的類型和特性來選擇合適的分塊大小，因此其分塊效果更加符合重復數據刪除的邊界條件，使得算法的重刪率較其他兩種算法高出很多。三種重復數據刪除算法對TXT、DOC、HTML和VMDK類型的文件重刪效果都較好，而對PPT和PDF類型的數據相對較差，這主要是因為PPT類型中的數據形式多變，且位置隨意，需要對數據進行嚴格的預處理，因此影響了重刪率。

圖4 不同文件類型的算法重刪率對比 Fig. 4 Comparison of deduplication rates for different file types

為了驗證不同重復率r以及重復分布情況對重復數據刪除性能的影響，對TXT數據集進行了相同數據集、不同重復率下的處理時間實驗，實驗結果如圖5所示。DWFM處理時間較短，且處理時間隨r的增加呈下降趨勢，逐漸趨近于FSP。當重復率r為0.7時，DWFM相對CDC算法改進最大，處理時間縮短了15.6 min，算法性能提升了18.31%。

圖5 不同重復率r時的算法時間對比 Fig. 5 Algorithm time comparison at different rate r

結合理論分析和實驗結果，對DWFM的復雜度進行全面分析，結果如表2所示，DWFM所消耗的時間復雜度包括以下幾點：

1)CAFM在進行數據分塊之前，需要通過預測模型選取最佳分塊大小，由預測算法公式可得，其時間復雜度為Tw=O(n)；

2)使用Winnowing算法計算待檢測數據流D中每個長度為w的子塊的指紋值，其時間復雜度為Th=O(n-w+1)，其中n為D中的字符數；

3)選擇模式串Pw的時間復雜度Tp=O(i+w-1)，其中i代表指紋組個數；

4)使用CAFM和Sunday算法進行分塊的時間復雜度Tc=O(n)；

5)MD5指紋計算與對比等重復數據檢測操作的時間復雜度為Td=O(m)，其中m表示需要對比的數據塊個數。

因此，DWFM總的時間復雜度T為：

T=Tw+Th+Tp+Tc+Td=2O(n)+O(m)+

O(n-w+1)+O(i+w-1)

(7) 表2 算法復雜度對比Tab. 2 Algorithm complexity comparison

由表2可得，FSP算法采用固定分塊大小，只需分塊后計算MD5指紋即可判斷是否為重復數據，因此算法時間最短；但由于無法檢測到文件內部重復，因此在實際中應用較少。而CDC算法首先需要使用Rabin算法計算指紋，然后利用參數取模條件來尋找分塊邊界，最后計算MD5指紋來判斷重復，且在分塊和指紋比對過程中無法跳過數據，只能按字節依次進行判斷，因此產生了大量的無用指紋，增加了指紋開銷和算法時間。DWFM在分塊前需要預測分塊大小，產生一定的時間復雜度，但在分塊時使用ASCII/Unicode指紋，而非Rabin指紋，計算開銷較小；而且利用指紋字符串匹配的方式來確定分塊邊界，在匹配失敗時能跳過盡可能多的字符，較顯著地減少了指紋計算次數。綜上對比，DWFM擁有更好的應用前景。

4 結語

本文算法將Winnowing算法引入重復數據刪除來減少指紋計算開銷，在分塊時無需預先設置參數，而是根據Rabin的底層原理，設計了指紋串匹配的分塊算法。該算法特別適合用來解決數據塊級重復數據刪除時的復雜分塊問題，尤其是在待檢測數據類型多變、重復內容分布不均的情況時，能夠得出更合理的分塊大小，在文件內部檢測到更多的重復數據。通過實驗與FSP和CDC算法相比，本文算法分塊大小更加準確，計算和對比開銷較小，且重復檢測沒有誤判率，擁有更好的應用前景。

參考文獻(References)

[1] SUN Y, ZENG C Y, CHUNG J, et al. Online data deduplication for in-memory big-data analytic systems [C]// Proceedings of 2017 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2017:1-7.

[2] ZHENG Y, DING W X, YU X X, et al. Deduplication on encrypted big data in cloud [J]. IEEE Transactions on Big Data, 2016, 2(2): 138-150.

[3] 熊金波,張媛媛,李鳳華,等.云環境中數據安全去重研究進展[J].通信學報,2016,37(11):169-180.(XIONG J B, ZHANG Y Y, LI F H, et al. Research progress on secure data deduplication in cloud [J]. Journal on Communications, 2016, 37(11): 169-180.)

[4] BHAGWAT D, ESHGHI K, LONG D D E, et al. Extreme binning: scalable, parallel deduplication for chunk-based file backup [C]// Proceedings of 2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems. Piscataway, NJ: IEEE, 2009: 1-9.

[5] LI Z B, HE K J, LIN F N, et al. Deduplication of files in cloud storage based on differential bloom filter [C]// Proceedings of 2016 7th IEEE International Conference on Software Engineering and Service Science. Piscataway, NJ: IEEE, 2016: 111-114.

[6] 張滬寅,周景才,陳毅波,等.用戶感知的重復數據刪除算法[J].軟件學報,2015,26(10):2581-2595.(ZHANG H Y, ZHOU J C, CHEN Y B, et al. User-aware de-duplication algorithm [J]. Journal of Software, 2015, 26(10): 2581-2595.)

[7] WIDODO R N S, LIM H, ATIQUZZAMAN M. A new content-defined chunking algorithm for data deduplication in cloud storage [J]. Future Generation Computer Systems, 2017, 71: 145-156.

[8] WANG G P, CHEN S Y, LIN M W, et al. SBBS: a sliding blocking algorithm with backtracking sub-blocks for duplicate data detection [J]. Expert Systems with Applications, 2014, 41(5): 2415-2423.

[9] 鄧雪峰,孫瑞志,張永瀚,等.基于數據位圖的滑動分塊算法[J].計算機研究與發展,2014,51(Suppl.):30-38.(DENG X F, SUN R Z, ZHANG Y H, et al. Sliding blocking algorithm based on data bitmap [J]. Journal of Computer Research and Development, 2014, 51(Suppl.): 30-38.)

[10] ZHANG Y C, HONG J, DAN F, et al. AE: an asymmetric extremum content defined chunking algorithm for fast and bandwidth-efficient data deduplication [C]// Proceedings of 2015 IEEE Conference on Computer Communications. Washington, DC: IEEE Computer Society, 2015: 1337-1345.

[11] SU H N, ZHENG D, ZHANG Y H. An efficient and secure deduplication scheme based on Rabin fingerprinting in cloud storage [C]// Proceedings of 2017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC). Piscataway, NJ: IEEE, 2017: 833-836.

[12] 閻芳,李元章,張全新,等.基于對象的OpenXML復合文件去重方法研究[J].計算機研究與發展,2015,52(7):1546-1557.(YAN F, LI Y Z, ZHANG Q X, et al. Object-based data de-duplication method for OpenXML compound files [J]. Journal of Computer Research and Development, 2015, 52(7): 1546-1557.)

[13] MIN J, YOON D, WON Y. Efficient deduplication techniques for modern backup operation [J]. IEEE Transactions on Computers, 2011, 60(6): 824-840.

[14] 王龍翔,董小社,張興軍,等.內容分塊算法中預期分塊長度對重復數據刪除率的影響[J].西安交通大學學報, 2016,50(12):73-78.(WANG L X, DONG X S, ZHANG X J, et al. Influence of expected chunk size on deduplication ratio in content defined chunking algorithm [J]. Journal of Xi’an Jiaotong University, 2016, 50(12): 73-78.)

[15] HIRSCH M, KLEIN S T, SHAPIRA D, et al. Controlling the chunk-size in deduplication systems [C]// Proceedings of the 2015 Prague Stringology Conference. Prague: PSC, 2015: 78-89.

[16] SCHLEIMER S, WILKERSON D S, AIKEN A. Winnowing: local algorithms for document fingerprinting [C]// Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2003: 76-85.

[17] LULU L, BELKHOUCHE B, HAROUS S. Overview of fingerprinting methods for local text reuse detection [C]// Proceedings of the 2016 International Conference on Computing and Network Communications. Piscataway, NJ: IEEE, 2016:1-6.

[18] MEYER D T, BOLOSKY W J. A study of practical deduplication [J]. ACM Transactions on Storage, 2012,7(4):1-20.

[19] 朱永強,秦志光,江雪.基于Sunday算法的改良單模式匹配算法[J].計算機應用,2014,34(1):208-212.(ZHU Y Q, QIN Z G, JIANG X. Improved single pattern matching algorithm based on Sunday algorithm [J]. Journal of Computer Applications, 2014, 34(1): 208-212.)

[20] CHO E M, KOSHIBA T. Big data cloud deduplication based on verifiable hash convergent group signcryption [C]// Proceedings of 2017 IEEE 3rd International Conference on Big Data Computing Service and Applications. Piscataway, NJ: IEEE, 2017: 265-270.

This work is partially supported by the National Natural Science Foundation of China (61502215).

WANGQingsong, born in 1974, M. S., associate professor. His research interests include big data, data mining.

GEHui, born in 1991, M. S. candidate. Her research interests include deduplication.