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

STEM版,合并数学,物理,化学,科学,工程,机械。不包括生物、医学相关,和计算机相关内容。

版主: verdeliteTlexander

boss
论坛精英
论坛精英
帖子: 6708
注册时间: 9月 30, 2022, 7:08 pm
昵称(选填): 上帝

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

帖子 boss »

(ヅ) 写了: 6月 2, 2023, 8:17 am 蠢货连一阶逻辑都不知道是什么

建议喂猪去比较适合你
蠢蛋 这跟一阶逻辑有个jb毛关系 自己再读读自己的主贴 蠢!
头像
(ヅ)楼主
著名点评
著名点评
帖子: 4578
注册时间: 8月 21, 2022, 2:20 pm

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

帖子 (ヅ)楼主 »

boss 写了: 6月 2, 2023, 8:20 am 蠢蛋 这跟一阶逻辑有个jb毛关系 自己再读读自己的主贴 蠢!
你这傻子连题目都读不懂,别秀智商了
图片
boss
论坛精英
论坛精英
帖子: 6708
注册时间: 9月 30, 2022, 7:08 pm
昵称(选填): 上帝

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

帖子 boss »

(ヅ) 写了: 6月 2, 2023, 8:21 am 你这傻子连题目都读不懂,别秀智商了
蠢驴 连“存在”都无法理解 丢人现眼 还尼玛一阶逻辑 离散数学学狗肚子里了
头像
(ヅ)楼主
著名点评
著名点评
帖子: 4578
注册时间: 8月 21, 2022, 2:20 pm

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

帖子 (ヅ)楼主 »

boss 写了: 6月 2, 2023, 8:24 am 蠢驴 连“存在”都无法理解 丢人现眼 还尼玛一阶逻辑 离散数学学狗肚子里了
哈哈,果然是个大聪明

拉盛洗碗工里就你离散数学最好
图片
头像
YouHi
论坛元老
论坛元老
帖子: 19812
注册时间: 7月 22, 2022, 10:36 pm

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

帖子 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/
Jack12345
论坛精英
论坛精英
帖子: 8119
注册时间: 7月 22, 2022, 11:46 am

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

帖子 Jack12345 »

boss 写了: 6月 2, 2023, 8:01 am 真尼玛蠢啊 你把压缩的输出当作输入 不就明白了吗?
这个 想法好。不过 有可能 还能 再压缩一点,虽然不多了

那就 再重复压缩 几次,直到 不能 再压缩了,就可以 得到 那个文件了
wttw
见习点评
见习点评
帖子: 1694
注册时间: 8月 2, 2022, 1:43 am

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

帖子 wttw »

就一个比特的文件,你能压缩到更小?
(ヅ) 写了: 6月 1, 2023, 11:49 pm 一定存在某二进制文件,使得压缩后的文件容量不会减少

假设所有文件都是简单的二进制数据,无overhead,没有固定的格式数据
头像
(ヅ)楼主
著名点评
著名点评
帖子: 4578
注册时间: 8月 21, 2022, 2:20 pm

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

帖子 (ヅ)楼主 »

huangchong 写了: 6月 2, 2023, 1:22 am 公理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的总信息量
后面的a b c是关键,前面的公理,可以通过香农-哈特利公式得到,不需要做假设,也对证明没帮助
图片
头像
(ヅ)楼主
著名点评
著名点评
帖子: 4578
注册时间: 8月 21, 2022, 2:20 pm

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

帖子 (ヅ)楼主 »

wttw 写了: 6月 2, 2023, 3:09 pm 就一个比特的文件,你能压缩到更小?
不能。所以前面限制了文件大小,不然就trivil了
图片
头像
hci
论坛精英
论坛精英
帖子: 6246
注册时间: 7月 22, 2022, 3:29 pm
昵称(选填): 海螺子

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

帖子 hci »

说了是无损压缩,那么压缩到香农信息量,就不能继续减小了,再小就与无损冲突了。证毕。

具体的说,哈夫曼编码就是最优的了,因为达到了香农极限。

如果需要保持其他特性,比如符号有顺序,要保持编码后的代码与原代码顺序一致,胡-塔克编码就最优的。这个玩意可以用在数据库上,我老的开源数据库马上就要发布这个特性,希望性能不会太差。
(ヅ) 写了: 6月 1, 2023, 11:49 pm 一定存在某二进制文件,使得压缩后的文件容量不会减少

假设所有文件都是简单的二进制数据,无overhead,没有固定的格式数据
头像
hci
论坛精英
论坛精英
帖子: 6246
注册时间: 7月 22, 2022, 3:29 pm
昵称(选填): 海螺子

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

帖子 hci »

压缩除了香农信息的概念,还有一种算法压缩的概念,就是看产生这个数据的算法的最小长度,所谓的柯尔莫哥洛夫复杂度。这个的量是可能低于香农信息量的。可惜这只是理论上的,没法具体算,其不可计算性是一个定理。

智能=柯尔莫哥洛夫复杂度,所以,真正的智能,不是造物。不可能造出一个真正具有智能的东西。LeCun, Marcus, Chomsky等人是对的,其他鼓吹AGI的人都是错的。

我老的博文,讲工业界可以如何用GPT赚钱的,被拆成了两个文章,最近要在venturebeat和另一个杂志上发了,也算给AGI泼一点冷水。
头像
verdelite
论坛元老
论坛元老
帖子: 14921
注册时间: 7月 21, 2022, 11:33 pm
昵称(选填): 众傻之傻

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

帖子 verdelite »

hci 写了: 6月 2, 2023, 5:08 pm 压缩除了香农信息的概念,还有一种算法压缩的概念,就是看产生这个数据的算法的最小长度,所谓的柯尔莫哥洛夫复杂度。这个的量是可能低于香农信息量的。可惜这只是理论上的,没法具体算,其不可计算性是一个定理。

智能=柯尔莫哥洛夫复杂度,所以,真正的智能,不是造物。不可能造出一个真正具有智能的东西。LeCun, Marcus, Chomsky等人是对的,其他鼓吹AGI的人都是错的。

我老的博文,讲工业界可以如何用GPT赚钱的,被拆成了两个文章,最近要在venturebeat和另一个杂志上发了,也算给AGI泼一点冷水。
AGI 只是要实现人的智能。并不是要实现什么“真正的智能”。这种“真正的智能”的说辞,我看类似于"perfect victim"那种东西。
没有光子;也没有量子能级,量子跃迁,量子叠加,量子塌缩和量子纠缠。
头像
hci
论坛精英
论坛精英
帖子: 6246
注册时间: 7月 22, 2022, 3:29 pm
昵称(选填): 海螺子

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

帖子 hci »

人的智能是我们唯一所知的智能,也就是真正的智能。

人的智能不是造物,也不可能造出。这就是我的意思。
verdelite 写了: 6月 2, 2023, 11:11 pm AGI 只是要实现人的智能。并不是要实现什么“真正的智能”。这种“真正的智能”的说辞,我看类似于"perfect victim"那种东西。
nk
著名点评
著名点评
帖子: 4004
注册时间: 3月 15, 2023, 6:49 am

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

帖子 nk »

hci 写了: 6月 2, 2023, 11:19 pm 人的智能是我们唯一所知的智能,也就是真正的智能。

人的智能不是造物,也不可能造出。这就是我的意思。
其是现在的机器已经引入了随机和自我修改,再完善和发展一下,实现对模糊知识的获取,这样就和人的智能就差不多了。

现在人工智能的攻坚是如何给机器赋予感情。
nk
著名点评
著名点评
帖子: 4004
注册时间: 3月 15, 2023, 6:49 am

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

帖子 nk »

WhiteRiver 写了: 6月 2, 2023, 4:59 pm 收敛吗

收敛还是震荡?
不用管是否收敛还是震荡,

假定开始的文件size是N个字节, 第i步后的文件size 是si, with s0=N

(*)必定存在一个有限值 k (1<=k<=N), such that sk-1 <=sk ,

如果(*)这个结论不对,则有s0 > s1 > ... >sN

每一步至少降低一个字节,到了N步之后, 由于s0=N,sN就小于1,因此矛盾

利用(*)的结果知道对于压缩k-1次的文件, 再压缩一次后的 文件size 是 sk , 不会小于输入的文件size sk-1

QED
nk
著名点评
著名点评
帖子: 4004
注册时间: 3月 15, 2023, 6:49 am

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

帖子 nk »

WhiteRiver 写了: 6月 3, 2023, 8:58 am 有没有可能增大,减少,增大,减少?

还是持续减少,然后不变了?

理论探讨,重点是有没有可能增大?
这个不知道,可能要看具体的压缩算法吧。 也许有的算法压缩后有可能增大。

数学完美的压缩算法需要加一个不能增大的这个条件。

可惜应用不是数学,哪个算法计算快,好编程,能解决大多数的压缩问题就可以了,数学的完美不是他们的首要考虑因素。
nk
著名点评
著名点评
帖子: 4004
注册时间: 3月 15, 2023, 6:49 am

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

帖子 nk »

WhiteRiver 写了: 6月 3, 2023, 9:06 am [ 163] ls -l zaa* Jun 03 9:02am
-rwxr-xr-x 1 13665 Jun 1 16:02 zaa.gz
[ 164] mv zaa.gz zaa ; gzip zaa ; ls -l zaa.gz Jun 03 9:02am
-rwxr-xr-x 1 13692 Jun 1 16:02 zaa.gz
[ 165] mv zaa.gz zaa ; gzip zaa ; ls -l zaa.gz Jun 03 9:02am
-rwxr-xr-x 1 13712 Jun 1 16:02 zaa.gz
[ 166] mv zaa.gz zaa ; gzip zaa ; ls -l zaa.gz Jun 03 9:02am
-rwxr-xr-x 1 13739 Jun 1 16:02 zaa.gz
[ 167] mv zaa.gz zaa ; gzip zaa ; ls -l zaa.gz Jun 03 9:02am
-rwxr-xr-x 1 13766 Jun 1 16:02 zaa.gz
[ 168] mv zaa.gz zaa ; gzip zaa ; ls -l zaa.gz Jun 03 9:02am
-rwxr-xr-x 1 13793 Jun 1 16:02 zaa.gz

实际中持续增大,可能有overhead,gzip
赞科研精神。

增加的很少,可以忽略不计。

应该就是你说的 overhead 增大(不只是对数据要重新编码,还要对overhead 重新编码)的问题,我对gzip (或者其他的实际应用的任何压缩算法)不熟悉,要不大牛来参与讨论一下。
nk
著名点评
著名点评
帖子: 4004
注册时间: 3月 15, 2023, 6:49 am

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

帖子 nk »

其实在软件设计上,可以先试压缩一下,如果不能降低文件长度,可以存原文件,这样就不会增加文件长度。然后header用一个字节来表示这个文件是不是压缩的就可以了。

可是好多的压缩文件的软件(比如gzip) 要做到 FIFO 的 piping 的设计,无法用前面说的那种先把文件扫完的那种小trick.
回复

回到 “STEM”