Question

关于无损压缩算法的疑问

任何一种现在常见的压缩算法（比如winrar的），压缩率一定会小于1吗？不会出现某个文件用这种算法压缩后反而变得更大的情况？总之目前我没遇到过，最次的情况也是遇到压缩率99%的。

但有一个问题，如果这种算法真的这么“强悍”，对所有的数据都能实现压缩率小于1的压缩，那必然会出现“任何一组包含N个字节（即N*8bit）的数据，都能用同一种映射规则（即这个压缩算法）映射成一组数据量少于N*8bit的数据”这样的结论，如果设所有由N个字节构成的数据的集合为集合A，则A中应有2^（N*8）个元素。A被压缩算法映射后的集合为B，则B中元素个数理应同于A即等于2^(N*8)，但实际上由于B中的数据大小都小于（8*N）bit，所以B中的元素个数必小于2^(1)+2^(2)+……+2((8*N)-1) = 2^(8*N) - 2。于是矛盾出现了。。。。。。不知道我的叙述是否表述地足够清晰，总的来说意思就是，N字节能表示的所有信息，在同一种压缩算法下，不可能全部用少于N字节的数据表示出来。

原谅我的无知，总之我就是感觉像这种“万能”的压缩算法肯定是不存在的，任何一种压缩算法都会出现压缩率大于1甚至远大于1的情况。注意我说的是无所压缩，不讨论有损压缩，那是另外一回事了。

（可能有大神要提到信息论信息量信息熵之类的，提就提吧，差不多可以理解）

送20分，当学费了

Answer 1

你要造成压缩后更大的情况很简单，你将一个文件压缩后，对这个rar再次压缩看看，不断的重复这个过程，最终总会出现压缩后比前面更大的情况（实际上一般压缩过一次之后，第二次再压缩的时候，压缩后的文件就会出现比压缩前更大的情况）。

Answer 2

这类算法压缩率较低，一般为1／2~1／5。典型的无损压缩算法有：Shanno-Fano编码、Huffman(哈夫曼)编码、算术编码、游程编码、LZW编码等。 基于哈夫曼编码...