理论：压缩算法，使一些文件较小，但没有更大？ [英] Theory: Compression algorithm that makes some files smaller but none bigger?

问题描述

我遇到了这个问题;

无损压缩算法声称保证使一些文件更小，没有文件更大。

this;

"A lossless compression algorithm claims to guarantee to make some files smaller and no files larger.
Is this;

a）不可能

a) Impossible

b）不确定的时间量，

b) Possible but may run for an indeterminate amount of time,

c）可能压缩系数为2或更小，

c) Possible for compression factor 2 or less,

d）压缩因子？

我倾向于（a），但不能给出解释为什么。 （我会列出一个朋友的想法，我想出了一个可能的答案）

I'm leaning towards (a), but couldn't give a solid explanation as to why. (I'll list the thoughts a friend and I came up with as a possible answer)

推荐答案

，给定10位的字符串，你有1024个可能的输入，并且需要映射到9位或更少， 1024个输出。

By the pigeon-hole principle, given a string of 10 bits you have 1024 possible inputs, and need to map to 9 bits or fewer, so there are < 1024 outputs.

这保证算法具有冲突（有损压缩），或者在某些点选择将未修改的输入作为输出返回。

This guarantees either the algorithm has collisions (lossy compression) or at some point choses to return the unmodified input as output.

在后一种情况下，您无法确定如何解压缩任意位串。 （它可以是未修改的输入，或者是来自较大位串的压缩输出）。

In the latter case, you cannot determine how to decompress an arbitrary string of bits. (It could be an unmodified input, or a compressed output from a larger bit string).

- >不可能。

这篇关于理论：压缩算法，使一些文件较小，但没有更大？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！