进一步思考几个问题
在压缩文件的时候,人们不禁会产生一些新想法或者遇到一些疑问:是否可以对压缩后的数据再次压缩?当2 n 的n变大后,遇到A:1010,B:10这样的情况,如何解读10101010?
就操作上来说,当然能反复编码,但通过对本文例子中得到的新编码再次操作后会发现,结果是不会有任何变化的。压缩的实质,在于消除特定字符分布上的不均衡,通过将短码分配给高频字符,而长码对应低频字符实现长度上的优化。而数据经过一次压缩后,字符的分布已经几乎平均化了,很难更进一步的压缩了。
而第二个问题描述的情况是不会出现的的。从构造霍夫曼树操作上可以看到,一个字符无法在另一个字符的上层。只要操作正确,就一定可以构造出唯一的代码表,不存在歧义。
还有一个有趣的问题是:虽然把40字节的内容压缩到了34字节,但需要将相应的码表一并发送给接收方(没有对应码表,无法解压)。这不反而使得压缩后的数据比压缩前的还要长?
事实也确实如此。本文例子中,真正的最终结果体积是大于原文的。但这不意味了算法错误。这是因为“n”过小(例子中为2,实际通常为8)导致的。
总长度的不够使得节省出来的那部分容量还不足以弥补码表本身的储存空间。实际应用中,如果你非要去压缩一个只有几个字节的文件,得到的压缩包也经常会大于文件本身。通常,压缩软件会在每压缩4kb到32kb数据后,重新生成并保存一个霍夫曼树。当分块过大时,统计上的整体平均,会掩盖小区域内的极度不平均,损失了压缩的空间。比如存在一个这样的文件:
AAAAA……AAAAA(一万个)BBBBB……BBBBB(一万个)……ZZZZ(一万个)。
如果从整体上进行霍夫曼树操作,将不会产生任何压缩,但是这时候我们把它分成26块,压缩并各自保存相应的重新编码的霍夫曼树,压缩率将非常惊人,约等于12.5%。
英语中各字母出现频率示意图
从上面字频图我们知道,在现实的文本中,英语字母使用频率各不相同,而且差别很大。有着很高的不平均度。所以大部分压缩软件对文本文件依然有着很高的压缩率。