分页: 2 / 2

Re: 黄术迷:如何证明任意无损压缩都不能使得所有输出都比输入短?

发表于 : 2023年 6月 2日 00:43
huangchong
huangchong 写了: 2023年 6月 2日 00:38 是的 完全随机数据是没法压缩的

像png 图 tif 图 尚可用lzw试着压一压 是因为一般图片动态范围有限 宽度有限 所以存在局部的非随机性 换句话说 这些普通图片里存的信息量有限 并没有存储长x宽x每像素比特数那么多的信息

如果是巨大的tif图 高动态范围 还是不要试着去压缩比较好
当然 信息量其实有时候看 也是有点主观的 比如我打20个汉字 当我们知道它的规律 用40个字节是可以完美存储的 但是如果存成lzw压缩的图片 40字节就绝对不够 这看起来奇怪 实际原因是这俩虽然对人来说一回事 实际上存储的信息是不同的

Re: 黄术迷:如何证明任意无损压缩都不能使得所有输出都比输入短?

发表于 : 2023年 6月 2日 01:40
huangchong
(ヅ) 写了: 2023年 6月 1日 23:31rt
去stem看看,我新写了个回复,觉得把你的2kb问题给证明了 :lol:

Re: 黄术迷:如何证明任意无损压缩都不能使得所有输出都比输入短?

发表于 : 2023年 6月 2日 02:08
pinfish
用个不动点定理就证了
(ヅ) 写了: 2023年 6月 1日 23:45 换句话说,一定存在某个二进制文件,zip过后大小无法缩小

Re: 黄术迷:如何证明任意无损压缩都不能使得所有输出都比输入短?

发表于 : 2023年 6月 2日 02:09
pinfish
这就是个双射的拓扑性质
完全不需要考虑这么细节的东西
huangchong 写了: 2023年 6月 2日 00:38 是的 完全随机数据是没法压缩的

像png 图 tif 图 尚可用lzw试着压一压 是因为一般图片动态范围有限 宽度有限 所以存在局部的非随机性 换句话说 这些普通图片里存的信息量有限 并没有存储长x宽x每像素比特数那么多的信息

如果是巨大的tif图 高动态范围 还是不要试着去压缩比较好

Re: 黄术迷:如何证明任意无损压缩都不能使得所有输出都比输入短?

发表于 : 2023年 6月 2日 02:17
huangchong
pinfish 写了: 2023年 6月 2日 02:09 这就是个双射的拓扑性质
完全不需要考虑这么细节的东西
你们学过硬理科的,可以一眼看到本质。姆们被伪科学耽误了一辈子的,只能靠直观常识慢慢理解了

Re: 黄术迷:如何证明任意无损压缩都不能使得所有输出都比输入短?

发表于 : 2023年 6月 2日 03:03
tlihz
huangchong 写了: 2023年 6月 1日 23:54 不断重复zip 如果总能缩小 那最后可以得到 内容为0的文件 于是可以说 空文件反复解压 可以得到世上任何黄片 显然这是荒唐的


所以 首先额不仅世上存在一个不可压缩的文件 而且存在无穷多不可压缩的文件 否则这个世界上的信息量就是有限值
哈哈,这个证明不错

Re: 黄术迷:如何证明任意无损压缩都不能使得所有输出都比输入短?

发表于 : 2023年 6月 2日 05:48
pinfish
希尔伯特旅馆 :lol:
蝗总很有数学天赋
huangchong 写了: 2023年 6月 1日 23:54 不断重复zip 如果总能缩小 那最后可以得到 内容为0的文件 于是可以说 空文件反复解压 可以得到世上任何黄片 显然这是荒唐的


所以 首先额不仅世上存在一个不可压缩的文件 而且存在无穷多不可压缩的文件 否则这个世界上的信息量就是有限值

Re: 黄术迷:如何证明任意无损压缩都不能使得所有输出都比输入短?

发表于 : 2023年 6月 2日 15:25
(ヅ)
huangchong 写了: 2023年 6月 2日 00:21 huffmann是基于存在redundancy的 (里面关键一步是数频率,别忘了) 对于完全随机的数据 编码以后不会变小
我冥思苦想一顿饭终于想明白了

在各种字符出现大约是均匀分布的时候,是无法压缩的