其实我并不知道压缩软件工作的原理。我就是知道Huffman编码：）我中学的时候还用Pascal写过一个压缩和解压缩的程序。真的可以用！
从一点数学推理开始。如果压缩是可逆的（不可逆还有谁会用？），那么就是一个可逆映射。从有限长的文件到有限长的文件。易见：（毕竟是blog么）一定存在某文件“压缩”之后长度变大。而且，这样的文件应该很多。
为什么我们日常压缩的文件总是变小呢？呵呵。。。。。。
我曾经是个爱思考好孩子。中学的时候我就想，怎么压缩呢？怎么把5个数表示的信息用3个数表示呢？想了好久都没有想出来。那个时候毕竟没有受过系统的数学训练，上面那段推理虽然简单，当时并没有意识到。
后来有一天一家计算机报纸专题介绍了Huffman编码的原理。茅塞顿开！大赞这个想法天才。日子久了，觉得也就一般般，为什么不呢？
简单地说，计算机里面的字节是0－255之间的一个数，用8个2进制位储存。但是一个文件里面，出现不同的数的次数是不同的，比如30％的字节都是0，只 有几个255，等等。这么以来用少几个bit表示0，多几个bit表示255不就赚了？Idea就是这么简单。当然了，还有些需要注意的地方。一个数字对 应的二进制表示如果长度不等，就要想办法避免歧义。那个都不说了。
这只是最原始的想法，流行的软件中的算法一定比这个改进了很多。听说还有很多专利问题。也是应该的，如果你手头有一个更好的压缩算法，不管是一般的数据还是多媒体。首先，就应该去开公司，去拉风险投资，然后上市，然后。。。。。。
还是中学的时候，再自恋一下，我问了一个好问题。我问教我们编程的老师，为什么不能把压缩后的文件再压缩一次呢？老师说，这个是信息熵的问题。年轻的我就这样被吓唬住了。多少年过去了，我竟然回到了这个问题上。这次我可是非常的professional.
- C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, July, October, 1948
这个要另外详谈。
没有评论:
发表评论