并行多路徑傳輸過程數據相似性檢測仿真

趙 敏

(西安電子科技大學，陜西 西安 710071)

1 引言

計算機、互聯網的高速發展使得數據傳輸的狀態和質量成為了熱點研究課題。其中，對數據傳輸質量影響較為嚴重的就是數據本身的質量[1]。數據清理是提高數據源質量的有效手段之一。在數據清理過程中，為了減少數據源內的冗余信息，相似重復的記錄、檢測和清理成為了關鍵部分。根據所記錄的相似性檢測結果，能夠評測所傳輸的數據中是否含有重復記錄[2-3]。為此，有相關學者提出了一些關于傳輸過程數據相似性檢測的方法。

文獻[4]中提出了一種基于MapReduce模型的大數據相似重復記錄檢測方法，首先提取能夠轉移的傳輸數據，并使用MapReduce模型對數據進行相似性分析，然后提取傳輸數據將其導入表信息內，結合模糊哈希算法對其進行相似性計算，完成對傳輸數據的相似性檢測。但是該方法在將數據導入表信息內時，很容易受到噪聲的影響，導致相似性檢測結果不夠精準。

文獻[5]中提出了一種基于信息熵與模糊綜合評判融合的相似數據檢測方法，首先對比數據內每一種字段的相似度，然后對每一種字段賦予各部相同的權重，利用信息熵轉換傳輸數據的損失函數與非極大值抑制函數，并簡化網絡傳輸架構，再將轉換完成的傳輸數據輸送至架構內進行迭代，并與與原始數據進行對比，完成傳輸數據的相似性檢測。但是該方法需要對數據進行反復的迭代，導致檢測數據召回率較高。

針對上述問題，提出了一種并行多路徑傳輸過程數據相似性檢測方法。

2 并行多路徑傳輸過程數據相似性檢測

2.1 位碼的相似度架構

針對相似性檢測問題，通過位碼代替法來估算傳輸數據架構之間的相似度，這種方法憑借純粹的架構差異[6]與標簽序列差異來估算傳輸數據架構之間的相似度。

首先對傳輸數據的主干信息進行提取，其主干架構樹如圖1所示。其中，a代表所傳輸的數據集，b類代表數據子集，c類代表節點數據，d類代表子節點數據。

圖1 所傳輸數據主干架構樹結構圖

相似度架構流程如下：

1)對深度優先遍歷過程進行數值化操作。在提取傳輸數據主干架構樹之后，對其進行深度優先遍歷，對通過遍歷的每一種節點的子節點數量進行編碼，將傳輸數據主干架構表示為數值序列；

2)統一所有層次內最大子節點的數量，填充偽代碼。為解決樹內節點數量不等的問題，擬定一種偽節點方法：搜索樹內每一層節點的最大子節點數量，將這種最大子節點數當做每一種節點的子節點數量，對不足節點進行補全填充[7]。填充偽碼后的填充樹如圖2所示。

圖2 主干架構樹的填充樹結構圖

3)對填充術進行數值化處理后對其進行二進制化。通過偽節點填充操作將兩種樹之間含有的相等節點數量相互對比，其前提是數據集層數與架構是相等的。但是填充樹的架構在進行數值編碼為序列之后，會出現子節點的數值都是零的現象，并且葉節點的數量較多，序列內會產生大量的冗余信息，因此，需剔除每一種葉子節點的數值，則所傳輸的數值序列會通過上述過程簡化為一下形式：

深度遍歷主干架構樹的遍歷順序是：a——b1，c1，c2——b2，c3，c4——b3，c5；主干架構樹遍歷之后的數值化順序是：3，2，2，0，2，0，0，1，0；

利用二進制位碼代替主干架構樹，順序是：111，110，110，000，110，000，000，100，000；

4)估算相似度。相似度架構估算含有架構相似度估算與語義相似度估算兩種部分。

①架構相似度數值估算。對上述數值順序進行估算或異，憑借統計XOR結構內的數量就可以獲取填充樹的架構差異程度數值。

②語義相似度數值估算。語義相似度是利用樹內的幾種標記來進行估算的，憑借深度優先遍歷對樹進行偽代碼填充之后，獲取標簽的序列，然后按照順序相應的找出不同的標簽標記，然后估算獲取語義相似度數值。

在所提的并行多路徑傳輸過程數據相似性檢測方法中，等同看待架構與語義的作用，因此可得到最終的相似度架構估算結果如下

(1)

式中，DSI為傳輸數據i與j的架構相似度值，DLi，j為傳輸數據i與j的語義相似度值，Nmax為樹內節點的最大子節點數量，M為樹的基本單元數量。

2.2 優化編譯

傳輸數據的數據排版格式只會干擾到數據的可讀性，因此，編譯器會自動的忽略它們，注釋在編譯的預處理節點就會被剔除，因此修改注釋與重新排版產生的噪聲[8]會變成最容易且最早被剔除的對象，數據內的標識標記并不會對傳輸的運行效果產生任何干擾，因此能夠忽略編譯后的二進制數據內的標識符號，那么標識符號重新命名后存在的噪聲也會被剔除。

優化編譯過程使用控制流分析、依賴分析[9]與數據流分析技術，剔除公共子代表式，已達到減少估算的強度、優化數據傳輸中的跳轉和循環的目的。優化編譯過程能夠把等價的程序邏輯代表方式轉換成一種統一的形式，需使用代碼冗余、代表式拆分或者等價控制架構轉換手段修改數據編碼，通過編譯優化編譯可使樣本數據和初始數據生成的目標數據相同。

在優化編譯時，須通過更換注釋、重新排版、符重、標識重新命名、添加冗余的變量與語句、表達式的簡易拆解與替換控制節點來等價控制架構[10]。源數據被轉換成二進制目標數據后被剔除，但在改變數據碼塊和語句順序時所帶來的噪聲還沒有被剔除，改變語句的順序不僅僅是導致指令順序的轉變，導致偏移傳輸地址發生的轉變，因此需要進一步過濾噪聲。

2.2.1 反匯編

上述經過優化編譯過程產生并傳輸存在關聯行的二進制數據，通過反匯編工具把正在傳輸內的數據段轉換成匯編數據，剔除和傳輸特征沒有關聯的信息。相較于二進制指令，匯編代碼更為簡單、便捷，并且每一種匯編指令都存在一定的語義。若運行邏輯不同的傳輸程序，其相應的反匯編數據也一定是不相同的。

2.2.2 過濾噪聲

通過上述處理過程，傳輸數據被轉換成匯編數據，而匯編數據內的傳輸偏移地址、函數地址、部分跳轉指令與立即數都需要進行特殊的處理。

傳輸偏移地址是較為容易轉換的[11]，語句或是變量聲明順序轉變能夠導致數據偏移地址出現轉變。

函數地址與偏移地址相同也是一種容易轉變的地址。假如轉變函數體的數據就能夠導致函數的地址出現轉變。因此，本研究統一利用FUNCTIDN來表示函數地址，同時屏蔽掉函數地址的差異。

立即數用以表示傳輸數據的常量。為了避免常量轉換所產生的噪聲干擾，本研究統一利用CONSTANT代替匯編數據內的立即數。

2.2.3 決策函數

源數據通過歸一化處理后能夠反射成匯編指令集合。假設P1與P2代替兩種待檢測的數據，F(P1)與F(P2)代表P1與P2歸一化后的匯編指令集合，Sim(P1，P2)代表兩種數據的相似度，首先建立決策函數如下所示

(2)

相似度Sim滿足Sim(P1，P2)=1，并且Sim(P1，P2)=Sim(P2，P1)。憑借先驗知識，該公式所估算出的結果比其它常見的關聯系數估算過程有著更好的區分度。同時，使用式(2)另外的一種優點就是其估算的結構不會被指令的順序所干擾，從而能夠有效過濾掉數據塊或是語句順序轉變所帶來的噪聲[12]。

因為歸一化流程內已經基本的過濾了轉變所帶來的噪聲，數據的相似度往往會達到一種比較高的峰值，相似和不相似數據之間的相似度會呈現出較為顯著的差異。

2.2.4 傳輸數據的相似性檢測

首先構建下三角矩陣，將傳輸數據之間的相似度對比轉換為儲存矩陣之間的相似度對比。

儲存矩陣不僅含有傳輸數據的架構信息，矩陣的坐標還能夠代表數據樹的架構，同時也包含了傳輸數據的語義信息。矩陣內儲存的數值就是數據樹內節點的內容信息，內容信息代表了傳輸數據的語義。因此這種憑借矩陣存儲的傳輸數據相似度就是包含語義相似度，同時還含有架構相似度。

儲存矩陣間相似度估算過程如下

sim(x，y)=0.5×(seman(x，y)+strue(x，y))

(3)

式中，seman(x，y)為數據x與y的語義相似度，strue(x，y)為傳輸數據x與y的架構相似度。其中，語義相似度的估算過程如式(4)所示

(4)

式中，變量c為在矩陣內同一種坐標的相同標簽數，M為填充樹內的元素數量，也就是儲存矩陣內的元素數量。

在此基礎上，將儲存矩陣進行轉換，將其轉換為一種數值化狀態，轉換過程如式(5)所示

(5)

為便于估算架構的相似度，將矩陣按照順序將其表達為向量的形式。通過這個思路，將傳輸數據樹表達成為n維的向量。由于是通過下三角矩陣的形式進行儲存的，因此，矩陣相似度估算最終是依靠向量的相似度估算而得到的。在本文研究中，使用向量的相關系數方法對相似度進行估算。向量之間的關聯系數表示傳輸數據之間的架構相似度，向量間關聯系數計算過程如下所示

(6)

式中，n代表總數據量，i∈n。在此基礎上，得到并行多路徑傳輸過程數據相似性計算過程如下

(7)

3 仿真與結果分析

為驗證所提的并行多路徑傳輸過程數據相似性檢測方法的應用效果，設計如下仿真，通過結果分析驗證相似性檢測過程的有效性。

仿真環境設置情況如下：Windows Server 2017， R2Intel(R) Xeon (TM) CPU E5-2650@2.30 GHz2.30GHzwith 32.0GB of RAM，利用MATLAB 2014a編程實現。

實驗指標為：①數據召回率；②檢測過程損耗；③相似性檢測誤差百分比。為進一步保證實驗結果的可說明性，將文獻[4]中基于MapReduce模型的大數據相似重復記錄檢測方法與文獻[5]中基于信息熵與模糊綜合評判融合的相似數據檢測方法作為對照組，用以突出本文方法的應用性能。

首先測試不同檢測方法的數據召回率。在數據相似性檢測過程中，檢測結果的質量可從數據召回率和檢測精度兩個角度進行評價。其中，數據召回率和檢測精度成反比。以60min為測試時間，統計不同數據相似性檢測方法的數據召回率，結果如圖3所示。

圖3 不同方法的檢測數據召回率對比圖

通過圖3能夠得知，隨著檢測時間的推移，不同方法的檢測數據召回率也在不斷變化，文獻[5]方法的最大數據召回率為10.7%，文獻[4]方法的最大數據召回率為9.1%，而本文方法的最大數據召回率為5.2%，且本文方法的數據召回率曲線大部分都位于兩種對比方法的數據召回率曲線之下，說明本文方法的檢測數據召回率較小。這是因為本文方法引入了決策函數，而傳統方法是通過估算傳輸數據交集開銷，只考慮了數據詞頻因素的干擾，降低了抽樣估算的精度，致使召回率較大。

同樣以60min為測試時間，統計不同數據相似性檢測方法檢測過程的損耗情況，結果如圖4所示。

圖4 不同方法的檢測過程損耗對比圖

通過圖4可知，隨著檢測時間的推移，不同方法的檢測過程損耗也在發生變化，文獻[4]方法的最大損耗為70dB，文獻[5]方法的最大損耗為64.2dB，而本文方法的最大損耗為58dB，說明本文方法檢測過程的能量損耗較小。

為進一步驗證本文方法的應用性能，計算不同方法的相似性檢測誤差百分比。測試數據集數量為500組，共進行10次測試，計算其均值，統計結果如表1所示。

表1 不同方法的相似性檢測誤差百分比對比

通過表1能夠看出，文獻[4]方法的相似性檢測誤差百分比處于14-17%之間，平均值為15.3%；文獻[5]方法的相似性檢測誤差百分比處于11-13%之間，平均值為12.2%；而本文方法的相似性檢測誤差百分比處于3-6%之間，平均值為4.5%。通過對比可知，本文方法的相似性檢測誤差較小，檢測有效性更高。

4 結論

為提高網絡的使用效率與吞吐量，提出一種并行多路徑傳輸過程數據相似性檢測方法，通過估算傳輸過程數據架構相似度、將數據轉換為數值化狀態、利用反匯編過濾匯編數據內的噪聲、對比儲存矩陣之間的相似度等過程實現對相似數據的檢測。文章還通過仿真證明了該方法具有數據召回率、檢測損耗和相似性檢測誤差較小的優點。

研究還發現，憑借優化編譯過程剔除數值化后的公共子代表式能夠減少后期檢測估算的強度，有效減少檢測誤差。