代码之家 › 专栏 › 技术社区 › Bruno Reis

不动点压缩算法是目前广泛使用的一种压缩算法

fixed-point compression algorithm

6

Bruno Reis · 技术社区 · 17 年前

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

为了解释,我们打电话吧 C : byte[] -> byte[] f 以致

C(f) = f

你知道这种现象吗?

2 回复 | 直到 17 年前

1

4

ire_and_curses 17 年前

对这是计算机上的一个变体 quine 问题

2

3

Brian 17 年前

警告:答案相当迂腐。

在许多情况下,D(f)=f(D被定义为解压缩)。然而,压缩的定义并不精确。对于大多数压缩算法,压缩算法的不同实现将给出不同的输出文件(大小不同)。考虑两个程序,1和2。对于完全互操作性,对于所有有效的F,D1(F)必须等于D2(F)。类似地,对于所有有效的F,D2(C2(F))==D2(C1(F))==D1(C1(F))==D1(C2(F))。然而,C1(F)==C2(F)是完全不必要的,事实上很少如此。

因此,如果你真的压缩了这样的奎因,你不太可能得到相同的文件,除非你使用了生成它的相同程序(这是不可能的,因为这样的奎因通常是手工制作的,C(F)甚至从未被测试过)。

虽然有可能(事实上是微不足道的!)生成一个程序,其中C(F)=F对于某些F,大多数人倾向于指出更明确的情况,其中D(F)=F(因为D1(F)==D2(F)对于F格式的所有有效、兼容的解压缩,假设F是有效的)。

所以,可能有C(F)=F的情况,但通常这是一个错误的问题,你应该问D(F)==F的情况,其他回答问题的人都提供了。