深入解析数据压缩算法VIP免费

深入解析数据压缩算法 所谓数据压缩，是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高传输、存储和处理效率的一种技术方法。或者是按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。 能实现数据压缩的本质原因就是数据的冗余性。 本系列将分为上下两个部分，介绍四种数据压缩算法，分别为 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 w e go！ 构造 huffman 编码二叉树规则： 从小到大， 从底向上， 依次排开， 逐步构造。 首先，根据构造规则，我将各个字符看成构造树的节点，即有节点a、b、c、d、e、f。那么，我先将节点f和节点e 合并，如下图： 于是就有： 经过排序处理得： 接下来，将节点b 和节点c 也合并，则有：...