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

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

这可以保证算法有冲突(有损压缩),或者在某个时刻选择返回未修改的输入作为输出。

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

->不可能。

只是稍微澄清一下RJFalconer的帖子…

你只需要 一些 文件变小了,所以一个10位的字符串必须映射到9位或更少的说法并不完全正确。尤其是,如果有人提出这样一种压缩机制, 能够 将10位或更少的所有字符串映射到完全相同的输出(即身份转换)。

但是,我们被告知 至少一个文件 它确实变小了。在不失去一般性的情况下,考虑从x位开始,最后是y位,其中y严格小于x。

现在考虑“Y位或更少的文件”的域,它有2个 ^Y+1 -1位字符串(包括空字符串)。为了不让它们产生更大的文件,每个都必须映射到同一域中的一个位字符串,即2 ^Y+1 -1个压缩文件。但是,我们已经知道,长度x位的初始字符串会压缩为这些值中的一个-只剩下2个 ^Y+1 -2个可能值。

AT 这 点鸽子洞原理来了-你显然不能画2 ^Y+1 - 1个输入到2个 ^Y+1 -2个不重复输出的输出,这违反了压缩的可逆性。

a)不可能

如果您有一个文件不能进一步压缩,那么无论它是否被压缩,您仍然需要添加信息,因此在这种情况下,文件必须增长。

我知道我有点晚了,但是我通过谷歌发现了这个,其他人也可以这么做,所以我会发布我的答案:显而易见的解决办法是 a) impossible 乔恩·斯基特也指出(顺便说一句,互联网上有很多证据)。我不是在质疑压缩随机数据的不可能性,只是从一开始就清楚了;我理解它背后的理论,如果你问我的话,我相信数学。D

但是,如果允许的话 think laterally 我们当然可以利用这个问题定义不明确的事实,也就是说,它没有给出“压缩算法”的严格定义,也没有给出它应该具有的属性(但是要减少 一些 不扩展任何其他人的文件)。

而且,它不会对要压缩的文件设置任何条件,它唯一感兴趣的是 “使某些文件变小而没有文件变大” .

也就是说,我们现在至少有两种方法可以证明,事实上,它确实存在这样一种算法:

1. 我们可以利用文件名来存储文件的某些信息(甚至是整个文件,如果文件系统允许的话,也可以这样做,从而将每个文件都减少到0位)。 简单地说,我们可以决定保留除了一个文件以外的所有文件,将其减少到0位并用一个预定义的名称重命名。 我同意这可以被视为作弊,但再次重申,在最初的问题中没有限制,并且该算法将有效地实现目标(只要没有人重命名文件,这就是为什么除了毫无意义之外,这将是一个非常糟糕的设计选择)。

2. 我们可以限制要压缩的文件的数量,比如说,至少限于那些 X 比特长。再一次,一个简单的解决方案是让每个文件都保持原样,只保留一个,这样我们可以减少使其与小于 X 位。 现在 我们做 有一种算法,它逐字引用,使一些文件变小而没有文件变大;但是,它对所有可能的输入执行限制(即它不能处理所有文件)。

对于那些认为这没有任何实际用途的人,我说我同意你的观点…但是,嘿,这是理论,这只是一篇理论论文。;)

显然,如果我要做一个测试并面对这个问题,我会在 a) 然后继续,不要想太多。

然而,我们完全有可能证明,由于自然语言本质上是模棱两可的,而且问题没有正式表达,其他可能的答案并不一定都是错误的:设置正确的条件,最终更清楚地说明某些概念的含义,我们在法律上可能满足GoA的要求。l任何其他列出的选项,做一些欺骗和强迫程序实现所需的行为。

e)可能

…有一些限制。

我最近遇到 Shoco 一个用于小字符串的字符串压缩库。在阅读此声明时,我想起了这个问题:

…Shoco最显著的特性是,压缩后的大小永远不会超过输入字符串的大小,前提是它是纯ASCII。

如果您确定输入数据是纯ASCII,则您的输出缓冲区只需要与输入字符串一样大。

http://ed-von-schleck.github.io/shoco/#how-it-works

可能的

to make some files smaller and no files larger

如果所说的压缩算法使文件变大,就让它返回原始文件。