并行多路徑傳輸過(guò)程數(shù)據(jù)相似性檢測(cè)仿真

趙 敏

(西安電子科技大學(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ù)清理過(guò)程中，為了減少數(shù)據(jù)源內(nèi)的冗余信息，相似重復(fù)的記錄、檢測(cè)和清理成為了關(guān)鍵部分。根據(jù)所記錄的相似性檢測(cè)結(jié)果，能夠評(píng)測(cè)所傳輸?shù)臄?shù)據(jù)中是否含有重復(fù)記錄[2-3]。為此，有相關(guān)學(xué)者提出了一些關(guān)于傳輸過(guò)程數(shù)據(jù)相似性檢測(cè)的方法。

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

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

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

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

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

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

首先對(duì)傳輸數(shù)據(jù)的主干信息進(jìn)行提取，其主干架構(gòu)樹(shù)如圖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)樹(shù)結(jié)構(gòu)圖

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

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

2)統(tǒng)一所有層次內(nèi)最大子節(jié)點(diǎn)的數(shù)量，填充偽代碼。為解決樹(shù)內(nèi)節(jié)點(diǎn)數(shù)量不等的問(wèn)題，擬定一種偽節(jié)點(diǎn)方法：搜索樹(shù)內(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]。填充偽碼后的填充樹(shù)如圖2所示。

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

3)對(duì)填充術(shù)進(jìn)行數(shù)值化處理后對(duì)其進(jìn)行二進(jìn)制化。通過(guò)偽節(jié)點(diǎn)填充操作將兩種樹(shù)之間含有的相等節(jié)點(diǎn)數(shù)量相互對(duì)比，其前提是數(shù)據(jù)集層數(shù)與架構(gòu)是相等的。但是填充樹(shù)的架構(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ì)通過(guò)上述過(guò)程簡(jiǎn)化為一下形式：

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

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

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

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

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

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

(1)

式中，DSI為傳輸數(shù)據(jù)i與j的架構(gòu)相似度值，DLi，j為傳輸數(shù)據(jù)i與j的語(yǔ)義相似度值，Nmax為樹(shù)內(nèi)節(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)量，M為樹(shù)的基本單元數(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)化編譯過(guò)程使用控制流分析、依賴分析[9]與數(shù)據(jù)流分析技術(shù)，剔除公共子代表式，已達(dá)到減少估算的強(qiáng)度、優(yōu)化數(shù)據(jù)傳輸中的跳轉(zhuǎn)和循環(huán)的目的。優(yōu)化編譯過(guò)程能夠把等價(jià)的程序邏輯代表方式轉(zhuǎn)換成一種統(tǒng)一的形式，需使用代碼冗余、代表式拆分或者等價(jià)控制架構(gòu)轉(zhuǎn)換手段修改數(shù)據(jù)編碼，通過(guò)編譯優(yōu)化編譯可使樣本數(shù)據(jù)和初始數(shù)據(jù)生成的目標(biāo)數(shù)據(jù)相同。

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

2.2.1 反匯編

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

2.2.2 過(guò)濾噪聲

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

傳輸偏移地址是較為容易轉(zhuǎn)換的[11]，語(yǔ)句或是變量聲明順序轉(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來(lái)表示函數(shù)地址，同時(shí)屏蔽掉函數(shù)地址的差異。

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

2.2.3 決策函數(shù)

源數(shù)據(jù)通過(guò)歸一化處理后能夠反射成匯編指令集合。假設(shè)P1與P2代替兩種待檢測(cè)的數(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é)果比其它常見(jiàn)的關(guān)聯(lián)系數(shù)估算過(guò)程有著更好的區(qū)分度。同時(shí)，使用式(2)另外的一種優(yōu)點(diǎn)就是其估算的結(jié)構(gòu)不會(huì)被指令的順序所干擾，從而能夠有效過(guò)濾掉數(shù)據(jù)塊或是語(yǔ)句順序轉(zhuǎn)變所帶來(lái)的噪聲[12]。

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

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

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

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

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

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

(3)

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

(4)

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

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

(5)

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

(6)

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

(7)

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

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

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

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

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

通過(guò)圖3能夠得知，隨著檢測(cè)時(shí)間的推移，不同方法的檢測(cè)數(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ù)召回率曲線之下，說(shuō)明本文方法的檢測(cè)數(shù)據(jù)召回率較小。這是因?yàn)楸疚姆椒ㄒ肓藳Q策函數(shù)，而傳統(tǒng)方法是通過(guò)估算傳輸數(shù)據(jù)交集開(kāi)銷，只考慮了數(shù)據(jù)詞頻因素的干擾，降低了抽樣估算的精度，致使召回率較大。

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

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

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

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

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

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

4 結(jié)論

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

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