深入解析數据压缩算法.docxVIP

深入解析数据压缩算法所谓数据压缩，是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高传输、存储和处理效率的一种技术方法。或者是按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。能实现数据压缩的本质原因就是数据的冗余性。本系列将分为上下两个部分，介绍四种数据压缩算法，分别为Huffman压缩算法、RLE压缩算法、LZW压缩算法、Rice压缩算法。其中本文将详解Huffman压缩算法和RLE压缩算法Huffman压缩算法huffman压缩算法可以说是无损压缩中最优秀的算法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。其中出现次数比较多的符号需要很少的位来表示，而出现次数较少的符号则需要较多的位来表示。huffman压缩算法的原理：利用数据出现的次数构造Huffman二叉树，并且出现次数较多的数据在树的上层，出现次数较少的数据在树的下层。于是，我们就可以从根节点到每个数据的路径来进行编码并实现压缩。老办法，还是举个例子。假设有一个包含100000个字符的数据文件要压缩存储。各字符在该文件中的出现频度如下所示：在此，我会给出常规编码的方法和Huffman编码两种方法，这便于我们比较。常规编码方法：我们为每个字符赋予一个三位的编码，于是有：此时，100000个字符进行编码需要100000 * 3 = 300000位。Huffman编码：利用字符出现的频度构造二叉树，构造二叉树的过程也就是编码的过程。这种情况下，对100000个字符编码需要：(45 * 1 + (16 + 13 + 12 + 9)*3 + (9 + 5)*4) * 1000 = 224000孰好孰坏，例子说明了一切！好了，老规矩，下面我还是用上面的例子详细说明一下Huffman编码的过程。首先，我们需要统计出各个字符出现的次数，如下：接下来，我根据各个字符出现的次数对它们进行排序，如下：好了，一切准备工作就绪。在上文我提到，huffman编码的过程其实就是构造一颗二叉树的过程，那么我将各个字符看成树中将要构造的各个节点，将字符出现的频度看成权值。Ok，有了这个思想，here we go！构造huffman编码二叉树规则：从小到大，从底向上，依次排开，逐步构造。首先，根据构造规则，我将各个字符看成构造树的节点，即有节点a、b、c、d、e、f。那么，我先将节点f和节点e合并，如下图：于是就有：经过排序处理得：接下来，将节点b和节点c也合并，则有：于是有：经过排序处理得：第三步，将节点d和节点fe合并，得：于是有：继续，这次将节点fed和节点bc合并，得：于是有：最后，将节点a和节点bcfed合并，有：以上步骤就是huffman二叉树的构造过程，完整的树如下：二叉树成了，最后就剩下编码了，编码的规则为：左0右1于是根据编码规则得到我们最终想要的结果：从上图中我们得到各个字符编码后的编码位：Ok，过程清楚了，我们来看看核心代码：由于Huffman编码在以前的文章已经给出过，故在这只给出链接！Huffman编码：/fengchaokobe/article/details/6969217好了，Huffman编码就讲完了。Go on!第二节 RLE压缩算法RLE：Run-length Encoding，译为“行程长度编码”，它是一个无损压缩的非常简单的算法。RLE压缩算法的原理：统计某一节字节在整个字节表中出现的次数，并以该字节和出现的次数作为编码的依据。好了，光说理论解决不了问题，还是用例子来说明。现有如下一些字节数据：那么，首先我对上述每个数据出现次数做统计，即得到：ok，编码的依据得到了，万事俱备。由于RLE编码太简单了，于是我们一步就得到编码的结果了。如下：编码的过程简单，代码的实现也就很容易了，下面我们看看核心代码：[cpp] view plaincopyprint?char * REL_Coding(char *src_ch, int length, char *dst_ch) /*** src_ch为原始字符串， *** length为原始字符串的长度， *** dst_ch为根据算法得到的编码 ***/ { int i = 0; int j = 0; int count = 0; char p = src_ch[0]; while(i = length) //开始编码 { if(p == src_ch[i])//如果有重复，计算其重复的次数 { i++;; count++; continue; } dst_ch[j] = p; dst_ch[++j] = (count + 0); j++; count = 0; p = src_ch[i]; //下一次比较的开始位置 } return dst_ch; } 对于上述方法，有人提出：如