江苏龙网

  1. 主页 > 生活百科 > >

理解 zip 和 gzip 压缩格式背后的压缩算法( 二 )

压缩算法


压缩EFTUPOEERRREOOPRRUTUTTEEE这个例子中，我们希望能无损地压缩这段文本 。通常一个字母占用 8 字节，所以这段文本总长度有 200 字节 。在这段本文中，我们发现其中字母 F 只出现了 1 次，而字母 E 出现了 7 次 。哈夫曼编码正是利用了这一特性，通过减少出现频率高的字母本身的字节长度，来减少整个文本所占的总长度 。
要采用哈夫曼编码压缩文章，首先需要统计各个文本中各个字母的出现频率，上述例子中的字母频率如下：
频率: E: 7, R: 5, T: 4, U: 3, O: 3, P: 2, F: 1我们需要使用文本中的字母作为叶子节点来构建一颗二叉树，通过这颗二叉树来编码文本中的每一个字母 。从出现频率最小的字母： P 和 F 开始，让其作为底层的叶子节点，将其频率相加的值作为父节点，这样便得到了如下的二叉树：
(3)/P(2)F(1)重复上面的步骤，依次使用频率最小的字母： U 和 O 以及 R 和 T ，最后剩下频率最高的字母 E 先单独放着 。
(6)(9)E(7)//U(3)O(3)R(5)T(4)接下来使用上面得到的 4 个二叉树作为子节点来创建一颗更大的二叉树，将上面的二叉树的根节点的频率值递增排序，优先使用根节点频率值小的二叉树作为新的二叉树子节点 。这里使用 U 和 O 、 R 和 T 这两组二叉树组成了如下的一颗二叉树：
(9)//(6)(3)//UO PF这时候还有 3 颗二叉树，根节点分别为：9、9、7（第一个 9 是上一步创建的二叉树），同样的，将根节点频率值最小的两个作为子节点创建新的二叉树如下：
(16)/(9)E//(6)(3)//UO PF复制代码现在剩下一颗将根节点值为 16 的大二叉树和根节点值为 9 叶子节点为 R 、 T 的二叉树，将其作为子节点创建一颗新的二叉树如下：
(25)//(16)(9)//(9)E RT//(6)(3)//UO PF【理解 zip 和 gzip 压缩格式背后的压缩算法】现在我们要做的就是根据这棵二叉树来对文本进行编码 。依次从跟节点访问各个字母，遇到左分支当成 0，遇到右分支当成 1，按照字母沿着二叉树访问路径的顺序所将这些 0、1 连接起来 。比如，从根节点到字母 E 先后需要经过 1 次左分支和 1 次右分支，所以字母 E 的编码为 10。字母 U 需要经过 4 次左分支，其编码为 1111 ； F 需要经过 2 次左分支和 2 次右分支，其编码为 1100。可以发现，在这里例子中出现频率非常高的字母 E 编码后位数比出现频率较少的字母 F 编码后位数要少 。经过这样的编码处理，最终压缩过的文本如下：
10110000111111011110101001010110111011101101010111110011110000101010这段压缩后的文本长度只有 68 位，远比原始的 200 位长度小 。
解压假如收到这样一段压缩过的文本，我们希望能够解压它让其变得可以理解 。我们都知道一段未压缩过的文本中的一个字符占用 8 位，上面说过经过哈夫曼编码压缩后一个字符的位数并不是固定 8 位的，所以并不清楚一段数据（比如： 011 ）是表示 1 个字符、2 个字符或者 3 个字符，因此这段压缩过的文本将如何解压呢？
这一步不存在任何奇迹，要准确解压还需要上面编码中构建的二叉树 。得到这个用于编码的二叉树有两种方案，第一种是其和压缩后的文本放一起作为原始文本的压缩结果，这可能会导致压缩后的文本比原始文本还要大；第二种方案是使用预先定义好的二叉树 。我们知道各个字母在英语中的使用频率，完全可以根据这个频率来构建上述的二叉树 。使用这种预先定义的公共字母频率二叉树压缩部分文本的结果可能比根据文本内容字母频率二叉树压缩的效果差一些，但是这样不再需要将字母频率二叉树保存到压缩后的文件中 。总而言之，这两种方案各有优缺点 。
虽然本文没有深入的分析各种压缩算法原理的细节和对应的实现，但是经过上述讲解你应该已经对文本如何被压缩成 zip 和 gzip 等格式有了大概的认识 。希望本文能满足你对压缩算法神秘面纱的好奇心:)
* 从技术上来说，zip 压缩格式是支持使用其他的压缩算法的，但是 DEFLATE 是其中最常用的一种 。



推荐阅读


上一篇：每个程序员都曾犯过的经典错误

下一篇：地球最强悍的生物 超级地球上有生命