一種基于Simhash 算法的重復(fù)域名數(shù)據(jù)去重方法

侯開茂，韓慶敏，吳云峰，黃 兵，張久發(fā)，柴處處

(中國電子信息產(chǎn)業(yè)集團有限公司第六研究所，北京100083)

0 引言

隨著電子信息技術(shù)的發(fā)展，各行各業(yè)都產(chǎn)生了大量的數(shù)據(jù)信息，根據(jù)國際數(shù)據(jù)公司(International Data Corporation，IDC)的最新預(yù)測 ：到 2023 年 ，中國的數(shù)據(jù)量將達到40 ZB，并且隨著5G 技術(shù)的普及，數(shù)據(jù)量增長將會迎來又一個新的高潮[1]。 有研究發(fā)現(xiàn),這些數(shù)據(jù)中超過60%都是重復(fù)冗余數(shù)據(jù)[2]，傳輸和存儲這些冗余數(shù)據(jù)不僅造成了存儲資源和網(wǎng)絡(luò)資源的嚴重浪費，也降低了使用數(shù)據(jù)的效率。 并且隨著時間推移，這些數(shù)據(jù)帶來的冗余問題會越來越嚴重。 域名[3](Domain Name)作為互聯(lián)網(wǎng)中頻繁使用的數(shù)據(jù)類型之一，是一種特殊的數(shù)據(jù)形式，其對字符的變化敏感度極高，一個字符的變化往往會對使用結(jié)果產(chǎn)生嚴重的影響。 因此，處理重復(fù)域名數(shù)據(jù)需要采用精確而且高效的去重技術(shù)。

已有重復(fù)數(shù)據(jù)處理技術(shù)中，完全文件檢測(Whole File Detection，WFD)技術(shù)[4]無法對內(nèi)容進行查重處理，固定分塊(Fixed-Sized Partition，F(xiàn)SP)檢測技術(shù)、可變分塊檢測技術(shù)和滑動塊檢測技術(shù)都是針對數(shù)據(jù)共有特征的粗粒度去重，直接用于重復(fù)域名的處理效果并不理想。 因此，本文在已有重復(fù)數(shù)據(jù)檢測技術(shù)的基礎(chǔ)上，引入Simhash 算法，結(jié)合域名數(shù)據(jù)的結(jié)構(gòu)特征，改進計算文本特征值的方式，提出了一種基于 Simhash 算法的重復(fù)域名數(shù)據(jù)去重方法。 經(jīng)過實驗對比看出，該方法對于處理重復(fù)域名數(shù)據(jù)效果更好，同時在時間開銷上也和原有技術(shù)差別不大，對于處理重復(fù)域名數(shù)據(jù)具有比傳統(tǒng)去重技術(shù)更好的實用價值。

1 重復(fù)數(shù)據(jù)檢測技術(shù)

現(xiàn)有的重復(fù)數(shù)據(jù)檢測技術(shù)都是通過檢測出文件中重復(fù)數(shù)據(jù)并進行刪除，只保留唯一的數(shù)據(jù)對象，然后使用指向此唯一數(shù)據(jù)對象的指針代替其他重復(fù)數(shù)據(jù)，以達到所有數(shù)據(jù)都只存儲一次的效果。目前主要有完全文件檢測技術(shù)[4]、固定分塊檢測技術(shù)、可變分塊檢測技術(shù)和滑動塊檢測技術(shù)[5]。

1.1 完全文件檢測技術(shù)

完全文件檢測技術(shù)是將目標(biāo)文件作為檢測單位，以文件為粒度進行相同數(shù)據(jù)查找的方法。 該算法首先對整個文件進行hash 計算，得到一個文件級的 hash 值，然后將計算得到的 hash 值與已經(jīng)存儲的所有 hash 值進行比較，如果與存儲 hash 值相同，則可以判斷文件數(shù)據(jù)重復(fù)，只需用一個指向已經(jīng)存儲數(shù)據(jù)的指針替換該文件即可，不必對數(shù)據(jù)進行實際的存儲操作。 如果沒有相同的值，則將該文件存儲為新文件[6]。

1.2 固定分塊檢測技術(shù)

固定分塊[7-8]檢測技術(shù)是將文件劃分為同等大小的文件塊，并以塊為單位進行hash 計算的檢測方法。 該算法檢測重復(fù)數(shù)據(jù)的主要過程為：(1)定義分塊策略，指定一個獨立于文件內(nèi)容的固定文件塊大小值，以此值為標(biāo)準(zhǔn)將整個文件分為若干塊；(2)對每個文件塊進行 hash 運算，得到一個可以唯一標(biāo)識該塊的指紋值；(3)將該值與系統(tǒng)中存儲的指紋值進行比較，如果存在相同的值，則可以判斷該文件塊數(shù)據(jù)重復(fù)，用一個指向已經(jīng)存儲文件塊的指針替換該文件塊即可，不對該文件塊進行實際的存儲操作。 如果沒有相同的值，則新分配一塊存儲空間存儲該文件塊。 由于該技術(shù)對數(shù)據(jù)變化敏感度很高，文件塊中一兩個字符的不同都會對檢測結(jié)果產(chǎn)生極大影響，因此在實際應(yīng)用中該技術(shù)多用于圖片、視頻等變化比較少的數(shù)據(jù)查重。

1.3 可變分塊檢測技術(shù)

可變分塊檢測技術(shù)基于內(nèi)容對文件進行分塊，所以分出的文件塊大小也不相等。 對內(nèi)容計算最常用的是 CDC(Content-Defined-Chunking)算法，該算法基于 Rabin 指紋[9]對文件內(nèi)容進行計算，然后根據(jù)計算結(jié)果進行分塊。 其過程為：(1)從文件頭開始，采用固定大小的滑動窗口對文件內(nèi)容進行覆蓋；(2)在窗口的每個邊界采用Rabin 指紋函數(shù)計算出該窗口邊界下文件塊的指紋值；(3)當(dāng)指紋值滿足某個預(yù)定條件(例如某個特殊數(shù)字的倍數(shù))時，就將該窗口邊界作為文件塊的邊界；(4)重復(fù)以上過程，直到所有文件被劃分為不同大小的塊。 與FSP 技術(shù)不同的是該方法對數(shù)據(jù)變化不敏感，數(shù)據(jù)發(fā)生變化時也只會影響鄰近數(shù)據(jù)塊的計算值，但是分塊大小的設(shè)定會影響該方法的去重效果。

1.4 滑動塊檢測技術(shù)

滑動塊檢測技術(shù)[10]采用兩級處理的方式對文件進行查重處理。 該技術(shù)首先對文件基于文件粒度進行處理，如果文件級比較值相同，則采用更細粒度的算法進行進一步處理。 該方法結(jié)合了文件級檢測和內(nèi)容級檢測的優(yōu)點，查重的正確率更高。 但是該技術(shù)過程繁瑣，效率也比較低，處理相同數(shù)據(jù)量的數(shù)據(jù)能耗比其他方法高，因此不適合用來處理大規(guī)模的數(shù)據(jù)。

1.5 小結(jié)

本節(jié)介紹了4 種常見的重復(fù)數(shù)據(jù)檢測技術(shù)，對處理過程和算法特征進行了深入分析。 在幾種算法中，完全文件檢測算法以文件為粒度對數(shù)據(jù)進行檢驗，檢測過程簡單，檢測效率高，但是不能用于對文件內(nèi)部數(shù)據(jù)的重復(fù)內(nèi)容進行檢測。 固定分塊檢測技術(shù)對數(shù)據(jù)變化敏感度很高，文件塊中一兩個字符的不同都會對檢測結(jié)果產(chǎn)生極大影響，因此不適合處理需要頻繁更新的數(shù)據(jù)。 而可變分塊技術(shù)中的CDC算法檢測技術(shù)彌補了前二者在文件內(nèi)容處理上的不足，對于相差幾個字節(jié)的數(shù)據(jù)可以有很好的檢測效果。 滑動塊檢測技術(shù)結(jié)合了文件級檢測和內(nèi)容級檢測的優(yōu)點，查重的正確率更高，但是，該方法存在計算過程繁瑣、效率低下、能耗高等缺點，不適合實時性要求高、成本預(yù)算低的文件處理。 基于以上對算法適用場景的分析以及域名數(shù)據(jù)對符號變化敏感的特點，基于CDC 算法的檢測技術(shù)最適合與Simhash 算法結(jié)合進行重復(fù)域名數(shù)據(jù)檢測，因此，在后面的內(nèi)容中，本文將采用基于CDC 算法的檢測技術(shù)對數(shù)據(jù)進行分塊去重。

2 基于Simhash 算法的域名數(shù)據(jù)去重

傳統(tǒng)去重算法檢測出的數(shù)據(jù)往往包含了一些相似而不相同的數(shù)據(jù)，造成檢測結(jié)果不理想的情況。這是因為不同的數(shù)據(jù)文件具有不同的結(jié)構(gòu)特征，采用傳統(tǒng)的重復(fù)數(shù)據(jù)檢測技術(shù)，只能通過統(tǒng)一的方法針對具有共性的部分作出檢測，而不能針對具體的數(shù)據(jù)對癥下藥。 因此，本文在分析域名數(shù)據(jù)結(jié)構(gòu)特征的基礎(chǔ)上，提出了基于Simhash[11]算法的域名數(shù)據(jù)去重方法。

2.1 域名數(shù)據(jù)文件特征分析

數(shù)據(jù)的語義特征對于查重技術(shù)和算法的選擇至關(guān)重要，不同的查重技術(shù)和算法對于不同格式的文件的去重效果有很大的影響。 因此，在對數(shù)據(jù)處理之前，有必要對域名數(shù)據(jù)的特征進行分析。

域名是互聯(lián)網(wǎng)上用于解決計算機名稱和IP 地址之間映射關(guān)系的一種方法。 一個完整的域名由一串由“.”分隔符分隔的字符串組成。 域名右邊第一個被“.”隔開的字符串代表的是頂級域名(TLD，也稱為一級域名)，依次向左分別是二級域名，三級域名……以中華人民共和國教育部官方網(wǎng)站域名(www.moe.gov.cn)為例，“cn”“gov”“moe”依次代表了一級域名、二級域名和三級域名[12]。

每一個域名都唯一對應(yīng)一個IP 地址，這種對應(yīng)關(guān)系以資源記錄(Resource Records，RR)的形式存儲在域名解析文件中。 一個資源記錄對應(yīng)一個域名和IP 地址的映射關(guān)系及其他相關(guān)信息。圖1 是常用的資源記錄格式，其各字段含義如下：

圖1 資源記錄格式

Name：主機域名；

TTL：該記錄有效時間；

IN：表示一個標(biāo)準(zhǔn)的 DNS Internet 類；

RR-Type：記錄類型，如 A、AAAA、SOA、NS、MX、CNAME 等；

Value：IP 地址。

例如：(www.node3.com IN A 1.1.1.1)代表了一條域名為“www.node3.com”，IP 地址為 1.1.1.1 的IPv4 資源記錄。

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

通過特征分析發(fā)現(xiàn)，域名數(shù)據(jù)可以以文件為粒度進行重復(fù)數(shù)據(jù)檢測，也可以先以資源記錄為粒度進行分塊，進一步以字段進行分詞檢測。 本文采用先分塊再分詞的方法進行查重。 首先基于CDC算法對文件進行分塊，再對分塊結(jié)果按字段分詞處理。 本小節(jié)主要介紹分塊的過程，分詞的過程將在下一部分介紹。 數(shù)據(jù)分塊的流程如圖2 所示，具體過程為：

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

(1)將整個文件讀入臨時緩沖區(qū)；

(2)創(chuàng)建一個臨時列表(List)；

(3)從文件頭部開始將緩沖區(qū)文件讀入臨時列表，從 Name 字段開始讀取，到 Value 字段結(jié)束，停止讀入；

(4)將臨時列表中的數(shù)據(jù)寫入到列表中，并將臨時列表清空；

(5)重復(fù)第(3)、(4)兩步，直到將整個文件都寫入列表。

經(jīng)過以上處理，得到一個列表，列表的每個元素就是一個資源記錄，這樣就可以以資源記錄為粒度對數(shù)據(jù)進行比較。

2.3 計 算 Simhash 值

由于資源記錄具有明顯的結(jié)構(gòu)特征，通過結(jié)構(gòu)屬性進行結(jié)構(gòu)分詞比基于語義特征分詞效率更高，因此本文通過結(jié)構(gòu)分詞之后再結(jié)合Simhash 算法，從列表中按數(shù)據(jù)塊即資源記錄計算指紋值。Simhash算法以分詞結(jié)果中關(guān)鍵詞為特征值[13]，以關(guān)鍵詞出現(xiàn)的頻率為權(quán)重，各關(guān)鍵詞的權(quán)重集合作為一個特征向量 N，然后采用 MD5 算法產(chǎn)生一個 m 位的簽名G，再對特征向量加權(quán)，對于最終向量的每一位如果大于 0 則為 1，否則為 0，這樣就能得到最終的Simhash 的指紋簽名。

在本文中，計算權(quán)重采用經(jīng)典的TF-IDF(Term Frequency-Inverse Document Frequency)算 法 ，TF 詞 頻指的是關(guān)鍵詞在文件中出現(xiàn)的頻率，關(guān)鍵詞wi的詞 頻 fwi，j表示為：

其 中 ，xi，j表 示 關(guān) 鍵 詞 wi在 文 檔 yj中 出 現(xiàn) 的 次 數(shù) ，表示所有關(guān)鍵詞的詞頻總和。

計算出權(quán)重即詞頻，指紋值計算的具體過程可以描述為：

(1)確定目標(biāo)指紋值的維度m。

(2)初始化向量 V=(v1，v2，…，vm)，初始值為 0。

(3)對列表的每一個元素(資源記錄)根據(jù)屬性分詞，得到 Name、TTL、IN、RR-Type、Value 五個分詞。

(4)采用MD5[14]算法，針對每一個分詞計算出一個數(shù)字簽名。 對于簽名的每一位，如果是1，則用權(quán)重和碼值相乘；如果是0，則用權(quán)重和碼值負相乘，得到每個關(guān)鍵詞的特征向量。

(5)將所有特征向量進行如圖3 所示列合并，得到和向量 S，對 S 進行降維處理，對于 S 的每一位，如果大于 0 則為 1，否則為 0，得到的結(jié)果就是目標(biāo)資源記錄的Simhash 指紋值。

圖3 n 維向量列相加

采用Simhash 算法計算一條資源記錄指紋值的算法過程如圖4 所示。

圖4 計算 Simhash 指紋值

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

經(jīng)過數(shù)據(jù)分塊和指紋值計算，文件里的每一條資源記錄都有且只有一個指紋值P 對其進行了標(biāo)識。 因此，判斷數(shù)據(jù)的重復(fù)性問題被簡化成了判斷指紋值重復(fù)的問題。 對指紋值P，將其與已存儲的指紋值Pi進行異或運算：

如果 P 與其中一個存儲值異或結(jié)果是 0， 則說明兩數(shù)相等，其對應(yīng)的資源記錄與之前存儲的資源記錄重復(fù)，放棄對該條記錄的存儲。 如果P 與所有存儲值異或結(jié)果為1，則說明該指紋值與所有存儲值不相等，即該資源記錄為新數(shù)據(jù)，將該數(shù)據(jù)和指紋值存入系統(tǒng)。 重復(fù)以上步驟直到列表為空，就完成了對文件的所有數(shù)據(jù)進行去重處理。

3 實驗分析

3.1 實驗環(huán)境和實驗數(shù)據(jù)

實驗仿真環(huán)境采用ASUS 電腦，處理器為Intel COREi7 8th Gen，8 個核心處理器，8 GB 內(nèi) 存 ，512 GB固態(tài)硬盤，64 位 Windows 10 系統(tǒng)。 以域名數(shù)據(jù)文件為實驗對象，將本文的實驗結(jié)果與傳統(tǒng)數(shù)據(jù)去重技術(shù)結(jié)果進行對比。 數(shù)據(jù)集是從 3 000 萬條 CN 頂級域下的域名數(shù)據(jù)中篩選出的200 萬條無重復(fù)域名的數(shù)據(jù)，將該數(shù)據(jù)集平均分成5 組，依次命名為A組、B 組、C 組、D 組、E 組。每組包含 40 萬條 互不 重復(fù)的域名數(shù)據(jù)。 再將這200 萬條域名數(shù)據(jù)復(fù)制五份，分別命名為 1 組、2 組、3 組、4 組、5 組，然后分別將 A 組數(shù)據(jù)和 1 組數(shù)據(jù)組合成一組， 命名為 A1組；將 B 組數(shù)據(jù)和 2 組數(shù)據(jù)組合成一組，命名為 B2組；依次類推，組合出 C3 組、D4 組、E5 組。 實驗數(shù)據(jù)準(zhǔn)備過程如圖5 所示。 經(jīng)過以上處理，每組數(shù)據(jù)包含了240 萬條數(shù)據(jù)，其中有40 萬對是重復(fù)數(shù)據(jù)。實驗的目標(biāo)就是通過設(shè)計程序，將40 萬對重復(fù)數(shù)據(jù)中的40 萬條重復(fù)數(shù)據(jù)進行查找和刪除。

圖5 數(shù)據(jù)分組

3.2 實驗參數(shù)選取

重復(fù)數(shù)據(jù)刪除率和執(zhí)行算法所耗時長是評價數(shù)據(jù)去重性能的兩個重要指標(biāo)。 為了評價本文介紹的方法在實際應(yīng)用中的性能，本文設(shè)計了一系列實驗，從重復(fù)數(shù)據(jù)刪除率和算法執(zhí)行時間兩個維度與傳統(tǒng)的數(shù)據(jù)去重算法進行對比實驗。

3.2.1 重復(fù)數(shù)據(jù)刪除率

重復(fù)數(shù)據(jù)刪除率[15]Ri定義為：

其中，D(i)表示文件中重復(fù)的數(shù)據(jù)量，E(i)表示實驗過后還剩的重復(fù)數(shù)據(jù)量。

通過圖6 的實驗結(jié)果可以看出，本文采用的算法在域名數(shù)據(jù)去重效率上相比于其他傳統(tǒng)的去重算法效果更好。

圖6 算法重復(fù)數(shù)據(jù)刪除率對比

3.2.2 算法執(zhí)行時間

本文對各算法執(zhí)行時間做了對比，結(jié)果如圖7所示。

圖7 算法執(zhí)行時間對比

通過對比可以看出，本文所研究的算法執(zhí)行時間稍微多于其他算法，這可能與本文在處理域名數(shù)據(jù)時，處理粒度較細有關(guān)。 但是本文介紹的方法時間上比其他幾種算法更穩(wěn)定，這說明該算法對數(shù)據(jù)變化敏感度不大，更適合處理需要頻繁更新的數(shù)據(jù)。

4 結(jié)論

本文在傳統(tǒng)數(shù)據(jù)去重技術(shù)的基礎(chǔ)上，引入Simhash算法，結(jié)合特定數(shù)據(jù)文件類型——域名數(shù)據(jù)的特征，對數(shù)據(jù)分塊的過程以及特征值指紋計算方法進行了改進。一方面，針對域名數(shù)據(jù)的結(jié)構(gòu)化特點，采用了基于CDC 算法可變分塊的數(shù)據(jù)分塊方法對文件進行分塊；另一方面，基于域名數(shù)據(jù)資源記錄的字段特征，引入了基于Simhash 算法的指紋值計算方法。 相比于傳統(tǒng)去重技術(shù)籠統(tǒng)的去重方式，該方法專門針對域名數(shù)據(jù)的去重問題進行研究，提高了檢測重復(fù)域名數(shù)據(jù)的效率。 在未來的工作中，一方面繼續(xù)優(yōu)化算法，減少算法的執(zhí)行時間；另一方面，可以將這種有的放矢的方式應(yīng)用到其他數(shù)據(jù)領(lǐng)域，使得數(shù)據(jù)去重技術(shù)體現(xiàn)出更好的實用價值。