基于BWT改進的LZSS算法在報文壓縮中的應用

李欣然 鐘俊

摘 要： 電網的智能化使遠動信息數據量急劇增大，對硬件設備的存儲能力提出了很大的挑戰。為緩解硬件設備壓力，減少對硬件設備的投資，并且保證解壓后能完整還原原始數據，需對報文進行無損壓縮。針對IEC60870?5?104報文規約結構，提出基于BWT改進的LZSS算法，使用BWT變換對字符串進行預處理，再將數據由LZSS算法進行壓縮。實驗仿真結果表明，該改進算法壓縮效率相對于傳統LZSS算法更好，平均壓縮比減少15.58%，平均耗時減少6.949 s，能夠有效減少電力報文數據的存儲空間。

關鍵詞： 數據壓縮； LZSS算法； BWT； 遠動信息規約報文； 智能變電站； 無損壓縮

中圖分類號： TN99?34； TP393.02 文獻標識碼： A 文章編號： 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 引 言

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

無損數據壓縮作為一種減少設備存儲能力的有效方案，在國內外早有研究[3]。文獻[4]分析了LZSS與LZW兩種壓縮算法的優缺點，在改進這兩種算法的前提下，設計了組合LZSS和LZW的壓縮算法；文獻[5]針對WAMS實時數據特點，對原始數據進行初等變換，提出了一種改進的LZW算法；文獻[6]在分析負載均衡和遙感信息服務網格節點中網絡數據傳輸問題的基礎上，提出了一種有效的基于游程編碼和Huffman編碼的數據壓縮方法；文獻[7]針對測井數據的特點，采用改進的預測算法結合壓縮算法對分類的數據進行壓縮。

遠動信息網絡傳輸規約主要采用IEC60870?5?104規約，報文的結構與一般的壓縮數據結構存在差異，不同的壓縮算法對其進行壓縮得到的壓縮效果有很大的不同。因此本文對通用無損壓縮算法進行對比分析，根據IEC60870?5?104報文結構提出一種基于BWT改進的LZSS算法。實驗結果表明，針對IEC60870?5?104報文壓縮，本文提出的改進算法比通用壓縮算法具有更好的壓縮效率，且耗時相對較短，在電力報文壓縮方面有一定的實際應用價值。

1 遠動傳輸規約IEC60870?5?104

傳統的遠動系統規約難以滿足現代智能電網對遠動信息傳輸實時、可靠、快速的要求，為實現遠動信息傳輸格式的標準化和遠動信息的網絡化傳輸，國際電工委員會TC57將IEC60870?5?101規約與TCP/IP網絡協議相結合，制定了變電站RTU與SCADA系統之間的通信規約IEC60870?5?104規約[8]。

IEC60870?5?104規約的應用規約數據單元（APDU）包含應用規約控制信息（APCI）和應用服務數據單元（ASDU），其結構如圖1所示。啟動字符68H定義數據流內的起始點，APDU的長度定義應用規約數據單元主體的長度。

APDU的三種報文格式由控制域的4個八位位組定義，分別為：信息傳輸格式類型（I格式），用于傳輸含有信息體的報文和確認對方I格式的信息報文；計數的監視功能類型（S格式），用于傳輸對站端確認的報文；不計數的控制功能類型（U格式），用于傳輸鏈路控制命令的報文。報文的格式類型主要取決于控制域八位位組1的前兩位。報文傳輸的三種格式結構如圖2所示，圖中CON表示確認，ACT表示生效。

ASDU由數據單元標識符和一個或多個信息對象所組成，數據單元標識符的結構如表1所示。三種報文格式中，只有信息傳輸格式類型的報文包含ASDU。考慮到傳輸層協議為TCP/IP協議，應用層無需對每幀的正確性與完整性進行判斷，因此沒有在APDU設置校驗結束字符。

2 基于BWT改進的LZSS壓縮算法

2.1 LZSS壓縮算法原理

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

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

輸出編碼的結構方面，在LZ77中，輸出編碼由偏移量、匹配長度和匹配短語后的一個字符組成，當出現未匹配的字符時只能使用偏移量為0、匹配長度為0的三元組表示，十分浪費存儲空間；而LZSS采用一個比特作為標志位，標明輸出的是匹配對還是未匹配成功的單字符，減少了額外負擔。LZSS把連續八個單位的標志位組成一個標志字節，按照一個標志字節加八個單位數據的方式輸出。

這兩點改進使得LZSS通常能得到比LZ77更優的壓縮效率，進一步提高了壓縮性能。

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

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

2.2 基于BWT變換的改進算法

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

2.2.1 編碼過程

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

2.2.2 解碼過程

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

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

由上文可知，在IEC60870?5?104報文傳輸過程中，相同報文傳輸格式的數據幀結構相同，使得報文在存儲的過程中出現大量重復且關聯性強的長字符串。

BWT變換雖不能對報文數據進行壓縮，但可以讓重復的字符串相對集中起來，增大報文數據的聚合度，LZSS算法對關聯性越強的數據獲得的壓縮性能越好，通過LZSS算法對經過BWT變換后的數據進行壓縮，壓縮過程中滑動窗口中的匹配長度更長，輸出的壓縮比更低，可獲得更好的壓縮效果。

改進的LZSS算法具體流程圖如圖5所示。

3 實驗仿真與分析

為了驗證改進算法的性能，進行測試實驗。所有測試結果均是在一臺操作系統為Ubuntu 15.10，CPU型號為Intel[?] CoreTM i5@2.53 GHz，內存大小為4 GB的聯想X201下完成的。測試數據選取文件大小為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報文，對其分別進行Huffman編碼、游程編碼、算術編碼、LZSS算法、基于BWT改進的LZSS算法五種方式的壓縮，采用的數據均源于2015年某省電力系統變電站之間的數據通信報文。

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

對壓縮解壓測試結果進行分析后，可以得出如下結論：

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

2） 使用本文提出的基于BWT改進的LZSS算法對報文進行壓縮，壓縮比優于LZSS算法，平均壓縮比減少15.58%。

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

4 結 語

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

參考文獻

[1] 朱永利，黃敏，邸劍.基于廣域網的電力遠動系統的研究[J].中國電機工程學報，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] 孔維棟.智能變電站網絡報文壓縮技術的研究[D].濟南：山東大學，2014.

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

[3] 吳文強.水聲通信數據無損壓縮方法的對比研究[J].現代電子技術，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] 齊文斌，李東平，楊東，等.廣域測量系統數據在線無損壓縮算法[J].電網技術，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] 劉龍歷，薛勇，光潔，等.遙感網格的數據壓縮與任務分配方法研究[J].遙感技術與應用，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] 漢澤西，郭楓，呂飛.測井數據的無損壓縮方法研究[J].現代電子技術，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].計算機應用，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] 鄭翠芳.幾種常用無損數據壓縮算法研究[J].計算機技術與發展，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.