趙 敏

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

1 引言

計(jì)算機(jī)、互聯(lián)網(wǎng)的高速發(fā)展使得數(shù)據(jù)傳輸?shù)臓顟B(tài)和質(zhì)量成為了熱點(diǎn)研究課題。其中，對(duì)數(shù)據(jù)傳輸質(zhì)量影響較為嚴(yán)重的就是數(shù)據(jù)本身的質(zhì)量[1]。數(shù)據(jù)清理是提高數(shù)據(jù)源質(zhì)量的有效手段之一。在數(shù)據(jù)清理過程中，為了減少數(shù)據(jù)源內(nèi)的冗余信息，相似重復(fù)的記錄、檢測和清理成為了關(guān)鍵部分。根據(jù)所記錄的相似性檢測結(jié)果，能夠評(píng)測所傳輸?shù)臄?shù)據(jù)中是否含有重復(fù)記錄[2-3]。為此，有相關(guān)學(xué)者提出了一些關(guān)于傳輸過程數(shù)據(jù)相似性檢測的方法。

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

文獻(xiàn)[5]中提出了一種基于信息熵與模糊綜合評(píng)判融合的相似數(shù)據(jù)檢測方法，首先對(duì)比數(shù)據(jù)內(nèi)每一種字段的相似度，然后對(duì)每一種字段賦予各部相同的權(quán)重，利用信息熵轉(zhuǎn)換傳輸數(shù)據(jù)的損失函數(shù)與非極大值抑制函數(shù)，并簡化網(wǎng)絡(luò)傳輸架構(gòu)，再將轉(zhuǎn)換完成的傳輸數(shù)據(jù)輸送至架構(gòu)內(nèi)進(jìn)行迭代，并與與原始數(shù)據(jù)進(jìn)行對(duì)比，完成傳輸數(shù)據(jù)的相似性檢測。但是該方法需要對(duì)數(shù)據(jù)進(jìn)行反復(fù)的迭代，導(dǎo)致檢測數(shù)據(jù)召回率較高。

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

2 并行多路徑傳輸過程數(shù)據(jù)相似性檢測

2.1 位碼的相似度架構(gòu)

針對(duì)相似性檢測問題，通過位碼代替法來估算傳輸數(shù)據(jù)架構(gòu)之間的相似度，這種方法憑借純粹的架構(gòu)差異[6]與標(biāo)簽序列差異來估算傳輸數(shù)據(jù)架構(gòu)之間的相似度。

首先對(duì)傳輸數(shù)據(jù)的主干信息進(jìn)行提取，其主干架構(gòu)樹如圖1所示。其中，a代表所傳輸?shù)臄?shù)據(jù)集，b類代表數(shù)據(jù)子集，c類代表節(jié)點(diǎn)數(shù)據(jù)，d類代表子節(jié)點(diǎn)數(shù)據(jù)。

圖1 所傳輸數(shù)據(jù)主干架構(gòu)樹結(jié)構(gòu)圖

相似度架構(gòu)流程如下：

1)對(duì)深度優(yōu)先遍歷過程進(jìn)行數(shù)值化操作。在提取傳輸數(shù)據(jù)主干架構(gòu)樹之后，對(duì)其進(jìn)行深度優(yōu)先遍歷，對(duì)通過遍歷的每一種節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量進(jìn)行編碼，將傳輸數(shù)據(jù)主干架構(gòu)表示為數(shù)值序列；

2)統(tǒng)一所有層次內(nèi)最大子節(jié)點(diǎn)的數(shù)量，填充偽代碼。為解決樹內(nèi)節(jié)點(diǎn)數(shù)量不等的問題，擬定一種偽節(jié)點(diǎn)方法：搜索樹內(nèi)每一層節(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)量，將這種最大子節(jié)點(diǎn)數(shù)當(dāng)做每一種節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量，對(duì)不足節(jié)點(diǎn)進(jìn)行補(bǔ)全填充[7]。填充偽碼后的填充樹如圖2所示。

圖2 主干架構(gòu)樹的填充樹結(jié)構(gòu)圖

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

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

利用二進(jìn)制位碼代替主干架構(gòu)樹，順序是：111，110，110，000，110，000，000，100，000；

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

①架構(gòu)相似度數(shù)值估算。對(duì)上述數(shù)值順序進(jìn)行估算或異，憑借統(tǒng)計(jì)XOR結(jié)構(gòu)內(nèi)的數(shù)量就可以獲取填充樹的架構(gòu)差異程度數(shù)值。

②語義相似度數(shù)值估算。語義相似度是利用樹內(nèi)的幾種標(biāo)記來進(jìn)行估算的，憑借深度優(yōu)先遍歷對(duì)樹進(jìn)行偽代碼填充之后，獲取標(biāo)簽的序列，然后按照順序相應(yīng)的找出不同的標(biāo)簽標(biāo)記，然后估算獲取語義相似度數(shù)值。

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

(1)

式中，DSI為傳輸數(shù)據(jù)i與j的架構(gòu)相似度值，DLi，j為傳輸數(shù)據(jù)i與j的語義相似度值，Nmax為樹內(nèi)節(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)量，M為樹的基本單元數(shù)量。

2.2 優(yōu)化編譯

傳輸數(shù)據(jù)的數(shù)據(jù)排版格式只會(huì)干擾到數(shù)據(jù)的可讀性，因此，編譯器會(huì)自動(dòng)的忽略它們，注釋在編譯的預(yù)處理節(jié)點(diǎn)就會(huì)被剔除，因此修改注釋與重新排版產(chǎn)生的噪聲[8]會(huì)變成最容易且最早被剔除的對(duì)象，數(shù)據(jù)內(nèi)的標(biāo)識(shí)標(biāo)記并不會(huì)對(duì)傳輸?shù)倪\(yùn)行效果產(chǎn)生任何干擾，因此能夠忽略編譯后的二進(jìn)制數(shù)據(jù)內(nèi)的標(biāo)識(shí)符號(hào)，那么標(biāo)識(shí)符號(hào)重新命名后存在的噪聲也會(huì)被剔除。

優(yōu)化編譯過程使用控制流分析、依賴分析[9]與數(shù)據(jù)流分析技術(shù)，剔除公共子代表式，已達(dá)到減少估算的強(qiáng)度、優(yōu)化數(shù)據(jù)傳輸中的跳轉(zhuǎn)和循環(huán)的目的。優(yōu)化編譯過程能夠把等價(jià)的程序邏輯代表方式轉(zhuǎn)換成一種統(tǒng)一的形式，需使用代碼冗余、代表式拆分或者等價(jià)控制架構(gòu)轉(zhuǎn)換手段修改數(shù)據(jù)編碼，通過編譯優(yōu)化編譯可使樣本數(shù)據(jù)和初始數(shù)據(jù)生成的目標(biāo)數(shù)據(jù)相同。

在優(yōu)化編譯時(shí)，須通過更換注釋、重新排版、符重、標(biāo)識(shí)重新命名、添加冗余的變量與語句、表達(dá)式的簡易拆解與替換控制節(jié)點(diǎn)來等價(jià)控制架構(gòu)[10]。源數(shù)據(jù)被轉(zhuǎn)換成二進(jìn)制目標(biāo)數(shù)據(jù)后被剔除，但在改變數(shù)據(jù)碼塊和語句順序時(shí)所帶來的噪聲還沒有被剔除，改變語句的順序不僅僅是導(dǎo)致指令順序的轉(zhuǎn)變，導(dǎo)致偏移傳輸?shù)刂钒l(fā)生的轉(zhuǎn)變，因此需要進(jìn)一步過濾噪聲。

2.2.1 反匯編

上述經(jīng)過優(yōu)化編譯過程產(chǎn)生并傳輸存在關(guān)聯(lián)行的二進(jìn)制數(shù)據(jù)，通過反匯編工具把正在傳輸內(nèi)的數(shù)據(jù)段轉(zhuǎn)換成匯編數(shù)據(jù)，剔除和傳輸特征沒有關(guān)聯(lián)的信息。相較于二進(jìn)制指令，匯編代碼更為簡單、便捷，并且每一種匯編指令都存在一定的語義。若運(yùn)行邏輯不同的傳輸程序，其相應(yīng)的反匯編數(shù)據(jù)也一定是不相同的。

2.2.2 過濾噪聲

通過上述處理過程，傳輸數(shù)據(jù)被轉(zhuǎn)換成匯編數(shù)據(jù)，而匯編數(shù)據(jù)內(nèi)的傳輸偏移地址、函數(shù)地址、部分跳轉(zhuǎn)指令與立即數(shù)都需要進(jìn)行特殊的處理。

傳輸偏移地址是較為容易轉(zhuǎn)換的[11]，語句或是變量聲明順序轉(zhuǎn)變能夠?qū)е聰?shù)據(jù)偏移地址出現(xiàn)轉(zhuǎn)變。

函數(shù)地址與偏移地址相同也是一種容易轉(zhuǎn)變的地址。假如轉(zhuǎn)變函數(shù)體的數(shù)據(jù)就能夠?qū)е潞瘮?shù)的地址出現(xiàn)轉(zhuǎn)變。因此，本研究統(tǒng)一利用FUNCTIDN來表示函數(shù)地址，同時(shí)屏蔽掉函數(shù)地址的差異。

立即數(shù)用以表示傳輸數(shù)據(jù)的常量。為了避免常量轉(zhuǎn)換所產(chǎn)生的噪聲干擾，本研究統(tǒng)一利用CONSTANT代替匯編數(shù)據(jù)內(nèi)的立即數(shù)。

2.2.3 決策函數(shù)

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

(2)

相似度Sim滿足Sim(P1，P2)=1，并且Sim(P1，P2)=Sim(P2，P1)。憑借先驗(yàn)知識(shí)，該公式所估算出的結(jié)果比其它常見的關(guān)聯(lián)系數(shù)估算過程有著更好的區(qū)分度。同時(shí)，使用式(2)另外的一種優(yōu)點(diǎn)就是其估算的結(jié)構(gòu)不會(huì)被指令的順序所干擾，從而能夠有效過濾掉數(shù)據(jù)塊或是語句順序轉(zhuǎn)變所帶來的噪聲[12]。

因?yàn)闅w一化流程內(nèi)已經(jīng)基本的過濾了轉(zhuǎn)變所帶來的噪聲，數(shù)據(jù)的相似度往往會(huì)達(dá)到一種比較高的峰值，相似和不相似數(shù)據(jù)之間的相似度會(huì)呈現(xiàn)出較為顯著的差異。

2.2.4 傳輸數(shù)據(jù)的相似性檢測

首先構(gòu)建下三角矩陣，將傳輸數(shù)據(jù)之間的相似度對(duì)比轉(zhuǎn)換為儲(chǔ)存矩陣之間的相似度對(duì)比。

儲(chǔ)存矩陣不僅含有傳輸數(shù)據(jù)的架構(gòu)信息，矩陣的坐標(biāo)還能夠代表數(shù)據(jù)樹的架構(gòu)，同時(shí)也包含了傳輸數(shù)據(jù)的語義信息。矩陣內(nèi)儲(chǔ)存的數(shù)值就是數(shù)據(jù)樹內(nèi)節(jié)點(diǎn)的內(nèi)容信息，內(nèi)容信息代表了傳輸數(shù)據(jù)的語義。因此這種憑借矩陣存儲(chǔ)的傳輸數(shù)據(jù)相似度就是包含語義相似度，同時(shí)還含有架構(gòu)相似度。

儲(chǔ)存矩陣間相似度估算過程如下

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

(3)

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

(4)

式中，變量c為在矩陣內(nèi)同一種坐標(biāo)的相同標(biāo)簽數(shù)，M為填充樹內(nèi)的元素?cái)?shù)量，也就是儲(chǔ)存矩陣內(nèi)的元素?cái)?shù)量。

在此基礎(chǔ)上，將儲(chǔ)存矩陣進(jìn)行轉(zhuǎn)換，將其轉(zhuǎn)換為一種數(shù)值化狀態(tài)，轉(zhuǎn)換過程如式(5)所示

(5)

為便于估算架構(gòu)的相似度，將矩陣按照順序?qū)⑵浔磉_(dá)為向量的形式。通過這個(gè)思路，將傳輸數(shù)據(jù)樹表達(dá)成為n維的向量。由于是通過下三角矩陣的形式進(jìn)行儲(chǔ)存的，因此，矩陣相似度估算最終是依靠向量的相似度估算而得到的。在本文研究中，使用向量的相關(guān)系數(shù)方法對(duì)相似度進(jìn)行估算。向量之間的關(guān)聯(lián)系數(shù)表示傳輸數(shù)據(jù)之間的架構(gòu)相似度，向量間關(guān)聯(lián)系數(shù)計(jì)算過程如下所示

(6)

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

(7)

3 仿真與結(jié)果分析

為驗(yàn)證所提的并行多路徑傳輸過程數(shù)據(jù)相似性檢測方法的應(yīng)用效果，設(shè)計(jì)如下仿真，通過結(jié)果分析驗(yàn)證相似性檢測過程的有效性。

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

實(shí)驗(yàn)指標(biāo)為：①數(shù)據(jù)召回率；②檢測過程損耗；③相似性檢測誤差百分比。為進(jìn)一步保證實(shí)驗(yàn)結(jié)果的可說明性，將文獻(xiàn)[4]中基于MapReduce模型的大數(shù)據(jù)相似重復(fù)記錄檢測方法與文獻(xiàn)[5]中基于信息熵與模糊綜合評(píng)判融合的相似數(shù)據(jù)檢測方法作為對(duì)照組，用以突出本文方法的應(yīng)用性能。

首先測試不同檢測方法的數(shù)據(jù)召回率。在數(shù)據(jù)相似性檢測過程中，檢測結(jié)果的質(zhì)量可從數(shù)據(jù)召回率和檢測精度兩個(gè)角度進(jìn)行評(píng)價(jià)。其中，數(shù)據(jù)召回率和檢測精度成反比。以60min為測試時(shí)間，統(tǒng)計(jì)不同數(shù)據(jù)相似性檢測方法的數(shù)據(jù)召回率，結(jié)果如圖3所示。

圖3 不同方法的檢測數(shù)據(jù)召回率對(duì)比圖

通過圖3能夠得知，隨著檢測時(shí)間的推移，不同方法的檢測數(shù)據(jù)召回率也在不斷變化，文獻(xiàn)[5]方法的最大數(shù)據(jù)召回率為10.7%，文獻(xiàn)[4]方法的最大數(shù)據(jù)召回率為9.1%，而本文方法的最大數(shù)據(jù)召回率為5.2%，且本文方法的數(shù)據(jù)召回率曲線大部分都位于兩種對(duì)比方法的數(shù)據(jù)召回率曲線之下，說明本文方法的檢測數(shù)據(jù)召回率較小。這是因?yàn)楸疚姆椒ㄒ肓藳Q策函數(shù)，而傳統(tǒng)方法是通過估算傳輸數(shù)據(jù)交集開銷，只考慮了數(shù)據(jù)詞頻因素的干擾，降低了抽樣估算的精度，致使召回率較大。

同樣以60min為測試時(shí)間，統(tǒng)計(jì)不同數(shù)據(jù)相似性檢測方法檢測過程的損耗情況，結(jié)果如圖4所示。

圖4 不同方法的檢測過程損耗對(duì)比圖

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

為進(jìn)一步驗(yàn)證本文方法的應(yīng)用性能，計(jì)算不同方法的相似性檢測誤差百分比。測試數(shù)據(jù)集數(shù)量為500組，共進(jìn)行10次測試，計(jì)算其均值，統(tǒng)計(jì)結(jié)果如表1所示。

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

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

4 結(jié)論

為提高網(wǎng)絡(luò)的使用效率與吞吐量，提出一種并行多路徑傳輸過程數(shù)據(jù)相似性檢測方法，通過估算傳輸過程數(shù)據(jù)架構(gòu)相似度、將數(shù)據(jù)轉(zhuǎn)換為數(shù)值化狀態(tài)、利用反匯編過濾匯編數(shù)據(jù)內(nèi)的噪聲、對(duì)比儲(chǔ)存矩陣之間的相似度等過程實(shí)現(xiàn)對(duì)相似數(shù)據(jù)的檢測。文章還通過仿真證明了該方法具有數(shù)據(jù)召回率、檢測損耗和相似性檢測誤差較小的優(yōu)點(diǎn)。

研究還發(fā)現(xiàn)，憑借優(yōu)化編譯過程剔除數(shù)值化后的公共子代表式能夠減少后期檢測估算的強(qiáng)度，有效減少檢測誤差。