基于BWT的文本压缩算法研究.pdf

李欣然 钟俊

摘 要： 电网的智能化使远动信息数据量急剧增大，对硬件设备的存储能力提出了很大的挑战。为缓解硬件设备压力，减少对硬件设备的投资，并且保证解压后能完整还原原始数据，需对报文进行无损压缩。针对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.