一种支持嵌入式标校系统的数据压缩算法*

刘爱东 李知宇 王 丰 贺林波

（1.海军航空工程学院201教研室 烟台 264001）（2.海军航空工程学院研究生管理大队 烟台 264001）（3.海军航空工程学院训练部数字化校园办公室 烟台 264001）

1 引言

在着舰引导系统的标校方式中，无人机标校作为一种安全有效的方式得到广泛应用。基于无人机的嵌入式标校系统具有功耗低、合作目标一体化的优点具有广泛的应用前景［1～3］。

嵌入式标校系统在完成校飞功能时需采集大量的数据，包括GPS原始测量数据、NMEA0183格式数据［4～5］，姿态传感器数据等。标校系统实时性高，需在系统分配的时间片内完成数据的采集压缩存储功能。因此，压缩算法需要时间复杂度低与空间开销低。因此需要针对标校系统采集的数据进行分析，采用一种适合嵌入式标校系统的算法来压缩数据。

2 LZ77算法基本原理与游程编码思想

LZ77与游程编码作为无损压缩算法中的经典压缩算法在各种压缩软件中一直得到广泛应用。

2.1 LZ77算法

LZ77 算法［6～8］是无损压缩算法，由以色列人Abraham Lempel于1977年提出，核心思想是利用数据的重复结构压缩数据，是典型基于字典的压缩算法。数据压缩时，将从待压缩数据中读入的源数据与字典中的数据项进行匹配，从中找出待压缩数据与字典中的数据最长匹配长度。

算法用到的结构数据主要有：待编码区（等待编码的区域），搜索缓冲区（已经编码区域），滑动窗口（搜索缓冲区+待编码区，定义border为二者的边界）。

输出结果为（p，l，c）

p为待编码区匹配字典数据最大匹配长度的字符串在字典中开始出现的位置；

l为最长匹配；

c为待编码区被匹配位置下一个字符串。

LZ77算法的执行流程主要有：

Step 1：从搜索缓冲区字典中寻找与待编码数据的最长匹配字符串，如果找到执行step 2，否则执行step 3。

Step 2：输出结构为（off，len，c）数据，off为字典中匹配字符串位置相对于border的偏移量，len为最长匹配字符串的长度。然后将窗口向后滑动len+1个字符，继续步骤1。

Step 3：输出结构为（0，0，c）数据，c为待编码区被匹配位置下一个字符串，窗口后移1个单位长度。继续步骤1。

2.2 游程编码

游程编码是无损压缩编码，其基本原理是用符号值或者串长代替连续相同值的数据，即对连续相同 数 据 进 行 编 码 的 过 程［9～11］。 例 如 ，数 据aaaaabbbbbbb可编码为a5b7，当压缩数据中出现大量连续相同数据情况，采用游程编码，有很好的压缩效果。

2.3 经典压缩算法在嵌入式标校系统应用情况分析

采用基于无人机的嵌入式标校系统对着舰引导系统进行标校时，系统的真值测量模块即GPS模块每秒接收GPS原始测量数据、NMEA0183格式数据，同时系统还需基于着舰引导系统标校规定的频率在ARM处理器分配的的时间片内完成姿态传感器的数据采集压缩存储功能。嵌入式的标校系统实时性高、存储空间有限、处理器任务繁重，需要压缩算法必须时间复杂度低［12～13］，且压缩过程中空间开销小。LZ77算法在压缩过程中需不断匹配待编码数据与搜索缓冲区的最长匹配字符串，算法复杂度较高。游程编码适合待压缩的数据中有大量连续重复数据的情况，否则效果不佳。

3 算法设计

3.1 数据分析

本文预先采集大量GPS原始测量数据、NMEA0183格式数据和实验中使用姿态传感器的数据进行分析，得出：标校系统中数据具有连续大量重复数据的情况只在局部数据出现，这段数据使用游程编码算法来压缩的效率最高，某些特定的数据结构重复读较高适合使用LZ77算法来压缩数据，但需改进算法以降低算法复杂度［14～15］，这些特定的数据结构以连续三个字节或者四个字节的形式出现在GPS原始测量数据中，NMEA0183格式数据和姿态传感器帧头起始位等具有特定语义的数据占有较长数据位，适合将较长数据帧头存储在字典中重新编码达到压缩数据目的。因此，需要针对标校系统数据的特殊情况，设计一种新的压缩算法。

3.2 算法描述

标校系统的数据存储是基于ASCII编码形式，8bit为单位统一存储，笔者预先对大量数据进行统计后，设计一种压缩算法，采用LZ77压缩算法和游程编码的思想对冗余度较高以及存在关联性的数据进行统一编码，同时克服两种算法的局限性，达到在算法复杂度低的情况下较好地完成数据压缩的目的。

原理主要有：

1）LZ77算法时间复杂度为O（n2），压缩过程中将大量时间资源用于寻找最长匹配字符串，本文对LZ77算法进行改进，预先采集大量数据统计中得知，连续三个字节或者四个字节的数据结构前后重复度较高，因此，预先将重复率较高的四个或者三个字节数据结构组成字典，将重复率高的数据结构和具有特定语义字符串采用16bit统一编码，构成基于字典的压缩数据，并且NMEA0183格式帧头等具有特定语义数据压缩数据查找表时优先查找。字典序列一共95条，结构图1所示。

连续三个或者四个字节重复数据结构以及较长字符串且具有特定语义数据压缩为16bit编码数据结构如图2所示。

在压缩过程中，将窗口大小初始值设置为4，不断将窗口中的数据与字典中数据比较，如果与字典中的数据匹配成功，则将数据编码为字典中的16bit，并按16位整数类型数据存储。如果窗口中的数据$开头，则是NMEA0183数据长度为6字节的帧头标志，则将数据编为字典中的16bit，并按16位整数类型数据存储。

图1 字典结构图

图2 压缩后16bit数据编码结构

2）通过对大量数据统计得知，GPS原始测量数据中，‘0’字符在有局部大量连续情况存在，对局部连续大量‘0’基于游程编码的思想，采用16bit统一表示。压缩后16bit编码数据结构如图3所示。

图3 基于游程编码思想压缩数据编码图

在基于游程编码思想编码压缩数据时，当数据‘0’连续重复超过5次时，将连续重复的数据‘0’按图3的情况进行编码后压缩为16bit的整数类型数据。例如000000，编码为1000000000000110，将连续5个字节‘0’数据编码为这16个二进制位，并转换为整数类型数据32774，压缩后只占两个字节。

在压缩过程中，如果数据不需要按上述情况处理，则转换为8位整数类型存储。解码过程中，如果整形数据大于32768，则按基于游程编码压缩的数据结构进行解码，当整型数据大于256且小于32768时按照基于字典压缩的数据结构进行解码。

4 算法应用测试

为检验笔者设计算法性能，笔者使用基于U-Blox公司型号为NEO-M8T的GPS芯片搭建的开发板采集GPS原始测量数据和NMEA0183格式数据，姿态传感器采用超核电子公司型号为HIM219基于陀螺仪的姿态传感器，GPS原始测量数据与NMEA0183数据每秒接收一次，姿态传感器工作的频率为5Hz，嵌入式标校系统将每秒采集的上述数据进行压缩，多次实验结果如表1所示。

表1 算法应用测试结果

算法基于数据量有限的字典对重复率高的数据结构进行编码，并局部使用游程编码压缩数据，时间复杂度为O（n），空间开销较小，经实验得出，本文设计的算法压缩率基本稳定，能在算法复杂度较低和空间开销较低的情况下完成嵌入式标校系统的数据压缩功能。

5 结语

本文针对前期搭建的基于无人机的嵌入式标校系统产生的数据量较大且ARM处理器工作时任务繁重不易处理数据的问题，预先采集大量的数据，对数据分片分析研究其中的数据结构，综合了LZ77算法与游程编码的压缩思想，设计了一种适合嵌入式标校系统的数据压缩算法，将需要压缩的数据统一采用16bit数据结构进行编码，算法基于字典压缩数据，但改进后降低了时间复杂度，同时将局部大量连续数据基于游程编码算法进行编码，算法性能稳定，有很好的实用价值。