假设数学表达式的字符数少于原始数。例子-
20880467999847912034355032910578 可以表示为 (23^23 +10)
这看起来是一种很好的压缩方法。它适用于压缩大文件吗？
更新-我并不是说将文件转换为大二进制数。假设我有一个文本文件，我用它们的 ascii 值替换其中的所有字符。现在我在十进制数字系统中有一个很大的数字。我可以将其表示为上面示例中的数学表达式。
问问题
353 次
3 回答
5
如果您将文件的内容作为一个大二进制数，并找到一个计算结果为该数字的表达式，并且可以比数字本身更紧凑地存储，那么是的，您已经压缩了文件。
不幸的是，对于大多数文件，您永远找不到这样的表达式。
简单的逻辑（请参阅@OliCharlesworth 发布的链接）应该让您相信，不可能为所有甚至大多数文件找到这样的表达式。即使对于可能具有合适表达的文件，找到它也将非常非常困难。如果您想说服自己相信这一点，请尝试以下挑战：
取以下 ASCII 字符串：
“天哪，Kolmogorov 的复杂性，蝙蝠侠！把这个傻瓜压下去，你会得到一大笔钱，我的好孩子！”
Interpreted as a binary number, with the high-order digits coming first, that is: 2280899635869589768629811602006623364651019118009864206881173103187172975244099647369151382436996220022807793898568915685059542016541775658916080587423284053601554008368389985872997499032440860090224967472423163775276043175694884234152335588829534778866153948275745.
尝试找到一个计算结果为该数字的多项式。所有使用的数字必须是整数，并且多项式中出现的小数位数总和必须小于80。如果成功，我将通过PayPal向您发送小额现金奖励。
于 2013-10-20T20:36:43.193 回答
5
您正在寻找的概念是 Kolmogorov 复杂性 - 它衡量一个数字在算法上的不可压缩程度。有关此类数字的严格定义和示例，请参阅此 wiki 文章。
于 2013-10-20T20:37:17.170 回答
0
是的，根据定义。您已经正确地将压缩定义为用较小的东西表示较大的东西。
你打算如何做到这一点？这多久会起作用？问题就在这里。
于 2013-10-20T22:40:05.653 回答