我遇到了这个问题；
“一种无损压缩算法，号称保证让一些文件变小，不让文件变大。
是这样的吗？
a) 不可能
b) 可能，但可能运行不确定的时间，
c) 压缩系数为 2 或更低时可能，
d) 任何压缩系数都可能吗？”
我倾向于（a），但无法给出一个可靠的解释。（我会列出一个朋友的想法，我想出一个可能的答案）
问问题
1631 次
6 回答
14
根据鸽子洞原理，给定一个 10 位的字符串，您有 1024 个可能的输入，并且需要映射到 9 位或更少，因此有 < 1024 个输出。
这保证了算法有冲突（有损压缩）或在某些时候选择将未修改的输入作为输出返回。
在后一种情况下，您无法确定如何解压缩任意位串。（它可能是未修改的输入，也可能是来自较大位串的压缩输出）。
-> 不可能。
于 2009-10-03T11:58:25.807 回答
10
只是稍微澄清一下 RJFalconer 的帖子......
您只需要让一些文件变得更小，因此声称一个 10 位的字符串必须映射到 9 位或更少的说法并不完全正确。特别是，如果有人提出这种压缩机制，它可以将所有 10 位或更少的字符串映射到完全相同的输出（即恒等转换）。
但是，我们被告知至少有一个文件确实变小了。不失一般性，考虑以 x 位开始并以 y 位结束，其中 y 严格小于 x。
现在考虑“y 位或更少的文件”的域，它有 2 个y+1 -1 位字符串（包括空的）。为了使这些都不会产生更大的文件，每个都必须映射到同一域中的位字符串，即 2 y+1 -1 个压缩文件。但是，我们已经知道长度为 x 位的初始字符串压缩为其中一个值 - 仅留下 2 y+1 -2 个可能的值。
此时鸽洞原理就出现了——你显然不能在不重复输出的情况下将 2 y+1 -1 输入映射到 2 y+1 -2 输出，这违反了压缩的可逆性。
于 2009-10-03T12:12:47.850 回答
0
a) 不可能
如果您有一个无法进一步压缩的文件，您仍然需要添加是否已压缩的信息，因此在这种情况下，文件将不得不增长。
于 2009-10-03T12:48:46.500 回答
0
我知道我有点晚了，但我通过谷歌找到了这个，其他人也可以这样做，所以我会发布我的答案：显而易见的解决方案是a) impossible，正如 Jon Skeet 所指出的那样（顺便说一句，有很多证据遍布互联网）。我不是在质疑压缩随机数据的可能性，只是从一开始就清楚；我理解它背后的理论，而且——如果你问我——我相信数学。: D
但是，如果我们被允许横向思考，我们绝对可以利用这个问题没有明确定义的事实，这意味着它没有对“压缩算法”和它应该具有的属性给出严格的定义（但要减少一些文件而不扩展其他任何人）。
此外，它对要压缩的文件没有任何条件，它唯一感兴趣的是“使一些文件更小，而不是让文件更大”。
也就是说，我们现在至少有两种方法可以证明，事实上，它确实存在这样的算法：
我们可以利用文件名来存储文件的一些信息（甚至整个文件，如果文件系统允许的话，从而将每个文件减少到0位）。简单地说，我们可以简单地决定除了一个文件之外的每个文件都保持不变，将其减少到 0 位并用预定义的名称重命名它。我同意这可以被认为是作弊，但话又说回来，最初的问题没有任何限制，并且该算法将有效地达到目的（只要没有人重命名文件，这就是为什么这将是一个非常糟糕的设计选择毫无意义）。
我们可以限制要压缩的文件的数量，例如，至少是
X位长的文件。再一次，一个简单的解决方案是让每个文件都保持不变，但我们可以减少使其与小于X位的文件匹配。现在我们确实有一个算法，逐字引用，使一些文件变小而没有文件变大；但是，它会对所有可能的输入进行限制（即它不能处理所有文件）。
对于那些认为这没有任何实际用途的人，我说我同意你的看法……但是，嘿，这是理论，这只是一篇理论论文。;)
显然，如果我要做一个测试并面对这个问题，我会在 上加上一个粗体 X a)，然后继续进行而不用想太多。
然而，完全有可能表明，由于自然语言本质上是模棱两可的，并且问题没有正式表达，其他每个可能的答案都不一定是错误的：放置正确的条件并最终更清楚地说明某些概念的含义，我们可以合法地实现任何其他列出的选项的目标，做一些诡计并强制程序实现所需的行为。
于 2014-09-19T01:07:24.523 回答
0
可能的
to make some files smaller and no files larger
如果所述压缩算法使文件变大，则让它返回原始文件。
于 2018-08-18T19:58:13.247 回答
0
e) 可能的
...有一些限制。
我最近遇到了Shoco，一个用于小字符串的字符串压缩库。阅读此声明时，我想起了这个问题：
... shoco 最显着的特性是压缩后的大小永远不会超过输入字符串的大小，只要它是纯 ASCII 码。
如果您确定输入数据是纯 ASCII，那么您的输出缓冲区只需与输入字符串一样大
于 2017-06-07T08:44:11.830 回答