一種基于Simhash 算法的重復域名數據去重方法

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

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

0 引言

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

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

1 重復數據檢測技術

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

1.1 完全文件檢測技術

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

1.2 固定分塊檢測技術

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

1.3 可變分塊檢測技術

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

1.4 滑動塊檢測技術

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

1.5 小結

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

2 基于Simhash 算法的域名數據去重

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

2.1 域名數據文件特征分析

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

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

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

圖1 資源記錄格式

Name：主機域名；

TTL：該記錄有效時間；

IN：表示一個標準的 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 數據分塊

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

圖2 數據分塊流程圖

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

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

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

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

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

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

2.3 計 算 Simhash 值

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

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

其 中 ，xi，j表 示 關 鍵 詞 wi在 文 檔 yj中 出 現 的 次 數 ，表示所有關鍵詞的詞頻總和。

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

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

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

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

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

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

圖3 n 維向量列相加

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

圖4 計算 Simhash 指紋值

2.4 數據去重

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

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

3 實驗分析

3.1 實驗環境和實驗數據

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

圖5 數據分組

3.2 實驗參數選取

重復數據刪除率和執行算法所耗時長是評價數據去重性能的兩個重要指標。 為了評價本文介紹的方法在實際應用中的性能，本文設計了一系列實驗，從重復數據刪除率和算法執行時間兩個維度與傳統的數據去重算法進行對比實驗。

3.2.1 重復數據刪除率

重復數據刪除率[15]Ri定義為：

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

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

圖6 算法重復數據刪除率對比

3.2.2 算法執行時間

本文對各算法執行時間做了對比，結果如圖7所示。

圖7 算法執行時間對比

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

4 結論

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