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

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

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

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

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

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

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

压缩都会存在一个极限。

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

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

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

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

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

码率的极限Shannon's source coding theorem

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

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

@zzh1ad

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

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

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

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

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

（ doge ）

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

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

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

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

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

有点像进制的转换?

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

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

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

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

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

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

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

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

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

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

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

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

@Puteulanus 然后一解压 芜湖

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

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

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

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

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

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

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

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

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

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