【动态Huffman算法在GPS数据压缩中的应用】数据压缩最新算法

【动态Huffman算法在GPS数据压缩中的应用】数据压缩最新算法 摘要GPS现在越来越多的应用于车载定位系统,车载定位的存储空间有限不能大量的存储原始数据,为解决GPS数据量大的问题,提出用动态Huffman算法对GPS信号进行压缩的方法。通过实验证明该方法也确实能大大的压缩原始数据,缩短GSM信道占用时间长的问题。 关键词GPS数据格式压缩动态Huffman压缩算法树 :TP3:A:1671-7597(xx)11xx1-01 一、引言 嵌入式GPS车载系统般体积较小,价格低已经越来越多的被人们所使用,在开发嵌入式系统的软件产品时必须将软件所占的存储空间限制在一定的范围内。所以GPS测量因其观测时间长,采样间隔短而具有非常庞大的数据量,为降低数据冗余度又不改变信号的特征。因此本文用动态Huffman算法来处理GPS信号,缩短了GSM信道的占用时间,同时也大大地缓解了向控制调度中心上传数据的压力。 二、GPS数据格式 NMEA-0183通信标准的GPS输出数据采用的是ASCII码,其内容包含了纬度、经度、高度、速度、日期、时间、航向以及卫星状况等信息。嵌入式GPS车载系统的使用者只关心其日期和时间、纠度、面速度信息,因而可以只选用RMC记录语句。一条$GPRMC语句包括13个记录:语句标识头、世界时间、定位状态、纬度、纬度方位、经度、经度方位、地面速度、地面路线、日期、磁偏角、磁偏角方向和方式指示,它一共占用70个字节(其中还包括用于分隔记录所使用的11个逗号),例如从当地(经纬度为106.5E,29.5N)采集的一组数据: $GPRMC,032510,A,2934.0467,N,10634.3591,E,000.0,000.0,191203,001.6,w*65 由此可见,从OEM板接收下来的数据流是文本字符串。本设计中用动态Huffman压缩算法完成压缩及解压缩的任务。该方法属于无损压缩技术。 三、动态Huffman算法分析 在当今流行的数据压缩算法中,通常采用的方法都是Huffman压缩方法,因为对于计算机能识别的文本字符都是采用ASCII字符表示。而每一个ASCII字符占用一个字节即每8个比特定义一个字符。在一篇文章中不是每一个ASCII字符都出现,所以对每一个字符可以按照在文章中出现的频度建立一棵Huffman树,对其重新编码,这样就可以实现压缩存储。但实现Huffman算法的最大困难就是:1.压缩时必须知道每一要压缩的字符在文本中出现的概率。也就是说要事先了解数据,这势必造成需两次扫描输入串;2.必须维护并传送在压缩过程中建立起的串码对应表,以便在扩展时,由此字码表将压缩的码复原,这些困难使Huffman算法的使用范围备受限制,大大降低了Huffman算法的优越性,人们在此基础上构造的动态Huffman算法,则使Huffman算法的性能得到进一步提高。 动态Huffman算法的基本思想:该算法的核心是要构造一棵树,这棵树随输入串的输入而不断地调整修改以保证确实反映了所输入串数据变化着的概率,为调整树,我们还设计一张反映每一结点使用概率情况的结点重量表,使用次数多的结点,其“重量”必然重,越重的结点就要调整到树中离根越近的地方。动态Huffman算法只需一遍扫描,且无需维护和传输串码对应表。 四、GPS信号的预处理 让我们在来观察GPS信号的输出格式,发现有许多数据冗余,为了方便后续压缩的进行,先对输出的信号进行压缩预处理。 1.语句标识头(ID):因为每个语句的标识头都一样,所以该记录段属地冗余信息,完全可以去除,在解压缩时再在每个语句前加上该标识头即可。 2.世界时间(UTC):该信息段以时、分、秒、毫秒的格式指示出当时世界时间。转换为北京时间还需要再加上8小时。世界时间可以在程序的一开始采集记录一下,在解压缩时根据语句的指针值再加上起始时间便可以复原,因此该记录段在第一次存储后,以后的语句中的该信息全都是冗余信息。 3.定位状态(A/V):占用1个字节,不进行预处理。 4.纬度:占用9个字节,不进行预处理。 5.经度:占用10个字节,不进行预处理。 6.经度指示器(E/W):占一个字节,它指示出经度。由于本系统在中国应用都是东径,它是冗余信息,因此采取程序一开始存储一次的方法。 7.纬度指示器(N/S):占一个字节。处理同经度指示器。 8.地面速度:占用4个字节,不进行预处理。 9.日期:占用6个字节,以日、月、年的格式显示。因为该系统一天启动一次,日期相同,是冗余信息,采取程序一开始存储一次的方法。 10.磁偏角:占用5个字节不做处理。 结束符合占用2个字节,只用来判断语句的有效数据范围,其它记录段与本系统的设计无关都不保留和进行压缩。 五、对数据进行压缩 仍然以上面给出的数据为例,经过预处理后的GPS数据为 A,2934.0467,10634.3591,000.0,000.0,001.6 未预处理前是70个字节,即8*70=560位。预处理后有40个字节,即8*40=320位数据。然后对预处理后的数据进行Huffman压缩。 于是得到如下编码: 字符串的长度为: long=2*12+3*5+3*5+3*3+4*2+4*3+4*3+4*3+5*1+5*1+5*1+5*1=127位 通过以上实验可以明显看出,数据占用的位数变小,也就达到了压缩的目的。压缩比在本例中为77%,但用动态Huffman算法压缩的数据,压缩后的比例并不一样,要根据数据出现频率的大小而定。 六、结论 实验证明在GPS车载定位系统中,采用动态Huffman算法对车载GPS数据进行压缩,可以提高系统的稳定性和完整性,可进一步提高车载定位系统的精度。但动态Huffman算法也有它自身的缺点,就是无法处理出现频率相似的数据,还要继续研究。 _: 1Liu Quan.Jiang Xuemei.Yu Namin Research on Adaptive Digital Watermarking Ba