一个奇怪的压缩算法的问题

[zzh1ad]

想请教一下各位，有没有一种数学方式可以把一个给定的数字转换成一个有一定压缩率的数学公式？例如 1 亿可以表示为 10 的 8 次方。

如果有，那么就可以把一份文件以一个比之前文件小的一个数学公式表示，然后重复这个操作。。。🤣

[thedrwu]

中国在建国大业的时候，乡农在搞信息论。
entropy 了解一下

[c2r5]

我也有过这个想法。但可能会造成，逆向解题（解压缩）时，会有多个答案。

[zzh1ad]

@thedrwu 我的意思是数学公式不包含原始数据，这个公式算出来的结果才是原始数据，就比如说圆周率的前一百万数字

[Puteulanus]

压到最后压成了一个数字，42

[aceralon]

@zzh1ad 所有数据都可以表示为圆周率的某一位到某一位之间的数字了，只是解压可能要花很长时间算 pi

[hahasong]

浮点数不就是这样表示的 IEEE 754 标准

[noe132]

压缩都会存在一个极限。

完美的压缩算法是一个 np-hard 问题，但实际上，就算 p=np ，压缩在多项式时间也是完全无法接受的。现在大多数压缩算法都是线性时间复杂度，而且很多还在这个基础上放弃压缩比例优化执行时间。

[keith1126]

信息论和密码学，非科班出身最缺乏的两门学科，同时也是各种民科造轮子的温床……

老老实实学一下信息论吧。

[flynaj]

现在的无损压缩都是用字典，所以重复内容越多，压缩越高，字典用二叉树来生成。要深入了解的话学点计算机基础。你说问题都是基础知识

[thedrwu]

@zzh1ad #3
公式本身就是被包含的信息

[AkashicRecords]

码率的极限——Shannon's source coding theorem

[Tianao]

恭喜楼主发明了科学记数法和浮点数。

[fkdtz]

压缩不可能无限压缩下去，总会达到一个极限，否则就可以无限套娃把压缩结果再压缩，最后压没了。

[Mohanson]

@zzh1ad

根据信息论, 圆周率提供的信息量是 0.

信息熵是对不确定性的量度, 而圆周率的不确定性为 0.

[adoal]

能用比原值更简短的简单公式来表示的数字串才是特例

[JeffGe]

所有正整数都能用 20 个以内的汉字表达出来，例如 1 亿可以表示为“一后面八个零”或者“十的八次方”。

证明：反证法，假设存在无法用 20 个以内汉字表达出来的数，则必然存在一个最小的不能用 20 个汉字表达出来的数，而这个数已经被“最小的不能用二十个以内的汉字表达的数”表示出来了，矛盾。

（ doge ）

[shuax]

你说这个叫哈希，要文件的时候去服务器取。

[MatDK]

一方面，信息论中定义了压缩的极限。
另一方面，这些“公式”[其实是“码表”]本身就是信息。
举个例字，Computation “计算”这个单词，用英语要 11 个字母，但是中文可能“计算”或者“算”就可以表达出这个意思。原因是，英语本身只有 26 个字母（码表的大小只有 26 ）,而常用汉字就有 3000 多个（码表远大于英语）。

有其他人说到，所有数据都可以表示成圆周率某位到某位的数字，固然你在表示的时候简单，但是这个码表的长度可能是难以估计的。要不花很多时间去计算这个码表，要不大家花海量的存储去存储一个非常长码表。

现在的各种压缩都已经是针对过不同的场景特化过的了。找了一个效率，码表和压缩率的平衡

[yankebupt]

楼主没考虑算法的最差情况
压缩算法的最差情况下结果是比原数据长的。
所以一直不停的压最后会越来越长，而不是趋近于一个最小值

[ClericPy]

有点像进制的转换?

>>> bin(10000000)
'0b100110001001011010000000'
>>> hex(10000000)
'0x989680'

[woctordho]

楼主要考虑的不是 Shannon entropy ，而是 Kolmogorov complexity

[msg7086]

1 亿本来就是 10 的 8 次方，这是同一个东西。

如果用圆周率，当然是可以的，预设圆周率字典。比如压缩软件自带一个 1TB 的字典，然后从字典里找数据来替代压缩，比如一个 10G 的视频可以无损压到 5G 。你只要把这 1029G 数据传给对方就能解压出 10G 的文件来。

[mxT52CRuqR6o5]

@aceralon 开始位置和结束位置的信息量很可能大于原始信息的信息量

[ipwx]

非科班很难理解信息量，不过这里给出一点点小提示：
-----

信息量 = 解码器的信息量 + 编码信息量

而一个具体事物的信息量是固定的。要减少编码后的信息量，就不得不增加解码器的信息量。举个例子，magnet 的种子信息量就只要固定长度的 hash ，压缩率很高对不对？但是如果你把全球所有人的设备都看成是解码器的一部分，你会发现这个解码器的信息量是非常巨大的。换句话说，通过增加解码器的信息量，成功把很多 3GB 的小黄片编码成了几十个字节。

但这种压缩方式还牵扯到另一件事情，哈希冲突。实际上用这种编码方法也无法编码“所有可能的文件”，只不过这套 BT 分布式编码方案只编码“常见的串”（真实出现的小黄片），而不太像正常影片的可能性被抛弃了。这种抛弃造成了解空间全局信息量的巨大下降，使得整个 BT 解码器成为了可能。

[statumer]

这说实话是个初中数学问题，
证明不存在单射 f:X↦Y ，其中 X 和 Y 是有限集且 Y 的元素个数小于 X 的元素个数。

[ETiV]

简单说：任意的不行，特定的可以

比如贝塞尔曲线，就是通过公式来描述一条曲线。如果你对这条曲线采样，采样率越高（对于曲线的描述越精确）数据量就越大。
但只要用公式+参数来表示它，它就是矢量的、精确的，而且数据量比高精度采样要小

[favtony]

前段时间刚好无聊到去想这个问题。没学过信息论，自己去折腾了一下
当时的思路也是用数学公式，各种多次方多项式单项式等。折腾了两天逐渐明白，把一个数字用另一个数字或公式表示之后，源数据与“压缩”后的数据，仍是一一对应关系，这样是没有办法做到压缩的。例如说
​0-63 有 64 个数字，如果你的公式也需要 64 个变化来一一对应的话，那么你还是要用原来一样甚至更多的空间去存储转换后的信息量
用 pi 的方法也有类似的问题，虽然理论上任意数据都能在 pi 里面找到，但是找到之后的表示仍是一一对应的，而且很可能此时偏移量数字本身的长度都大于源数据本身了
​正统的压缩算法，都是在找重复的东西，然后用更少的位数表示。比较简单的有霍夫曼编码，行程长度编码等，可以看看来得到启发 @zzh1ad

[hgert]

@Puteulanus 然后一解压 芜湖

[caixiangyu17]

不要学民科想当然，去学一下压缩需要的算法，先了解一下什么是 entropy ，run-length encoding 和 Huffman tree/Huffman coding ，然后再说怎么做压缩。

[zxCoder]

@keith1126 好家伙 科班表示也没上过这两门课 hhh

[sadfQED2]

软件工程专业毕业，表示也没学过这两门课😂想问问楼上的科班都是啥专业呀

[3dwelcome]

@favtony “例如说 ​0-63 有 64 个数字，如果你的公式也需要 64 个变化来”

这就和 perfect hash 算法一样，构造的公式，可以通过 AI 去预处理数据源来实现。

只所以要 64 个变化，是因为 0~63 出现的概率是相等的，如果数据出现有一定倾向性，那不管怎么样，都是有可能压缩的。

唯一无法压缩的数据流，就是真随机数了。那是真没法预测。

[raptor]

但凡看过一点信息论的科普，也不至于有这种疑问……

[ipwx]

@sadfQED2 信息论基础不需要单独开课。我们学校记得就是大一的“计算机科学导论”里面有一点相关内容。

[caixiangyu17]

@sadfQED2 本科不一定有，毕竟本科教的基础课程更多一些。国外的 coursework 研究生很多就会有压缩相关的课程，我澳洲研究生的时候就学过相关的课程。https://www.handbook.unsw.edu.au/undergraduate/courses/2022/COMP9319?year=2022