基于Huffman编码的GPS定位数据无损压缩算法

目录

一、引言

二、霍夫曼编码

三、经典Huffman编码

四、适应性Huffman编码

五、GPS定位数据压缩

---

提示：文末附定位数据压缩工具和源码

一、引言

        车载监控系统中，车载终端需要获取GPS信号（经度、纬 度、速度、方向等）实时上传至监控中心，监控中心按通信协议将收到的定位信息进行本地存储，便于实时监控以及历史轨迹回放。在对车队进行监控管理过程中，多辆车同时向监控中心传输GPS文件，在数据量大的情况下，对数据进行有效地压缩，降低信息冗余，降低通信费用，减少对传输信道的占用是在数据传输过程中需要解决的关键问题。

        本文针对GPS数据格式的特点，在数据预处理的基础上，提出了采用Huffman编码的方法对GPS定位数据进行压缩。该算法与目前现有的GPS定位数据压缩算法比较，程序量小，压缩比大，且易于实现。对解决车载GPS系统中数据量大而存储器资源有限的问题,以及数据传输的瓶颈问题具有重要的实际意义。

二、霍夫曼编码

        霍夫曼在1952年提出了霍夫曼编码，又称Huffman编码。这种编码因为最接近压缩比上限的编码方法，被称作最优编码。Huffman编码是无损压缩的编码，压缩后的文件重新解码后与源文件数据保持一致，这也是Huffman编码优于其他编码中最突出的地方。根据编码方式的不同，可分为经典（静态）Huffman编码和适应性（动态）Huffman编码。

三、经典Huffman编码

        经典的Huffman编码通过构造一棵用来编码和解码的Huffman树来对待处理数据进行编码。构造huffman树的首要前提是是获得每个字符的频率。然后根据字符出现的频率，构造Huffman树。首先可以将字符的频率作为节点的值。然后将所有结点排列成队列，从中选出值最小的两个结点，然后构造出一个父亲结点，使得父亲结点的值是两个孩子结点的值之和，然后将两个孩子结点出队，再将父亲结点入队，进入下一轮循环。原理图如下图所示。 

        

        由上图所示，我们获得6个字符的频次，并将它们构造成结点队列。从队列中频次最小的两个结点挑选出来，构造成一棵树。将这颗树的父亲结点入队，再从中挑选出频次最小的两个结点，依次递归，直到队列中只剩下一个根节点为止。这个时候我们就获得了Huffman编解码树。 

        获得Huffman编码树之后，我们便可以对每个字符进行重新编码，对于每个到达叶子结点所经过的路径中，如果它是一棵左子树，那么它的编码为0，如果它是一棵右子树，那么它的编码为1。我们假设编码前字符用三位二进制表示，编码后字符新的编码方式如下表所示。 

字符	频次	编码前	编码后
A	3	001	001
B	1	010	00000
C	5	011	01
D	6	100	1
E	2	101	0001
F	1	110	00001

        由上表可知，编码前该数据的比特数为（3+1+5+6+2+1）*3=54位。编码后该数据的比特位数为3*3+1*5+5*2+6*1+2*4+1*5=43位。压缩率为79.6%。随着数据量的增大，频次的逐渐提高，压缩率将进一步提升。
        但在实际生成文件过程中，由于也要将Huffman编码表保存在文件的头部，增加了文件的信息冗余，实际的压缩率要比计算出的压缩率要大一些。

四、适应性Huffman编码

         由于文件头部信息等冗余信息的存在，Huffman编码的压缩仍存在可提升空间。因此减少文件头部携带的信息，可以提高编码率。要减少文件头部的信息，就需要找到一种方式，使得编码和解码按照同样的机制运行，可以获得完全相同的Huffman树，不受文件编码的影响。

        查阅论文发现，Jeffery在1987年提出了一种自适应的Huffman编码方法，可以使得编码器和解码器在传输时构造代码，动态的收集和更新字符的概率，动态的更新Huffman树。这样的好处是不需要文件头部的信息，编码器和解码器文件编解码过程中实时生成Huffman树。具体原理如下。

        首先我们对待处理的数据的字符列表的权值赋值为1，构造一棵初始的Huffman树；从文件中获得第一个字符，将字符根据当前的Huffman编码写入到文件中，通过将对应字符的权值加1，更新Huffman树。 自适应Huffman编码的原理图如下图所示。

        由上图所示，左边第一颗Huffman树是初始构造的Huffman树，所有的叶子结点权值为1；此时A的编码为00000；当从文件中获得一个新的字符时，Huffman树的权值发生更新，获得中间的二叉树，这颗二叉树已经不满足兄弟性质，因为A的叶子结点和B的叶子结点在重新排序过程中将不相邻，因此需要将该二叉树重新调整为一棵新的二叉树，即右边新得到的Huffman树，此时A的编码变为1。 

        自适应Huffman编码相比于经典的Huffman编码不需要文件头部统计各个字符的词频，只需要依据自适应策略不断的动态调整Huffman树，可以减少文件头部的信息冗余。但如果在压缩过程中或文件保存过程中出现损坏，得到的文件将无法还原为原来的数据。

五、GPS定位数据压缩

1、CSV格式的定位数据如下图

2、对定位数据预处理，缩减字符数量

3、精简后的字符串如下图，压缩率为40%左右 

4、构建自适应Haffman树进行二次压缩

通过构建自适应Haffman树进行二次压缩，压缩率可达15%左右。

5、压缩结果演示

a)将源csv文件复制到该目录下
b)运行脚本文件start.bat
c)输入1并回车，执行压缩操作，生成compress.txt压缩文件

6、解压缩结果演示

a)删除源csv文件
b)运行脚本文件start.bat
c)输入2并回车，执行解压缩操作，生成decompress.csv解压缩文件