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

[zzh1ad]

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

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

[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