algorithm - 当今广泛使用的压缩算法上的不动点

Question

我想知道是否有一种今天常用的压缩算法，它包含一个固定点，即一个身份文件。

为了解释，让我们调用C : byte[] -> byte[]一个表示压缩算法的函数。我想知道是否存在（以及它是什么，如果可以在合理的时间内确定）f这样的文件

C(f) = f

也就是说，当通过当今常用的合适的、广为人知的压缩算法压缩时，文件将作为结果生成自身。

你知道这样的现象吗？

Answer 1

是的！这是quine问题的一个变体。

1. 使用gzip的示例： http ://groups.google.com/group/comp.compression/browse_thread/thread/c57c322e15c782aa/350d9fb166fdf11f

2. 使用zip/unzip的示例：http : //www.steike.com/code/useless/zip-file-quine/

Answer 2

警告：相当迂腐的答案。

在很多情况下，D(f) = f（D 被定义为减压）。但是，压缩的定义并不精确。对于大多数压缩算法，压缩算法的不同实现会给出不同的输出文件（大小不同）。考虑两个程序，1 和 2。对于完全互操作性，对于所有有效 F，D1(F) 必须等于 D2(F)。类似地，D2(C2(f)) == D2(C1( F)) == D1(C1(F)) == D1(C2(F))，对于所有有效的 F。但是完全没有必要 C1(F) == C2(F)，这实际上很少见案子。

因此，如果您实际压缩此类 quines，则不太可能最终得到相同的文件，除非您使用用于生成它的相同程序来执行此操作（这不太可能，因为此类 quines 通常是手工制作的, C(F) 甚至从未被测试过)。

虽然可以（实际上，微不足道！）为某些 F 生成 C(F) == F 的程序，但大多数人倾向于将 D(F) == F 的更明确的情况指出为 quines （因为 D1(F)==D2(F) 对于所有有效的、兼容的 F 格式的解压缩，假设 F 是有效的）。

因此，可能存在 C(F) == F 的情况，但通常这是错误的问题，您应该询问 D(F) == F 的情况......其他回答问题的人已提供。