理论：压缩算法使某些文件较小但没有更大的文件？
https://stackoverflow.com/questions/1513567
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我遇到了这个问题；
“无损压缩算法声称可以保证使某些文件较小而没有更大的文件。
这是;
a）不可能
b）可能但可能会持续不确定的时间，
c）可能使压缩因子2或更少，
d）可能有任何压缩因子吗？”
我倾向于（a），但不能对原因做出可靠的解释。 （我将列出一个朋友，我想出的是一个可能的答案）
解决方案
根据鸽子孔原理，给定10位的字符串，您有1024个可能的输入，需要映射到9位或更少的位置，因此有<1024个输出。
这可以保证该算法具有碰撞（有损压缩），或者在某个时候选择返回未修改的输入作为输出。
在后一种情况下，您无法确定如何解压缩任意串。 （它可能是未修改的输入，也可能是来自较大位字符串的压缩输出）。
- >不可能。
其他提示
只是对Rjfalconer的帖子有所澄清...
你只需要 一些 文件变得越来越小，因此声称10位必须映射到9位或更少的串并不正确。特别是，如果有人提出了这样的压缩机制 可以 将所有10位或更少的字符串映射到完全相同的输出（即身份转换）。
但是，我们被告知有 至少一个文件 确实变小。在不失去一般性的情况下，请考虑从X位开始，最终以y位最终，其中Y严重小于X。
现在考虑“ y位或更少的文件”的域，其中有2个Y+1-1位弦（包括空字符串）。为了使那些不会导致更大的文件，每个文件都必须映射到同一域中的一个位字符串，即2Y+1-1压缩文件。但是，我们已经知道，长度x位的初始字符串压缩到其中一个值 - 仅留下2Y+1-2可能的值。
在 这个 点鸽子孔原理进来 - 您显然无法映射2Y+1-1输入到2Y+1-2输出而无需重复输出，这违反了压缩的可逆性。
a）不可能
如果您的文件无法进一步压缩，则仍然必须添加该信息是否已被压缩，因此在这种情况下，文件必须增长。
我知道我有点晚了，但是我通过Google找到了这一点，其他人也可以做同样的事情，所以我会发布我的答案：显而易见的解决方案是 a) impossible, 同样，乔恩·斯基特（Jon Skeet）指出（顺便说一句，互联网上都有很多证据）。我并不是在质疑不可能压缩随机数据的可能性，只是从一开始就可以清楚地表明。我理解了在它背后的理论，如果您问我 - 我相信数学。 ：d
但是，如果我们允许 横向思考, ，我们绝对可以利用一个事实，即问题没有明确定义，这意味着它没有对“压缩算法”和应有的属性给出严格的定义（但要减少 一些 文件没有扩展其他任何人）。
另外，它不会在要压缩的文件上放置任何条件，唯一感兴趣的是 “使某些文件较小，没有更大的文件”.
也就是说，我们现在至少有两种方法可以证明它确实存在这样的算法：
我们可以利用文件的名称来存储文件的某些信息（如果文件系统允许的话，则可以将每个文件降低到0位）。琐碎的是，我们可以简单地决定将每个文件都保留不变，只有一个文件将其减少到0位，然后用预定义的名称重命名。我同意这可以被视为作弊，但是话又说回来，最初的问题没有任何限制，这种算法将有效地实现目的（只要没有人重命名文件，这就是为什么这将是一个非常糟糕的设计选择毫无意义）。
我们可以至少将要压缩的文件数量限制为
X长。再次，一个琐碎的解决方案是将每个文件保持不变，但可以使我们可以减少将其与小于文件匹配的匹配X位。现在 我们的确是 具有词语，引用逐字记录，使某些文件较小，没有更大的文件；但是，它对其所有可能输入（即无法处理所有文件）执行限制。
对于那些认为这不会有任何实际用途的人，我说我同意你的看法……但是，这是理论，这只是一个理论论文。 ）
显然，如果我要进行测试并面对这个问题，我会在 a), ，然后继续前进，没有太多考虑。
然而，完全有可能表明，由于自然语言本质上是模棱两可的，而且问题没有正式表达，因此每个其他可能的答案不一定是错误的：放置正确的条件，最终更清楚地指定某些概念的含义，我们可以从法律上能够实现其他列出的选项的目标，进行某种骗局并强迫程序实现所需的行为。
e）可能
...有一些限制。
我最近遇到了 shoco, ，用于小字符串的弦乐压缩库。阅读此说法时，我想起了这个问题：
... Shoco最显着的属性是，只要是普通的ASCII，压缩尺寸将永远不会超过输入字符串的大小。
如果您确定输入数据是普通的ASCII，则您的外部缓冲区只需大大就必须与输入字符串一样大
可能的
to make some files smaller and no files larger
如果所述压缩算法使文件更大，则只需返回原始文件即可。
