4
一个奇怪的压缩算法的问题
source link: https://www.v2ex.com/t/845022
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
想请教一下各位，有没有一种数学方式可以把一个给定的数字转换成一个有一定压缩率的数学公式？例如 1 亿可以表示为 10 的 8 次方。
如果有，那么就可以把一份文件以一个比之前文件小的一个数学公式表示，然后重复这个操作。。。🤣
26 条回复 • 2022-04-06 00:32:35 +08:00
2
noe132 9 小时 53 分钟前 via Android
压缩都会存在一个极限。
完美的压缩算法是一个 np-hard 问题，但实际上，就算 p=np ，压缩在多项式时间也是完全无法接受的。现在大多数压缩算法都是线性时间复杂度，而且很多还在这个基础上放弃压缩比例优化执行时间。
完美的压缩算法是一个 np-hard 问题，但实际上，就算 p=np ，压缩在多项式时间也是完全无法接受的。现在大多数压缩算法都是线性时间复杂度，而且很多还在这个基础上放弃压缩比例优化执行时间。
JeffGe 5 小时 18 分钟前
所有正整数都能用 20 个以内的汉字表达出来，例如 1 亿可以表示为“一后面八个零”或者“十的八次方”。
证明：反证法，假设存在无法用 20 个以内汉字表达出来的数，则必然存在一个最小的不能用 20 个汉字表达出来的数，而这个数已经被“最小的不能用二十个以内的汉字表达的数”表示出来了，矛盾。
（ doge ）
证明：反证法，假设存在无法用 20 个以内汉字表达出来的数，则必然存在一个最小的不能用 20 个汉字表达出来的数，而这个数已经被“最小的不能用二十个以内的汉字表达的数”表示出来了，矛盾。
（ doge ）
MatDK 4 小时 53 分钟前
一方面，信息论中定义了压缩的极限。
另一方面，这些“公式”[其实是“码表”]本身就是信息。
举个例字，Computation “计算”这个单词，用英语要 11 个字母，但是中文可能“计算”或者“算”就可以表达出这个意思。原因是，英语本身只有 26 个字母（码表的大小只有 26 ）,而常用汉字就有 3000 多个（码表远大于英语）。
有其他人说到，所有数据都可以表示成圆周率某位到某位的数字，固然你在表示的时候简单，但是这个码表的长度可能是难以估计的。要不花很多时间去计算这个码表，要不大家花海量的存储去存储一个非常长码表。
现在的各种压缩都已经是针对过不同的场景特化过的了。找了一个效率，码表和压缩率的平衡
另一方面，这些“公式”[其实是“码表”]本身就是信息。
举个例字，Computation “计算”这个单词，用英语要 11 个字母，但是中文可能“计算”或者“算”就可以表达出这个意思。原因是，英语本身只有 26 个字母（码表的大小只有 26 ）,而常用汉字就有 3000 多个（码表远大于英语）。
有其他人说到，所有数据都可以表示成圆周率某位到某位的数字，固然你在表示的时候简单，但是这个码表的长度可能是难以估计的。要不花很多时间去计算这个码表，要不大家花海量的存储去存储一个非常长码表。
现在的各种压缩都已经是针对过不同的场景特化过的了。找了一个效率，码表和压缩率的平衡
ClericPy 3 小时 59 分钟前
有点像进制的转换?
>>> bin(10000000)
'0b100110001001011010000000'
>>> hex(10000000)
'0x989680'
>>> bin(10000000)
'0b100110001001011010000000'
>>> hex(10000000)
'0x989680'
msg7086 1 小时 6 分钟前
1 亿本来就是 10 的 8 次方，这是同一个东西。
如果用圆周率，当然是可以的，预设圆周率字典。比如压缩软件自带一个 1TB 的字典，然后从字典里找数据来替代压缩，比如一个 10G 的视频可以无损压到 5G 。你只要把这 1029G 数据传给对方就能解压出 10G 的文件来。
如果用圆周率，当然是可以的，预设圆周率字典。比如压缩软件自带一个 1TB 的字典，然后从字典里找数据来替代压缩，比如一个 10G 的视频可以无损压到 5G 。你只要把这 1029G 数据传给对方就能解压出 10G 的文件来。
ipwx 43 分钟前
非科班很难理解信息量，不过这里给出一点点小提示：
-----
信息量 = 解码器的信息量 + 编码信息量
而一个具体事物的信息量是固定的。要减少编码后的信息量，就不得不增加解码器的信息量。举个例子，magnet 的种子信息量就只要固定长度的 hash ，压缩率很高对不对？但是如果你把全球所有人的设备都看成是解码器的一部分，你会发现这个解码器的信息量是非常巨大的。换句话说，通过增加解码器的信息量，成功把很多 3GB 的小黄片编码成了几十个字节。
但这种压缩方式还牵扯到另一件事情，哈希冲突。实际上用这种编码方法也无法编码“所有可能的文件”，只不过这套 BT 分布式编码方案只编码“常见的串”（真实出现的小黄片），而不太像正常影片的可能性被抛弃了。这种抛弃造成了解空间全局信息量的巨大下降，使得整个 BT 解码器成为了可能。
-----
信息量 = 解码器的信息量 + 编码信息量
而一个具体事物的信息量是固定的。要减少编码后的信息量，就不得不增加解码器的信息量。举个例子，magnet 的种子信息量就只要固定长度的 hash ，压缩率很高对不对？但是如果你把全球所有人的设备都看成是解码器的一部分，你会发现这个解码器的信息量是非常巨大的。换句话说，通过增加解码器的信息量，成功把很多 3GB 的小黄片编码成了几十个字节。
但这种压缩方式还牵扯到另一件事情，哈希冲突。实际上用这种编码方法也无法编码“所有可能的文件”，只不过这套 BT 分布式编码方案只编码“常见的串”（真实出现的小黄片），而不太像正常影片的可能性被抛弃了。这种抛弃造成了解空间全局信息量的巨大下降，使得整个 BT 解码器成为了可能。
ETiV 28 分钟前 via iPhone
简单说：任意的不行，特定的可以
比如贝塞尔曲线，就是通过公式来描述一条曲线。如果你对这条曲线采样，采样率越高（对于曲线的描述越精确）数据量就越大。
但只要用公式+参数来表示它，它就是矢量的、精确的，而且数据量比高精度采样要小
比如贝塞尔曲线，就是通过公式来描述一条曲线。如果你对这条曲线采样，采样率越高（对于曲线的描述越精确）数据量就越大。
但只要用公式+参数来表示它，它就是矢量的、精确的，而且数据量比高精度采样要小
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK