理论:压缩算法,使一些文件更小,但没有更大？

Question

我遇到了这个问题;

"无损压缩算法声称保证使一些文件更小,文件更大.
这是;

a)不可能

b)可能但可能运行不确定的时间,

c)压缩系数2或更低可能,

d)可能出现任何压缩因素？"

我倾向于(a),但无法对其原因给出可靠的解释.(我会列出朋友和我想出的想法作为可能的答案)

Answer 1

根据鸽子串原理,给定一个10位的字符串,您有1024个可能的输入,并且需要映射到9位或更少,因此有<1024个输出.

这保证算法具有冲突(有损压缩)或在某些时候选择将未修改的输入作为输出返回.

在后一种情况下,您无法确定如何解压缩任意位串.(它可以是未修改的输入,也可以是来自较大位串的压缩输出).

- >不可能.

Answer 2

只是略微澄清了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输出.