程 飛,劉 凱,丁文文,時 歡,張百戩

(西安電子科技大學計算機學院,陜西西安 710071)

測量報告數據的譜分析壓縮算法

程 飛,劉 凱,丁文文,時 歡,張百戩

(西安電子科技大學計算機學院,陜西西安 710071)

針對網絡帶寬難以滿足海量測量報告?zhèn)鬏斠?定義了測量數據的譜,并提出了測量報告數據的譜分析壓縮算法.該算法通過分析測量數據的譜,提出了對數據完成兩次排序的預處理方案,減少了數據冗余的間隔距離,以期提高上下文的命中率.其次,該壓縮算法構建了測量數據的多個上下文模型,并作為單層神經網絡的輸入結點.神經網絡通過對每個上下文模型的預測概率線性組合,得到對下一比特的預測概率,并用真實的下一比特來調整對應輸入結點的權重,提高匹配歷史信息的概率.實驗結果表明,在采用該壓縮算法后,算法的運行時間明顯減小,壓縮率隨被壓縮數據量的增大而提高.與其他通用壓縮算法相比,該算法能有效提高測量數據的壓縮率,從而達到減少網絡數據傳輸量的目的.

測量報告;數據壓縮;譜分析;神經網絡

移動運營商需要對正式投入運行的通信網絡進行數據采集和分析工作[1],以洞悉通信狀態(tài)的動態(tài)變化.其主要收集用戶終端發(fā)出的測量報告(Measure Report,MR),獲知所轄的移動網絡狀態(tài).測量報告包含接入電平門限、切換電平門限、話務密度等性能參數,并且記錄移動通信網絡的配置.測量報告數據采集過程如圖1所示,處在某蜂窩網中的用戶終端隨時會與基站保持通信,將測量報告通過基站和基站控制器傳輸并保存到數據采集服務器上.數據采集服務器周期性將數據遠程傳輸到數據中心,以便于全面地了解網絡的運行狀況,及時地發(fā)現網絡故障,并針對問題給出解決方案.隨著終端用戶增加,MR數據量出現大幅度的增長.數據采集服務器與數據中心之間的帶寬有限,難以適應測量數據的海量傳輸.為減少數據傳輸量,需要對MR數據進行壓縮處理.

現有的文本壓縮算法主要是針對常規(guī)文本數據的壓縮過程[2-7].如文獻[2]使用字典編碼的機制,用偏移加長度的方式表示重復出現的字符串,結合哈夫曼編碼和Deflate來壓縮文本數據.文獻[3-4]提出基于上下文模型的預測的自適應性的統(tǒng)計數據壓縮技術,該系列算法將不同階的上下文模型混合預測輸入序列的下個字符.文獻[6]中的壓縮算法思想與局部匹配預測(Prediction by Partial Matching,PPM)類似,與其不同的是,其利用多層神經網絡將上下文模型混合,得到下個字符的預測概率.文獻[7]提出用伯羅斯惠勒變換(Burrows-Wheeler Transform,BWT)將重復性的字符序列轉換為同樣字母組成的字符串,再利用前向移動技術和哈夫曼編碼處理文本.

圖1　測量報告數據采集示意圖

與其他文本[8]和圖像[9-11]壓縮問題不同,測量數據是一種特殊的文本數據.測量數據中冗余信息的間隔距離對這些算法提出了挑戰(zhàn).距離間隔是冗余信息在原始數據的偏移量的差值,表現為冗余信息之間其他字段所占用的字節(jié)數.由于MR數據是由多個MR報文順序組成的,冗余信息的間隔距離分為報文間距和字段間距兩種情況,報文間距為數據冗余多的報文之間存在多個報文;相鄰報文的同一字段之間存在其他字段,這些字段形成了字段間距.當冗余信息的間隔距離過長時,常規(guī)壓縮算法無法在有限的上下文模型的范圍內查找成功,信息的數據編碼變長,導致數據壓縮效果不明顯.

筆者提出了一種基于譜分析的MR數據壓縮算法,該算法定義了MR的譜,同時根據譜分析的結果對MR數據采取兩次排序的預處理方案.該預處理過程分為多關鍵字歸并排序與合并字段排序兩個步驟.多關鍵字歸并排序提出對MR聯合TRXID和MXID字段聯合排序,提高相鄰報文的相似性,減少報文間距.在聯合字段排序的基礎上合并字段排序,減少字段間距.其次,壓縮算法采用神經網絡模型,筆者提出了建立適合MR數據的上下文模型,每個上下文模型均輸出上下文預測概率,將這些概率預測混合得到下個字符的預測概率,并將混合的預測概率代入算術編碼器進行字符編碼.

1　MR 數據壓縮算法

1.1MR譜分析

數據收集服務器收集每個終端的MR報文發(fā)送給數據分析中心.若終端在某時間段內的某些通信特征不發(fā)生明顯變化,該段時間的MR數據在時間上存在冗余,則稱為時間相關性.若某個蜂窩網中的終端數目可達到一定的密度,所監(jiān)測的信號范圍相互交疊,則稱為空間相關性.時空相關性[12]是MR存在數據冗余的原因,然而由于各個基站通信狀態(tài)和數據收集時間是相互獨立的,MR報文到達數據收集服務器時間也是相互獨立的,MR文件中的報文次序是隨機排列的.因此,存在含有冗余信息的報文在MR文件存儲順序是非相鄰的情況.為提高MR數據的壓縮率,可結合MR數據時空相關性調整報文的順序,減小冗余信息的間隔距離.MR報文包含若干字段,選取何種字段作為調整MR文件中報文次序的依據成為難題.假設從某個特定的時刻開始采集數據,直到另一個固定時刻為止,獲得MR數據表示成矩陣形式為

其中,Xk=(xk1,xk2,…,xkm)T,(k∈N,N={1,2,…,n})是MR數據中第k個報文;xkj(k∈N,j={1,2,…,m})是第k個報文的第j字段,m為MR報文中字段總數.矩陣Y的每行表示1個報文,每個列表示某個數據字段.向量Xk與Xj的歐式距離Sk,j表示報文Xk與Xj的相似性,Sk,j的數值越小,報文Xk與Xj相似性越大,則報文之間存在冗余信息的概率越大.MR數據是以報文為單位順序存儲的,選取不同的字段排序后,相鄰報文的相似性會發(fā)生改變.相鄰的報文相似性越大,MR數據中冗余距離減小的可能性就越大.為此,筆者提出了MR數據的譜dY的定義.dY是指為所有相鄰報文相似性的均值,可表示為

其中,Si,i+1表示第i個報文和第i+1個報文的相似性,譜的值越小,冗余數據的間隔距離就越小.矩陣Y按照m個字段分別排序后的譜均有變化,按第k個字段排序的MR譜記為dY(k).若能夠找到min dY(k),就能夠最大程度地減少數據冗余的距離.

以MR數據為實驗對象.該數據由360 096個MR報文構成,按其所含59個不同字段分別調整報文順序,計算得到的排序后的MR譜dY(k),如圖2所示.圖2中,橫坐標表示MR報文的所有字段,縱坐標表示MR數據按某字段排序后的譜dY(k),水平虛線是表明為未進行字段排序的MR初始的譜dY(0),可作為排序后對比的基準.由圖2可知,按MXID排序的譜最小,TRXID排序次之.因此,MXID排序后,相鄰報文的冗余信息較大,或者說冗余信息的間隔距離較小.字段MXID表示基站號,字段TRXID表示載頻號.在同一個基站的范圍內的用戶終端,MR數據中的基站號相同,具有空間相關性;一個基站內不同用戶設備(User Equipment,UE)被分配的載頻號不同,MXID和TRXID相同的報文表示同一UE的MR消息,具有時空相關性.以上按不同字段排序后的MR相關性的分析方法,稱為譜分析.

圖2　MR數據的譜分析

1.2多歸并排序

依據MR譜分析,可對MR報文按MXID和TRXID多歸并排序.多communications Measure Report,GSM-MR)數據格式中,MXID和TRXID是相鄰字段,MXID字段位數是4 B,TRXID字段位數是2 B.將MXID和TRXID映射到一個64 bit的無符號整型數據中,高16 bit用0填充.在多字段排序中,依據每個報文中MXID和TRXID對應的64位無符號整型為主鍵,將多

歸并排序變?yōu)橐淮螝w并排序,最好情況和最壞情況的時間復雜度都為n log(n).從矩陣角度來看,多

歸并排序就是根據列的數值重新排矩陣Y的行序列.

按照相關度大小選擇排序多個字段,第1個排序主字段為MXID,第2個排序主字段為TRXID.首先,依據MXID的值對MR數據進行歸并排序,改變數據的初始順序;當MXID的數值相等時,依照TRXID再進行歸并排序.一次歸并排序的最好情況和最壞情況的時間復雜度均為n log n.多

分別排序是兩次歸并,時間消耗較大,時間復雜度是n log n≤T(n)≤2n log n.在全球移動通信系統(tǒng)測量報告(Global System for Mobile

1.3合并字段排序

多歸并排序后,相同字段間還存在字段間距,這會影響概率預測準確度.多T,其中,歸并處理文件對應的矩陣(Y′)T,即對n×m矩陣Y′按列排序生成m×n矩陣(Y′)T.

歸并排序后的MR數據稱為MR歸并數據,記為Y′.將MR歸并數據中所有報文的同字段依次順序排列,減少字段間距.具體地說,將所有報文的第1個字段順序排列,接著將第2個字段順序排列,以此類推.對于矩陣將第1列代表的字段作為整體,接著把第2列代表的字段排在第1列的后面,即對矩陣Y′進行轉置變換(Y′)

1.4基于神經網絡的多上下文編碼

將MR的各字段擴展為整字節(jié)的數據字段,筆者對此提出建立4類上下文模型,分別為半字節(jié)上下文模型、整字節(jié)上下文模型、雙字節(jié)上下文模型以及四字節(jié)上下文模型.其中,每個上下文模型通過匹配輸入比特得到的預測概率為Pi,i=1,2,…,4;4個上下文模型的預測概率Pi通過單層神經網絡加權線性混合后得到的輸出預測概率為P.輸入Pi,神經網絡的輸入結點可表示為

神經網絡的預測概率P可表示為

其中,y是輸入的下一比特;y-P是預測誤差;γ為學習率,其取值不宜過大,取值為0.002.P作為算術編碼器編碼的依據,設字符s出現的概率為P(s),那么為該字符分配一個在Q和Q+P(s)之間的數作為編碼,其中Q為所有在字符s之前出現的概率之和.基于神經網絡的多上下文編碼該過程被記為XDMRC(XDMR Coding).綜合形成的MR壓縮算法步驟如下:

(1)對輸入的MR進行譜分析,按照TRXID和MXID進行多歸并排序,減少報文間距.

(2)對歸并排序后的MR進行合并字段排序,減少字段間距.

(3)4個上下文模型匹配已輸入字段,輸出每個模型的預測概率Pi,利用式(3)和式(4)得到神經網絡的預測概率P,將P送入算術編碼器編碼.

(4)利用式(5)將讀入的下一比特y來調整神經網絡中每個輸入結點的權重wi.

2　實驗結果及分析

筆者采取3組實驗來說明所提出的XDMR壓縮算法的有效性.XDMR壓縮算法采用C語言編寫,實驗測試環(huán)境的機器配置為3.0 GHz主頻的Intel Core i5-2320中央處理器,4 GB內存計算機,預裝Windows 7 64位旗艦版操作系統(tǒng).其中,XDMR壓縮算法分為MR預處理和多上下文模型的算術編碼過程,簡記為Pre和XDMRC.

實驗1 測試預處理對MR數據壓縮效果的影響.實驗采用PPMd、PAQ8L、XDMRC、GZIP、LZMA和PPMd+pre、PAQ8L+pre、XDMRC+pre、GZIP+pre、LZMA+pre對3組原始的MR數據平均壓縮情況、預處理前后的壓縮率和相對壓縮率RC進行對比.RC=(Sorigi-Spre)/Spre,其定義了相對壓縮率MR數據平均壓縮情況,表示壓縮算法采用預處理相比未采用預處理壓縮效果的相對提升程度,Sorigin表示對未經預處理MR壓縮后的文件大小,Spre表示對預處理的MR壓縮后的文件大小.如圖3所示,左斜線柱和右斜線柱分別表明未經預處理的壓縮算法和預處理的壓縮算法針對3組MR數據的平均壓縮率.在未經預處理的壓縮算法中,PAQ8L和XDMR對MR壓縮效果較明顯,平均壓縮率分別為18.27%和24.51%,RAR壓縮效果最差,平均數據壓縮率為37.56%.對采用預處理的壓縮算法中,PAQ8L+pre和XDMRC+pre算法的數據壓縮效果相對較好,平均數據壓縮率是13.09%和14.59%,bzip2+pre和RAR+pre算法的數據壓縮相對較差,平均數據壓縮率是20.97%和19.99%.未加預處理和結合預處理的壓縮算法對MR數據壓縮率的變化,表明所列的壓縮算法結合文中所提出的預處理方法能夠有效提升MR數據壓縮率.交叉線柱圖是對比兩種方式的相對壓縮率,表明預處理過程對MR數據壓縮提升效果的量化數據.各壓縮算法采用預處理對MR數據的相對壓縮率在28.38%～46.84%之間,提升效果明顯.

圖3　預處理方法對MR數據壓縮效果

實驗2 測試對比預處理方法和未采用預處理方法以及MR文件大小與壓縮率的變化關系.實驗2與實驗3均是壓縮大小為5 MB、10 MB、15 MB、20 MB的12個MR數據,每組有3個MR文件,壓縮率是每組平均壓縮率.如圖4所示,無預處理的壓縮算法對MR數據的壓縮率隨文件大小變化的曲線是基本上平行橫坐標的直線,可認為壓縮率是恒定的數值.這說明無預處理的壓縮算法,壓縮率與文件大小的關系是恒定不變的.與此不同的是,從采用預處理的壓縮算法對MR的壓縮率與MR大小的變化曲線可以看出,MR數據的壓縮率隨MR文件的增大而變小.例如,PPMd+pre在4類大小不同數據的平均壓縮率取值分別是20.78%、19.65%、19.29%、19.09%,其中,5 MB大小的數據文件壓縮率最高,20 MB大小的數據文件壓縮率最低.壓縮率的降低原因是MR文件越大,存在冗余的報文可能性越增多.因此,采用預處理的壓縮算法的特點之一是MR數據的壓縮率隨文件大小緩慢降低,這也是未采用預處理的壓縮算法所不具備的特點.

圖4　預處理方法和未采用預處理方法數據大小與壓縮率的變化關系

實驗3 對比未采用預處理與采用預處理的壓縮算法消耗的壓縮時間.如圖5所示,PAQ8L和PAQ8L +pre消耗的壓縮時間是未采用預處理和采用預處理的壓縮算法中耗時最長的,所有的壓縮算法的壓縮耗時,都隨文件增大而增大.圖5表明采用預處理壓縮算法比未采用預處理的壓縮算法對于同樣大小的MR文件的壓縮耗時少,采用預處理的壓縮算法減少了冗余信息的距離,而且減少了冗余信息的匹配次數,因此,采用預處理的壓縮算法的消耗的壓縮時間少于未采用預處理過程的壓縮算法.從3組實驗可知,XDMR是較為理想的測量報告壓縮算法.

3　結束語

筆者提出了基于譜分析的測量報告壓縮算法.該算法提出了MR數據譜分析的方法,并利用分析結果對MR數據進行兩次排序,再利用神經網絡對測量報告建立上下文.實驗結果表明,在采用壓縮算法后,壓縮時間明顯減小,壓縮率隨被壓縮數據的增大而減小,對測量報告的壓縮效果結果明顯.

圖5　未采用預處理與采用預處理的壓縮算法消耗的壓縮時間

[1]AL R Y,KARMOUCH A.QoS-Based Composition of Service Specific Overlay Networks[J].IEEE Transactions on Computers,2015,64(3):832-846.

[2]ZIV J,LEMPEL A.A Universal Algorithm for Sequential Data Compression[J].IEEE Transactions on Information Theory,1977,23(3):337-343.

[3]CLEARY J G,WITTEN I H.Data Compression Using Adaptive Coding and Partial String Matching[J].IEEE Transactions on Communications,1984,32(4):396-402.

[4]SHKARIN D.PPM:One Step to Practicality[C]//Data Compression Conference Proceedings:2002.Piscataway: IEEE,2002:202-211.

[5]STEINRUECKEN C,GHAHRAMANI Z,MACKAY D.Improving PPM with Dynamic Parameter Updates[C]//Data Compression Conference Proceedings:2015.Piscataway:IEEE,2015:193-202.

[6]MAHONEY M.Adaptive Weighing of Context Models for Lossless Data Compression[R].Melbourne:Florida Institute of Technology,2005.

[7]SEWARD J.On the Performance of BWT Sorting Algorithms[C]//Data Compression Conference Proceedings:2000. Piscataway:IEEE,2000:173-182.

[8]BRISABOA N R,CERDEIRA-PENA A,NAVARRO G.XXS:Efficient XPath Evaluation on Compressed XML Documents [J].ACM Transactions on Information Systems,2014,32(3):13.

[9]劉凱,李云松,郭杰.高性能EBCOT編碼加速算法及其實現結構[J].西安電子科技大學學報,2010,37(4): 587-593. LIU Kai,LI Yunsong,GUO Jie.High Performance EBCOT Algorithm and VLSI Architecture[J].Journal of Xidian University,2010,37(4):587-593.

[10]STRUTZ T.Adaptive Context Formation for Linear Prediction of Image Data[C]//IEEE International Conference on Image Processing.Piscataway:IEEE,2014:5631-5635.

[11]STRUTZ T.Entropy Based Merging of Context Models for Efficient Arithmetic Coding[C]//IEEE International Conference on Acoustics,Speech and Signal Processing.Piscataway:IEEE,2014:1991-1995.

[12]ACETO G,BOTTA A,PESCAPéA,et al.Efficient Storage and Processing of High-volume Network Monitoring Data [J].IEEE Transactions on Network and Service Management,2013,10(2):162-175.

(編輯:齊淑娟)

Spectrum analysis compression algorithm of measure report data

CHENG Fei,LIU Kai,DING Wenwen,SHI Huan,ZHANG Baijian
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

To solve to the problem that with the increment of the number of mobile users,the network bandwidth cannot meet the mass transfer of the measure report.This paper defines the conception of the spectrum of the measure report and proposes a spectrum analysis compression algorithm for the measure report.The algorithm utilizes two step sorting in order to reduce the distance between similar contents according to the analysis of the spectrum of measure report data.Furthermore,this algorithm employs several context models,which are regarded as the input nodes of the neural network.The prediction probability is calculated by the linear combination of the probability of each context model,and the weight in each link is tuned by the next bit in order to increase the possibility of matching.Experimental results reveal that the algorithm not only decreases the compression consuming time,but also ascends the compression ratio with the increment of the size of compression data.Compared with other competitors,this algorithm can effectively increase the compression ratio of the measure report to gain a better transfer time.

measure report;data compression;spectrum analysis;neural network

TP391

A

1001-2400(2016)04-0178-06

10.3969/j.issn.1001-2400.2016.04.031

2015-10-19

國家自然科學基金資助項目(61571345,61550110247);中央高?；究蒲袠I(yè)務費專項資金資助項目(BDY191420);安徽省高等學校自然科學研究資助項目(KJ2014B14)

程 飛(1985-),男,西安電子科技大學博士研究生,E-mail:chengfei8582@163.com.