原创 GPS定位数据压缩算法的设计与实现

摘要：为了解决嵌入式GPS车载系统中存储空间小、GPS定位数据量大的矛盾，根据GPS定位数据的特点，提现了专用于GPS定位数据压缩的改进型半字节压缩算法。该算法是一种在原半字压缩算法的基础上改进的算法，经过实际测试，压缩比可达50%。若将压缩预处理也折算在内，总压缩比可达80%以上，为车载系统节省了大量的存储资源。除此之外，也缩短了GSM信道的占用时间，大大地缓解了向控制调度中心上传数据的压力。
关键词：数据压缩　GPS数据格式　压缩预处理　半字节压缩算法

嵌入式GPS车载系统一般体积较小，无存储量大的硬盘等设备，系统程序、应用程序一般装在FLASH或ROM中。由于FLASH 或 ROM等存储介质的价格相对台式机上广泛使用的硬盘、光盘等来说是非常昂贵的，因此，在开发嵌入式系统的软件产品时必须将软件所占的存储空间限制在一定的范围内。
在GPS车载系统的研发过程中，主要需解决的问题是：车载系统为了实现自导航，必须储存大量的GPS定位数据(每天需要存储约6MB)；其二是这些数据还要通过GSM信道上传到控制调度中心(若通过短信业务发送，每次160B，则需要每分上传6次)。无疑，数据压缩是在不增加硬件成本的前提下，从软件的角度来充分发挥系统现有资源的有效办法。
数据压缩方法种类繁多，可以分为无损压缩和有损压缩两大类。无损压缩利用数据的统计冗余进行压缩，可完全恢复原始数据而不引入任何失真，但压缩率受到数据统计冗余度的理论限制，一般为2:1到5:1。这类方法广泛用于文本数据、程序和特殊应用场合的图像数据(如指纹图像、医学图像等)的压缩。有损压缩方法利用了人类视觉对图像中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息。虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响较小，却换来了大得多的压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩。
目前现成的压缩算法很多，但不能直接用于嵌入式系统当中，这完全由嵌入式系统的特点所决定。首先，用于嵌入式系统的数据压缩方法应是无损压缩方法。其次，压缩代码和解码所需的信息代码必须足够短，否则就会失去压缩的意义。还有，嵌入式系统的数据压缩必须结合具体的数据格式的特点，才能进一步提高数据的压缩比。除此之外，目前的压缩程序的启动执行必须人为干预，不能自动执行，因为它们是为文件系统设计的，而嵌入式系统的数据压缩必须能够自动执行。

1 GPS数据格式
GPS OEM板由变频器、信号通道、微处理器和存储单元等组成。GPS OEM板的型号甚多，性能各异，但大多采用美国国家海洋电子协会制定的NMEA-0183通信标准格式。本系统选择的是美国SiRF公司的SiRFstarII OEM板。SiRFstarII OEM板语句的输入、输出是通过RS232串行接口完成的其通信端口的数据格式应该设置为8个数据位、1个起始位和1个停止位(校验方式选为无奇偶校验)波特率设置为4800波特。NMEA-0183通信标准的输出数据采用的是ASCII码其内容包含了纬度、经度、高度、速度、日期、时间、航向以及卫星状况等信息,语句有六种,包括GGA、GLL、GSA、GSV、RMC和 VTG。对于不同的用途，选用的语句记录也不同，例如嵌入式GPS车载系统的使用者只关心其日期和时间、经纬度、地面速度信息，因而可以只选用RMC记录语句。一条$GPRMC语句包括13个记录：语句标识头、世界时间、定位状态、纬度、纬度方位、经度、经度方位、地面速度、地面路线、日期、磁偏角、校验和和结束标记，它一共占用70个字节(其中还包括用于分隔记录所使用的11个逗号)，例如：
$GPRMC,121530.998,A,4000.0162,N,11619.5476,E,0.00,240.81,160102,,*3B
由此可见，从SiRFstarII OEM板接收下来的数据流是文本字符串，根据GPS数据格式的特点，本设计中拟采用半字节法完成压缩及解压缩的任务。该方法属于无损压缩技术，其原理是去除字节中的冗余位，从而达到压缩目的。然而，这种方法只适用于纯数字文本文件的压缩，显然GPS定位数据并不是纯数字的，还必须在压缩前进行一下压缩预处理，最后再利用半字节压缩算法完成数据的压缩。