李欣然 鐘俊

摘 要： 電網(wǎng)的智能化使遠(yuǎn)動(dòng)信息數(shù)據(jù)量急劇增大，對(duì)硬件設(shè)備的存儲(chǔ)能力提出了很大的挑戰(zhàn)。為緩解硬件設(shè)備壓力，減少對(duì)硬件設(shè)備的投資，并且保證解壓后能完整還原原始數(shù)據(jù)，需對(duì)報(bào)文進(jìn)行無損壓縮。針對(duì)IEC60870?5?104報(bào)文規(guī)約結(jié)構(gòu)，提出基于BWT改進(jìn)的LZSS算法，使用BWT變換對(duì)字符串進(jìn)行預(yù)處理，再將數(shù)據(jù)由LZSS算法進(jìn)行壓縮。實(shí)驗(yàn)仿真結(jié)果表明，該改進(jìn)算法壓縮效率相對(duì)于傳統(tǒng)LZSS算法更好，平均壓縮比減少15.58%，平均耗時(shí)減少6.949 s，能夠有效減少電力報(bào)文數(shù)據(jù)的存儲(chǔ)空間。

關(guān)鍵詞： 數(shù)據(jù)壓縮； LZSS算法； BWT； 遠(yuǎn)動(dòng)信息規(guī)約報(bào)文； 智能變電站； 無損壓縮

中圖分類號(hào)： TN99?34； TP393.02 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）15?0092?05

Application of modified LZSS algorithm based on BWT in message compression

LI Xinran， ZHONG Jun

（College of Electrical Engineering and Information， Sichuan University， Chengdu 610065， China）

Abstract： The data amount of telecontrol information is increased dramatically with the intelligentization of the power system， a higher challenge for the storage capacity of the hardware equipment is put forward. Therefore， it is necessary to perform lossless compression for the message to alleviate the hardware equipment pressure， reduce the investment in the hardware equipment， and ensure the complete original data restoration after decompression. According to the characteristics of the IEC60870?5?104 protocol， a modified LZSS compression algorithm based on BWT is proposed. The BWT transform is used to preprocess the character string， and then the data is compressed by means of LZSS algorithm. The simulation results show that the compression efficiency of the improved algorithm is better than that of the traditional LZSS algorithm， the average compression ratio of the modified algorithm is reduced by 15.58%， and the average time consumption is reduced by 6.949 s， which can effectively reduce the storage space of the power message data.

Keywords： data compression； LZSS algorithm； BWT； telecontrol information protocol message； smart substation； lossless compression

0 引 言

隨著網(wǎng)絡(luò)化和數(shù)字化技術(shù)在變電站中的革新與發(fā)展，電網(wǎng)中遠(yuǎn)動(dòng)系統(tǒng)的網(wǎng)絡(luò)化傳輸模式使電網(wǎng)運(yùn)行質(zhì)量得到了進(jìn)一步優(yōu)化。變電站與主站間的信息交互涉及一次設(shè)備在線狀態(tài)監(jiān)測信息、生產(chǎn)管理信息、電能計(jì)量信息、輔助應(yīng)用信息等，對(duì)交互信息進(jìn)行記錄分析可有效預(yù)防電力系統(tǒng)事故的發(fā)生[1]。當(dāng)電力系統(tǒng)發(fā)生故障時(shí)，對(duì)已記錄的網(wǎng)絡(luò)報(bào)文進(jìn)行快速解析可有效查找故障原因。然而，電網(wǎng)的智能化使遠(yuǎn)動(dòng)信息數(shù)據(jù)量急劇增大，這對(duì)硬件設(shè)備的存儲(chǔ)能力提出了很大的挑戰(zhàn)，因此為緩解硬件設(shè)備壓力，減少對(duì)硬件設(shè)備的投資，保證壓縮、解壓后數(shù)據(jù)信息無誤，需對(duì)網(wǎng)絡(luò)報(bào)文進(jìn)行無損壓縮[2]。

無損數(shù)據(jù)壓縮作為一種減少設(shè)備存儲(chǔ)能力的有效方案，在國內(nèi)外早有研究[3]。文獻(xiàn)[4]分析了LZSS與LZW兩種壓縮算法的優(yōu)缺點(diǎn)，在改進(jìn)這兩種算法的前提下，設(shè)計(jì)了組合LZSS和LZW的壓縮算法；文獻(xiàn)[5]針對(duì)WAMS實(shí)時(shí)數(shù)據(jù)特點(diǎn)，對(duì)原始數(shù)據(jù)進(jìn)行初等變換，提出了一種改進(jìn)的LZW算法；文獻(xiàn)[6]在分析負(fù)載均衡和遙感信息服務(wù)網(wǎng)格節(jié)點(diǎn)中網(wǎng)絡(luò)數(shù)據(jù)傳輸問題的基礎(chǔ)上，提出了一種有效的基于游程編碼和Huffman編碼的數(shù)據(jù)壓縮方法；文獻(xiàn)[7]針對(duì)測井?dāng)?shù)據(jù)的特點(diǎn)，采用改進(jìn)的預(yù)測算法結(jié)合壓縮算法對(duì)分類的數(shù)據(jù)進(jìn)行壓縮。

遠(yuǎn)動(dòng)信息網(wǎng)絡(luò)傳輸規(guī)約主要采用IEC60870?5?104規(guī)約，報(bào)文的結(jié)構(gòu)與一般的壓縮數(shù)據(jù)結(jié)構(gòu)存在差異，不同的壓縮算法對(duì)其進(jìn)行壓縮得到的壓縮效果有很大的不同。因此本文對(duì)通用無損壓縮算法進(jìn)行對(duì)比分析，根據(jù)IEC60870?5?104報(bào)文結(jié)構(gòu)提出一種基于BWT改進(jìn)的LZSS算法。實(shí)驗(yàn)結(jié)果表明，針對(duì)IEC60870?5?104報(bào)文壓縮，本文提出的改進(jìn)算法比通用壓縮算法具有更好的壓縮效率，且耗時(shí)相對(duì)較短，在電力報(bào)文壓縮方面有一定的實(shí)際應(yīng)用價(jià)值。

1 遠(yuǎn)動(dòng)傳輸規(guī)約IEC60870?5?104

傳統(tǒng)的遠(yuǎn)動(dòng)系統(tǒng)規(guī)約難以滿足現(xiàn)代智能電網(wǎng)對(duì)遠(yuǎn)動(dòng)信息傳輸實(shí)時(shí)、可靠、快速的要求，為實(shí)現(xiàn)遠(yuǎn)動(dòng)信息傳輸格式的標(biāo)準(zhǔn)化和遠(yuǎn)動(dòng)信息的網(wǎng)絡(luò)化傳輸，國際電工委員會(huì)TC57將IEC60870?5?101規(guī)約與TCP/IP網(wǎng)絡(luò)協(xié)議相結(jié)合，制定了變電站RTU與SCADA系統(tǒng)之間的通信規(guī)約IEC60870?5?104規(guī)約[8]。

IEC60870?5?104規(guī)約的應(yīng)用規(guī)約數(shù)據(jù)單元（APDU）包含應(yīng)用規(guī)約控制信息（APCI）和應(yīng)用服務(wù)數(shù)據(jù)單元（ASDU），其結(jié)構(gòu)如圖1所示。啟動(dòng)字符68H定義數(shù)據(jù)流內(nèi)的起始點(diǎn)，APDU的長度定義應(yīng)用規(guī)約數(shù)據(jù)單元主體的長度。

APDU的三種報(bào)文格式由控制域的4個(gè)八位位組定義，分別為：信息傳輸格式類型（I格式），用于傳輸含有信息體的報(bào)文和確認(rèn)對(duì)方I格式的信息報(bào)文；計(jì)數(shù)的監(jiān)視功能類型（S格式），用于傳輸對(duì)站端確認(rèn)的報(bào)文；不計(jì)數(shù)的控制功能類型（U格式），用于傳輸鏈路控制命令的報(bào)文。報(bào)文的格式類型主要取決于控制域八位位組1的前兩位。報(bào)文傳輸?shù)娜N格式結(jié)構(gòu)如圖2所示，圖中CON表示確認(rèn)，ACT表示生效。

ASDU由數(shù)據(jù)單元標(biāo)識(shí)符和一個(gè)或多個(gè)信息對(duì)象所組成，數(shù)據(jù)單元標(biāo)識(shí)符的結(jié)構(gòu)如表1所示。三種報(bào)文格式中，只有信息傳輸格式類型的報(bào)文包含ASDU?？紤]到傳輸層協(xié)議為TCP/IP協(xié)議，應(yīng)用層無需對(duì)每幀的正確性與完整性進(jìn)行判斷，因此沒有在APDU設(shè)置校驗(yàn)結(jié)束字符。

2 基于BWT改進(jìn)的LZSS壓縮算法

2.1 LZSS壓縮算法原理

LZ77算法無需知道數(shù)據(jù)的統(tǒng)計(jì)特性，原理簡單，自提出以來得到了廣泛的運(yùn)用。LZ77的字典是變化的，由最近編碼的一大塊正文組成。LZ77算法引入“滑動(dòng)窗口”概念，在字符串上順序滑動(dòng)，若找到匹配，則輸出三元組替換，從而實(shí)現(xiàn)壓縮功能。

LZSS算法在LZ77的基礎(chǔ)上在窗口匹配模式和輸出編碼結(jié)構(gòu)兩個(gè)方面進(jìn)行變化[9]。窗口匹配模式方面，在LZ77中，搜索緩沖區(qū)的短語以單個(gè)相鄰的方式存儲(chǔ)，沒有更高層的組織，而LZSS將編碼完成后即將移入搜索緩沖區(qū)的短語添加到一個(gè)二叉搜索樹中，通過對(duì)二叉搜索樹中短語的排序，尋找其中最長短語的復(fù)雜度大大降低。

輸出編碼的結(jié)構(gòu)方面，在LZ77中，輸出編碼由偏移量、匹配長度和匹配短語后的一個(gè)字符組成，當(dāng)出現(xiàn)未匹配的字符時(shí)只能使用偏移量為0、匹配長度為0的三元組表示，十分浪費(fèi)存儲(chǔ)空間；而LZSS采用一個(gè)比特作為標(biāo)志位，標(biāo)明輸出的是匹配對(duì)還是未匹配成功的單字符，減少了額外負(fù)擔(dān)。LZSS把連續(xù)八個(gè)單位的標(biāo)志位組成一個(gè)標(biāo)志字節(jié)，按照一個(gè)標(biāo)志字節(jié)加八個(gè)單位數(shù)據(jù)的方式輸出。

這兩點(diǎn)改進(jìn)使得LZSS通常能得到比LZ77更優(yōu)的壓縮效率，進(jìn)一步提高了壓縮性能。

LZSS算法如圖3所示，圖中[L]為最大匹配長度，Min_Length為最小匹配長度，[P]為指向這一最大匹配的指針。

其他無損壓縮算法如算術(shù)編碼雖然壓縮率低，但由于其算法本身復(fù)雜性太高，導(dǎo)致壓縮解壓時(shí)間過長；Huffman編碼的壓縮效率由各字符出現(xiàn)的頻率決定，與文件自身上下文相關(guān)性關(guān)聯(lián)不大，不適用于上下文關(guān)聯(lián)性大的IEC60870?5?104報(bào)文。相比較而言，雖然LZSS算法有其局限性，如對(duì)于較長的文件進(jìn)行壓縮時(shí)會(huì)因建立二叉樹過于龐大而會(huì)影響編碼時(shí)間等[10]，但LZSS壓縮效率較高，編譯算法較簡單，有著良好的壓縮效果，所以本文選擇LZSS算法作為IEC60870?5?104報(bào)文壓縮的基本算法，并對(duì)其進(jìn)行改進(jìn)。

2.2 基于BWT變換的改進(jìn)算法

BWT變換[11]是一種用于無損數(shù)據(jù)壓縮的可逆數(shù)據(jù)變換方法，它本身不會(huì)對(duì)數(shù)據(jù)進(jìn)行壓縮，但經(jīng)BWT變換后的某些數(shù)據(jù)會(huì)聚合在一起，后續(xù)采用壓縮算法處理數(shù)據(jù)可以得到更好的壓縮效果。下面用一實(shí)例闡明BWT變換的基本原理。

2.2.1 編碼過程

在編碼的過程中，對(duì)于長度為[N=7]的字符串[S="AFAQMMZ"]，將其循環(huán)左移[N]次操作得到[N×N]的原始輪轉(zhuǎn)矩陣[P]，將矩陣[P]由字典方式從小到大進(jìn)行排序得到有序輪轉(zhuǎn)矩陣[Q]。選取矩陣[Q]的最后一列[L]及第一次移位后的S1在[Q]中的位置序號(hào)[I]。在以上步驟后，正變換后輸出結(jié)果為[L="ZFAQMAM"]，[I=2]。本例中的原始輪轉(zhuǎn)矩陣[P]與有序輪轉(zhuǎn)矩陣[Q]見表2。

2.2.2 解碼過程

已知結(jié)果[L="ZFAQMAM"]，[I=2]，可以通過一定的策略得到原始的輸入串[S]，方法如下：將[L]內(nèi)字符進(jìn)行順序排序得到[F]，根據(jù)輪轉(zhuǎn)矩陣的生成過程可知，[L]中的每個(gè)字符是從[F]列的同一行開始的字符串的前綴字符，且[L]中的所有字符串在[F]中以相同的順序出現(xiàn)，但不一定在同一行中。現(xiàn)假設(shè)轉(zhuǎn)換變量[T]，[i]為字母在[L]中的位置，[j]為字母在[F]中的位置，則轉(zhuǎn)換變量[T]滿足[T[j]=i]，其映射關(guān)系如表3所示。由表3可知，[T={2，5，1，4，6，3，0}]。

根據(jù)[L="ZFAQMAM"]，[I=2]，[T={2，5，1，4，6，3，0}]，可還原出原始序列[S]，具體解碼流程如圖4所示。

由上文可知，在IEC60870?5?104報(bào)文傳輸過程中，相同報(bào)文傳輸格式的數(shù)據(jù)幀結(jié)構(gòu)相同，使得報(bào)文在存儲(chǔ)的過程中出現(xiàn)大量重復(fù)且關(guān)聯(lián)性強(qiáng)的長字符串。

BWT變換雖不能對(duì)報(bào)文數(shù)據(jù)進(jìn)行壓縮，但可以讓重復(fù)的字符串相對(duì)集中起來，增大報(bào)文數(shù)據(jù)的聚合度，LZSS算法對(duì)關(guān)聯(lián)性越強(qiáng)的數(shù)據(jù)獲得的壓縮性能越好，通過LZSS算法對(duì)經(jīng)過BWT變換后的數(shù)據(jù)進(jìn)行壓縮，壓縮過程中滑動(dòng)窗口中的匹配長度更長，輸出的壓縮比更低，可獲得更好的壓縮效果。

改進(jìn)的LZSS算法具體流程圖如圖5所示。

3 實(shí)驗(yàn)仿真與分析

為了驗(yàn)證改進(jìn)算法的性能，進(jìn)行測試實(shí)驗(yàn)。所有測試結(jié)果均是在一臺(tái)操作系統(tǒng)為Ubuntu 15.10，CPU型號(hào)為Intel[?] CoreTM i5@2.53 GHz，內(nèi)存大小為4 GB的聯(lián)想X201下完成的。測試數(shù)據(jù)選取文件大小為185 KB，312 KB，782 KB，1 524 KB，2 096 KB，3 696 KB，5 198 KB，6 094 KB，8 701 KB的IEC60870?5?104報(bào)文，對(duì)其分別進(jìn)行Huffman編碼、游程編碼、算術(shù)編碼、LZSS算法、基于BWT改進(jìn)的LZSS算法五種方式的壓縮，采用的數(shù)據(jù)均源于2015年某省電力系統(tǒng)變電站之間的數(shù)據(jù)通信報(bào)文。

對(duì)五種壓縮算法進(jìn)行測試后，各算法的壓縮比如圖6所示，各算法的壓縮耗時(shí)、解壓耗時(shí)、總耗時(shí)如圖7～圖9所示，其中壓縮比是壓縮后的文件大小占原文件大小的百分比，耗時(shí)單位為s。

對(duì)壓縮解壓測試結(jié)果進(jìn)行分析后，可以得出如下結(jié)論：

1） Huffman編碼、游程編碼與算術(shù)編碼雖然耗時(shí)較小，但因未考慮字符間的聯(lián)合概率等原因，壓縮比效果不理想；相較于此三者，采用LZSS算法的壓縮效果更好，壓縮比大幅減少，證明了本文選擇LZSS算法進(jìn)行改進(jìn)的合理性。

2） 使用本文提出的基于BWT改進(jìn)的LZSS算法對(duì)報(bào)文進(jìn)行壓縮，壓縮比優(yōu)于LZSS算法，平均壓縮比減少15.58%。

3） 五種算法解壓耗時(shí)都相對(duì)較小，故總耗時(shí)取決于壓縮耗時(shí)。本文改進(jìn)算法壓縮耗時(shí)小于LZSS算法，平均壓縮耗時(shí)減少7.476 s，總耗時(shí)減少6.949 s。隨著文件大小的增加，LZSS算法的壓縮耗時(shí)由于其二叉樹建立過于龐大導(dǎo)致壓縮時(shí)間急劇增大，而本文改進(jìn)算法的壓縮耗時(shí)增幅較小，這對(duì)較大文件的壓縮可以取得更理想的效果。

4 結(jié) 語

本文綜合考慮了各種通用壓縮算法對(duì)IEC60870?5?104報(bào)文壓縮后的壓縮比以及壓縮解壓耗時(shí)，選擇LZSS算法進(jìn)行改進(jìn)，結(jié)果表明，該改進(jìn)算法壓縮效率好，相對(duì)于傳統(tǒng)LZSS算法平均壓縮比減少15.58%，且壓縮耗時(shí)小于傳統(tǒng)LZSS算法，平均壓縮解壓耗時(shí)減少6.949 s，在電力報(bào)文壓縮方面具有一定的實(shí)際應(yīng)用價(jià)值。

參考文獻(xiàn)

[1] 朱永利，黃敏，邸劍.基于廣域網(wǎng)的電力遠(yuǎn)動(dòng)系統(tǒng)的研究[J].中國電機(jī)工程學(xué)報(bào)，2005（7）：119?124.

ZHU Yongli， HUANG Min， DI Jian. The study on wan?based telecontrol system for power system [J]. Proceedings of the CSEE， 2005（7）： 119?124.

[2] 孔維棟.智能變電站網(wǎng)絡(luò)報(bào)文壓縮技術(shù)的研究[D].濟(jì)南：山東大學(xué)，2014.

KONG Weidong. Research on compression technology for network packets of the smart substation [D]. Jinan： Shandong University， 2014.

[3] 吳文強(qiáng).水聲通信數(shù)據(jù)無損壓縮方法的對(duì)比研究[J].現(xiàn)代電子技術(shù)，2012，35（9）：103?105.

WU Wenqiang. Research of lossless compression algorithms for acoustic communication data [J]. Modern electronics technique， 2012， 35（9）： 103?105.

[4] YUAN J. The combinational application of LZSS and LZW algorithms for compression based on Huffman [C]// 2011 IEEE International Conference on Electronics and Optoelectronics. Dalian： IEEE， 2011： 397?399.

[5] 齊文斌，李東平，楊東，等.廣域測量系統(tǒng)數(shù)據(jù)在線無損壓縮算法[J].電網(wǎng)技術(shù)，2008，32（8）：86?90.

QI Wenbin， LI Dongping， YANG Dong， et al. Online lossless compression algorithm of WAMS data [J]. Power system techno?logy， 2008， 32（8）： 86?90.

[6] 劉龍歷，薛勇，光潔，等.遙感網(wǎng)格的數(shù)據(jù)壓縮與任務(wù)分配方法研究[J].遙感技術(shù)與應(yīng)用，2016，31（2）：247?254.

LIU Longli， XUE Yong， GUANG Jie， et al. Remote sensing information service grid node and the research of data compression and task allocation [J]. Remote sensing technology and application， 2016， 31（2）： 247?254.

[7] 漢澤西，郭楓，呂飛.測井?dāng)?shù)據(jù)的無損壓縮方法研究[J].現(xiàn)代電子技術(shù)，2004，27（22）：94?96.

HAN Zexi， GUO Feng， L? Fei. Research of lossless data compression method about logging data [J]. Modern electronics technique， 2004， 27（22）： 94?96.

[8] Power Electrical Engineering Standards Policy Committee. Telecon?trol equipment and systems， Part 5： transmission protocols?section 102： companion standard for the transmission of integrated totals in electric power systems [S]. British： Power Electrical Engineering Standards Policy Committee， 1994.

[9] 何丹，李志蜀.一種基于LZSS的文本文件壓縮算法[J].計(jì)算機(jī)應(yīng)用，2008，28（9）：2335?2337.

HE Dan， LI Zhishu. Compression algorithm of text files based on LZSS [J]. Computer applications， 2008， 28（9）： 2335?2337.

[10] 鄭翠芳.幾種常用無損數(shù)據(jù)壓縮算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（9）：73?76.

ZHENG Cuifang. Research of several common lossless data compression algorithms [J]. Computer technology and development， 2011， 21（9）： 73?76.

[11] BURROWS M. A block?sorting lossless data compression algorithm [J]. Technical report digital SRC research report， 1994， 57（4）： 425.