求证或证伪，对于任意无损压缩算法，比如zip

[（ヅ）]

一定存在某二进制文件,使得压缩后的文件容量不会减少

假设所有文件都是简单的二进制数据，无overhead，没有固定的格式数据

[YouHi]

不断把压缩过的再次压缩。肯定不会越来越小。

[huangchong]

一定存在某二进制文件,使得压缩后的文件容量不会减少

假设所有文件都是简单的二进制数据，无overhead，没有固定的格式数据

岂非香农的信息墒乎？

[（ヅ）]

不断把压缩过的再次压缩。肯定不会越来越小。

居然毫无违和，说明题目没出好

如果固定输入长度为2kB呢

[huangchong]

居然毫无违和，说明题目没出好

如果固定输入长度为2kB呢

假设有2kbit的数据比较方便

如果收发方各有一个长度为 2^(2k）的字典 这个字典涵盖所有长度2kbit的01串 因此它的内容也不用存 按需要换成数字即可

于是可以把信息编码成2^（2k-1）长的序列号发送 结果是双方仍旧需要发送2kbit

[huangchong]

居然毫无违和，说明题目没出好

如果固定输入长度为2kB呢

既然任意长的字串都已经被证明了 特殊长度的字串会有什么不同呢

[huangchong]

公理1： 不可能用比1比特小的存储器来 存储1比特的数据。这很明显，要存储0或者1（1比特），不可能什么存储器都不用（0比特），也不存在半比特

公理2 ： 不可能用1比特的数据，存储2比特的信息。 因为0，1，2，3，四个信息，压缩成1比特，就成了两个信息，解压的时候，怎么能从2个状态分解出4个状态呢

公理3 ： 不可能用1或2比特的数据，存储3比特的信息。 因为3比特有8种状态，而1比特加上2比特，一共才6种状态，6种记录方式全用上，也不可能无歧义还原出8种状态

同样 3比特的数据，一共是 2＋4＋8＝14 种状态，小于存储4比特信息所需的16种状态


看出来了吧， n bit的信息 永远不可能用 1..(n-1) 比特的数据来全部表示。 因为2^n - 2^(1+....+n-1) = 2 , 永远差两个编码，来表示所有的2^n个状态

所以，公理X： 如果需要记录所有的n bit信息，是必须要用n bit的存储器的






那现在题目问，我有2K byte＝16kbit的任意数据，对于任何一个给定的压缩方式，是否肯定存在一个不可压缩的特定16kbit串呢。看看上面的分析，答案是肯定的:



a，既然是压缩，就是说要求对给定的任意16kbit字串，必须要要得短于16k bit的编码。也即是说，要有个从输入的16kit 字串 到一个或多个长度在 1和（16k-1） bit 之中的二进数的映射

b，压缩后得到的编码只可以解出唯一一个16kbit字串：如果一个编码对应两个输入，那就不能解压缩。那就是说，对每个输入的16kbit字串，需要有个独特的编码。所以，1 到（16k-1） bit 这些字串，只能分别对应0或1个解压结果。

而前面分析过了， 1...n-1比特的所有数字 只能索引 （2^n-2） 种信息。也就是说至少有两个 16k bit字串，是无法被长度为 (1... 16k-1） bit的，所有可能的压缩字串，中的任何一个，无歧义编码的。所以必然至少有两个16k bit字串，在给定的压缩算法里，找不到比它短的映射结果，因此无法被压成更短的字串。所以，根本原因是，编码不够用。




所以，这算是用一种笨而直观的方法，重新叙述了一遍为啥n位 2进制编码恰好携带 2^n bit的总信息量

[huangchong]

公理1： 不可能用比1比特小的存储器来 存储1比特的数据。这很明显，要存储0或者1（1比特），不可能什么存储器都不用（0比特），也不存在半比特

公理2 ： 不可能用1比特的数据，存储2比特的信息。 因为0，1，2，3，四个信息，压缩成1比特，就成了两个信息，解压的时候，怎么能从2个状态分解出4个状态呢

公理3 ： 不可能用1或2比特的数据，存储3比特的信息。 因为3比特有8种状态，而1比特加上2比特，一共才6种状态，6种记录方式全用上，也不可能无歧义还原出8种状态

同样 3比特的数据，一共是 2＋4＋8＝14 种状态，小于存储4比特信息所需的16种状态


看出来了吧， n bit的信息 永远不可能用 1..(n-1) 比特的数据来全部表示。 因为2^n - 2^(1+....+n-1) = 2 , 永远差两个编码，来表示所有的2^n个状态

所以，公理X： 如果需要记录所有的n bit信息，是必须要用n bit的存储器的






那现在题目问，我有2K byte＝16kbit的任意数据，对于任何一个给定的压缩方式，是否肯定存在一个不可压缩的特定16kbit串呢。看看上面的分析，答案是肯定的:



a，既然是压缩，就是说要求对给定的任意16kbit字串，必须要要得短于16k bit的编码。也即是说，要有个从输入的16kit 字串 到一个或多个长度在 1和（16k-1） bit 之中的二进数的映射

b，压缩后得到的编码只可以解出唯一一个16kbit字串：如果一个编码对应两个输入，那就不能解压缩。那就是说，对每个输入的16kbit字串，需要有个独特的编码。所以，1 到（16k-1） bit 这些字串，只能分别对应0或1个解压结果。

而前面分析过了， 1...n-1比特的所有数字 只能索引 （2^n-2） 种信息。也就是说 至少有两个 16k bit字串，是无法被 (1... 16k-1） bit的压缩结果 无歧义编码的。所以必然至少有两个16k bit字串，在给定的压缩算法里，找不到比它短的映射结果，因此无法被压成更短的字串。




所以，这算是用一种笨而直观的方法，重新叙述了一遍为啥n位 2进制编码恰好携带 2^n bit的总信息量

这个分析说明，一般情况下，我们可以压缩数据，是因为被压缩的数据里存在冗余，数据的变化程度并没有完全用到存储方式给它提供的信息容量。。

同时也说明，不存在一种对任何数据都能压缩的压缩算法。只存在广谱的，对适用范围内的数据有一定效果的压缩算法。

[（ヅ）]

公理1： 不可能用比1比特小的存储器来 存储1比特的数据。这很明显，要存储0或者1（1比特），不可能什么存储器都不用（0比特），也不存在半比特

公理2 ： 不可能用1比特的数据，存储2比特的信息。 因为0，1，2，3，四个信息，压缩成1比特，就成了两个信息，解压的时候，怎么能从2个状态分解出4个状态呢

公理3 ： 不可能用1或2比特的数据，存储3比特的信息。 因为3比特有8种状态，而1比特加上2比特，一共才6种状态，6种记录方式全用上，也不可能无歧义还原出8种状态

同样 3比特的数据，一共是 2＋4＋8＝14 种状态，小于存储4比特信息所需的16种状态


看出来了吧， n bit的信息 永远不可能用 1..(n-1) 比特的数据来全部表示。 因为2^n - 2^(1+....+n-1) = 2 , 永远差两个编码，来表示所有的2^n个状态

所以，公理X： 如果需要记录所有的n bit信息，是必须要用n bit的存储器的






那现在题目问，我有2K byte＝16kbit的任意数据，对于任何一个给定的压缩方式，是否肯定存在一个不可压缩的特定16kbit串呢。看看上面的分析，答案是肯定的:



a，既然是压缩，就是说要求对给定的任意16kbit字串，必须要要得短于16k bit的编码。也即是说，要有个从输入的16kit 字串 到一个或多个长度在 1和（16k-1） bit 之中的二进数的映射

b，压缩后得到的编码只可以解出唯一一个16kbit字串：如果一个编码对应两个输入，那就不能解压缩。那就是说，对每个输入的16kbit字串，需要有个独特的编码。所以，1 到（16k-1） bit 这些字串，只能分别对应0或1个解压结果。

而前面分析过了， 1...n-1比特的所有数字 只能索引 （2^n-2） 种信息。也就是说至少有两个 16k bit字串，是无法被长度为 (1... 16k-1） bit的，所有可能的压缩字串，中的任何一个，无歧义编码的。所以必然至少有两个16k bit字串，在给定的压缩算法里，找不到比它短的映射结果，因此无法被压成更短的字串。所以，根本原因是，编码不够用。




所以，这算是用一种笨而直观的方法，重新叙述了一遍为啥n位 2进制编码恰好携带 2^n bit的总信息量

这个思想包括步骤都是是正确的

无损压缩是可以还原，即为双射

双射就有个性质定义域跟值域一样大

[laodongzhe18]

压缩算法就是一个信息替代算子，如果我构建一个包子压缩算法，1就是有包子，0就是没包子，那么这个文件的大小就是一个比特，不可能再小了。

[lsheng]

这要额外证明，难道不是随机产生的数据，没相关性就不能压缩么？

[boss]

真尼玛蠢啊 你把压缩的输出当作输入 不就明白了吗？

[（ヅ）]

真尼玛蠢啊 你把压缩的输出当作输入 不就明白了吗？

真尼玛蠢啊，连一阶逻辑是什么都没听过吧

[boss]

真尼玛蠢啊，连一阶逻辑是什么都没听过吧

大蠢材 任意一个输出 可不就是不能再压缩吗？

这么提示都不明白 蠢啊

[（ヅ）]

大蠢材 任意一个输出 可不就是不能再压缩吗？

这么提示都不明白 蠢啊

蠢货连一阶逻辑都不知道是什么

建议喂猪去比较适合你

[boss]

蠢货连一阶逻辑都不知道是什么

建议喂猪去比较适合你

蠢蛋 这跟一阶逻辑有个jb毛关系 自己再读读自己的主贴 蠢！

[（ヅ）]

蠢蛋 这跟一阶逻辑有个jb毛关系 自己再读读自己的主贴 蠢！

你这傻子连题目都读不懂，别秀智商了

[boss]

你这傻子连题目都读不懂，别秀智商了

蠢驴 连“存在”都无法理解 丢人现眼 还尼玛一阶逻辑 离散数学学狗肚子里了

[（ヅ）]

蠢驴 连“存在”都无法理解 丢人现眼 还尼玛一阶逻辑 离散数学学狗肚子里了

哈哈，果然是个大聪明

拉盛洗碗工里就你离散数学最好

[YouHi]

真是凑巧。这个科普文章今早被送到我的邮箱：

Data Compression Drives the Internet. Here’s How It Works.



Huffman’s approach has turned out to be so powerful that, today, nearly every lossless compression strategy uses the Huffman insight in whole or in part.

https://www.quantamagazine.org/how-loss ... -20230531/