深入解析数据压缩算法

《深入解析数据压缩算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、深入解析数据压缩算法所谓数据压缩，是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高传输、存储和处理效率的一种技术方法。或者是按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。能实现数据压缩的本质原因就是数据的冗余性。本系列将分为上下两个部分，介绍四种数据压缩算法，分别为Huffman压缩算法、RLE压缩算法、LZW压缩算法、Rice压缩算法。其中本文将详解Huffman压缩算法和RLE压缩算法第一节Huffman压缩算法huffman压缩算法可以说是无损压缩中最优秀的算法。它使用预先二

2、进制描述来替换每个符号，长度由特殊符号出现的频率决定。其中出现次数比较多的符号需要很少的位来表示，而出现次数较少的符号则需要较多的位来表示。huffman压缩算法的原理：利用数据出现的次数构造Huffman二叉树，并且出现次数较多的数据在树的上层，出现次数较少的数据在树的下层。于是，我们就可以从根节点到每个数据的路径来进行编码并实现压缩。老办法，还是举个例子。假设有一个包含100000个字符的数据文件要压缩存储。各字符在该文件中的出现频度如下所示：在此，我会给出常规编码的方法和Huffman编码两种方法，

3、这便于我们比较。常规编码方法：我们为每个字符赋予一个三位的编码，于是有：此时，100000个字符进行编码需要100000*3=300000位。Huffman编码：利用字符出现的频度构造二叉树，构造二叉树的过程也就是编码的过程。这种情况下，对100000个字符编码需要：(45*1+(16+13+12+9)*3+(9+5)*4)*1000=224000孰好孰坏，例子说明了一切！好了，老规矩，下面我还是用上面的例子详细说明一下Huffman编码的过程。首先，我们需要统计出各个字符出现的次数，如下：接下来，我根据

4、各个字符出现的次数对它们进行排序，如下：好了，一切准备工作就绪。在上文我提到，huffman编码的过程其实就是构造一颗二叉树的过程，那么我将各个字符看成树中将要构造的各个节点，将字符出现的频度看成权值。Ok，有了这个思想，herewego！构造huffman编码二叉树规则：从小到大，从底向上，依次排开，逐步构造。首先，根据构造规则，我将各个字符看成构造树的节点，即有节点a、b、c、d、e、f。那么，我先将节点f和节点e合并，如下图：于是就有：经过排序处理得：接下来，将节点b和节点c也合并，则有：于是有：经

5、过排序处理得：第三步，将节点d和节点fe合并，得：于是有：继续，这次将节点fed和节点bc合并，得：于是有：最后，将节点a和节点bcfed合并，有：以上步骤就是huffman二叉树的构造过程，完整的树如下：二叉树成了，最后就剩下编码了，编码的规则为：左0右1于是根据编码规则得到我们最终想要的结果：从上图中我们得到各个字符编码后的编码位：Ok，过程清楚了，我们来看看核心代码：由于Huffman编码在以前的文章已经给出过，故在这只给出链接！Huffman编码：http://blog.csdn.net/feng

6、chaokobe/article/details/6969217好了，Huffman编码就讲完了。Goon!第二节RLE压缩算法RLE：Run-lengthEncoding，译为“行程长度编码”，它是一个无损压缩的非常简单的算法。RLE压缩算法的原理：统计某一节字节在整个字节表中出现的次数，并以该字节和出现的次数作为编码的依据。好了，光说理论解决不了问题，还是用例子来说明。现有如下一些字节数据：那么，首先我对上述每个数据出现次数做统计，即得到：ok，编码的依据得到了，万事俱备。由于RLE编码太简单了，于是

7、我们一步就得到编码的结果了。如下：编码的过程简单，代码的实现也就很容易了，下面我们看看核心代码：[cpp]viewplaincopyprint?1.char*REL_Coding(char*src_ch,intlength,char*dst_ch)2./***src_ch为原始字符串，3.***length为原始字符串的长度，4.***dst_ch为根据算法得到的编码5.***/6.{7.inti=0;8.intj=0;9.intcount=0;10.charp=src_ch[0];11.12.while

8、(i<=length)//开始编码13.{14.if(p==src_ch[i])//如果有重复，计算其重复的次数15.{16.i++;;17.count++;18.continue;19.}20.dst_ch[j]=p;21.dst_ch[++j]=(count+'0');22.j++;23.count=0;24.p=src_ch[i];//下一次比较的开始位置25.}26.27.returndst_ch;28.}char*R