cms建站详细教程,深圳app客户端做网站,网站推广的10种方法,微信社群营销推广方案目录
一、引言
二、霍夫曼编码
三、经典Huffman编码
四、适应性Huffman编码
五、GPS定位数据压缩 提示#xff1a;文末附定位数据压缩工具和源码 一、引言 车载监控系统中#xff0c;车载终端需要获取GPS信号#xff08;经度、纬 度、速度、方向等#xff09;实时上传…目录
一、引言
二、霍夫曼编码
三、经典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 由上表可知编码前该数据的比特数为315621*354位。编码后该数据的比特位数为3*31*55*26*12*41*543位。压缩率为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解压缩文件
