GPS定位数据压缩算法的设计与实现 摘要:为了解决嵌入式GPS车载系统存储空间小、GPS定位数据量大的矛盾,根据GPS定位数据的特点,提出了专用于GPS定全数据压缩的改进型半字节压缩算法。该算法是一种在原半字节压缩算法的基础上改进的算法,经过实际测试,压缩比可达50%。若将压缩预处理也折算法在内,总压缩比可达80%以上,为车载系统节省了大量的存储资源。除此之外,也缩短了GSM信道的占用时间,大大地缓解了向控制调度中心上传数据的压力。 在GPS车载系统的研发过程中, 数据压缩方法种类繁多,可以分为无损压缩和有损压缩两大类。无损压缩利用数据的统计冗余进行压缩。数据统计冗余度的理论限制,般为2:1到5:1。这类方法广泛用于文本数据、程序和特殊应用场合的图像数据(如指纹图像、医学图像等)的压缩。有损压缩方法利用了人类视觉对图像中的某些频率成分不敏感的特性,允许压缩过程中的损失一定的信息。虽然不能xx恢复原始数据,但是所损失的部分对理解原始图像的影响较小,却换来了大得多的压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩。 目前现在的压缩算法很多,但不能直接用于嵌入式系统当中,这xx由嵌入式系统的特点所决定。首先,用于嵌入式系统的数据压缩方法应是无损压缩方法。其次,压缩代码和解码所需的信息代码必须足够短,否则就会失去压缩的意义。还有,嵌入式系统的数据压缩必须结合具体的数据格式的特点,才能进一步提高数据的压缩比。除此之外,目前的压缩程序的启动执行必须人为干扰,不能自动执行,因为它们是为文件系统设计的,而嵌入式系统的数据压缩必须能够自动执行。 GPS OEM板由变频器、信号通道、 ①语句标识头(ID):因为每个语句的标识头都一样,所以该记录段属地冗余信息,xx可以去除,在解压缩时再在每个语句前加上该标识头即可。 通过以上压缩预处理后,保留了四个数据记录,共占用24个字节,如图1所示。 文本数据的压缩的都是无损压缩技术,即还原后的文件应该与源文件xx相同。文本文件压缩的方法有很多种,如HUFFMAN编码、算术编码和字节压缩方法等。它们均是无损压缩方法,都适用于文本数据的压缩。半字节压缩方法是针对文本数据的特点所设计的,主要是去除文本中的字节中的冗余位,从而达到减少数据文件所占用的存储空间的目的。在数据压缩技术中,除压缩重复字符外,还可以根据数据本身的特点进行压缩。在计算机中,任何数据都是以某种代码的方式存储的。在些文件中,或许有一些代码具有某些相似之处,我们可以根据代码的特点进行特定的操作,压缩掉这些数据的相似部分,或者说压缩掉这些数据的特征部分,半字节压缩就是这样一种方法。半字节方法主要用于纯数字的文本文件的压缩,因为数字0~9的ASCII码的高四位都一样,是冗余的,因此每一个数字xx可以用低四位描述,即每个字节的八位编码可压缩为四位编码,压缩比理论上可趋近50%。 从图1中可以看出,经过预处理后的数据中,包含的文本字节有:“0~9”十个数字符号,“A”、“V”两个英文大写字母和一个小数点“.”符号,共13个字符。“A”、“V”、“.”的ASCII码的高四位显然与数字字节的不一样,半字节压缩方法不能简单套用。然而,我们知道四位二进制编码可区分16种状态,用来表示13种不同的字符是足够的。 压缩数据编码表如表1的慰,为了充分利用编码表中的状态,在原来13个字节的基础上又新增添了两个字符“B”和“W”,其四位编码分别为1101和1110。这两个字符是在压缩预处理过程中,用来记录那些因语句校验和出错而舍弃的语句。因为每条语句的时间信息全部在预处理阶段被舍弃,在解压缩时要恢复时间值。该值在正常情况下是根据时间的基数再加上语句的计数值(由于每秒接受到一条语句,所以语句计数值就是以秒为单位的时间增量)确定的。当发生语句校验和出错时,若处于定位有效状态,则在定位状态记录上不填写“A”字符,而填写“B”字符;若处在定位无效状态,则不填写“V”字符,而填写“W”字节。在以后解压缩时,若检测到“A”、“V”字节,时间的还原按正常的算法进行;若检测到“B”、“W”字符时,进行的还原除了按正常的算法进行以外还要加上秒钟,这样才能确保时间能够正确的恢复,这是因为“B”、"W"字节表示上一条语句发生错误已经被丢弃,语句的压缩是非连续的,有继句现象发生。
由图2可知,实现半字节压缩算法需要解决两上问题:首先是压缩对象的计数;其次是如何把两个数字的低位合并到一个字节中。后一个问题只要规定好压缩后的字节中奇数号字符的四位编码与偶数号字符的四位编码的存放次序即可,程序的实现非常简单,在此我们规定编号是奇数的字符放在高四位,编号为偶数的字符的编码放在低四位。假设压缩前的数据流中的前四个字节分别为“1、2、3、4”,则压缩后的数据格式如图3所示。 半字节压缩中需要解决的首要问题是压缩对象的计数问题,解决此问题的方法有两种:一种是半字节计数器(Half-Byte Counter),另一种是全字节计数器(Full-Byte Counter)。不管那一种方法,它们都要占用字节,再加上压缩标识也要占用字节,所以要影响数据的压缩比。改进后的半字节压缩算法xx解决了此问题,因为GPS定位数据经过压缩预处理后的数据长度是固定的24个字节长,不是动态可变的,所以不需要解决压缩对象的计数问题。一般来说,任何一种压缩算法都需要用压缩指示字符作压缩数据的标识,压缩标识符越短越好,因为过长会影响缩效果。然而,由于GPS定位数据中的所有字符都进行了编码处理,不存在原样字符(不进行压缩的字符,在解压缩时原样输出),因此压缩标识xx可以省略,可进一步提高数据的压缩比。压缩预处理程序框图和改进后的半字节压缩算法框图如图4所示。 GPS定位数据的压缩算法经过实际的验证,压缩比随着压缩数据的减小而略有减少,这是因为参照信息随着压缩数据的减小其所占的比例在逐渐增加的原故。但示,该压缩方法在车载系统中使用不仅能节省存储空间,而且能减少信道占有时间及提高数据的安全性。由于压缩程序是针对GPS数据格式编写的的,因此其压缩比大但通用性不强。尽管如此,该程序略做修改可移植到其它系统中,因为各个GPS厂家所执行的规范标准都是GPS厂家所执行的规范标准都是NMEA-0183,其数据的输出格式略有差别。 |