我想知道压缩算法是否总是为两组不同的文件生成唯一的输出。
假设我有两个文件 A 和 B，并假设我正在为每个文件应用压缩算法（例如 PKZIP - 这可以是任何压缩算法）以分别获取 A.zip 和 B.zip。对于 A 和 B 的某种组合，A.zip 是否有可能在二进制级别与 B.zip 完全相同？如果这不可能，我们可以安全地假设压缩等同于加密散列，以保证唯一性? 另一方面，如果可能的话，您能否提供一个样本 A 和 B 文件以及用于验证这种重复性的压缩算法？
问问题
2016 次
10 回答
21
无损压缩（在 ZIP 文件中使用）总是会为不同的文件产生不同的输出 - 否则您将无法可靠地恢复原始数据。但是，输出数据可以是任意大小 - 对于某些输入，它会大于原始输入。因此，这作为散列通常不是很有用，散列通常需要固定大小的输出。
有损压缩（例如，MP3、JPEG 等）可以为不同的输入产生相同的输出 - 因此，您无法恢复原始数据，而是得到类似的东西。正因为如此，鸽笼原理不是问题，因此您可以保证它会减小输出大小，通常甚至指定所需的输出大小。然而，因为相似但略有不同的输入通常会产生相同的输出，所以这对于散列也没有用，因为散列需要输入的微小变化才能产生输出的大变化。
于 2009-07-17T19:00:21.983 回答
14
这不可能。如果压缩文件是相同的，当你解压它们时，它们怎么会产生不同的结果呢？
于 2009-07-17T18:58:45.713 回答
3
当然，有损压缩可以提供与已经提到的相同的输出。
但我认为没有提到的一个非常重要的一点是加密哈希应该很难反转（或通过两个不同的输入重现相同的哈希）。出于这个原因，像 zips 这样的无损且因此可逆的压缩算法将不适合作为加密哈希。
于 2009-07-17T19:12:19.087 回答
2
令f为压缩算法。如果压缩A并B产生相同的文件，则f(A) = f(B) = C，对于某些C。现在，设f'为解压缩算法。然后f'(f(A)) = f'(C) = f'(f(B))。因此，f'解压缩A.zip到B.zip同一个文件。
因此，要么f是一个毫无价值的压缩算法（因为它不是双射），要么A实际上B是同一个文件。（当我说无价值时，我的意思是无损压缩毫无价值！）
至于您的另一个问题，请注意无损压缩算法根据定义不是散列算法，因为散列函数h将域A映射到（通常）较小的域B上。因此h 不能是双射，而我们只是断言我们的无损压缩函数f 是双射。
于 2009-07-17T19:02:42.540 回答
1
应该很明显：如果压缩文件是相同的，那么解压缩器怎么知道是制作 A 还是 B 出来？
但是，这不会产生可用的哈希，因为长度是可变的。
于 2009-07-17T19:00:19.610 回答
1
压缩函数需要是单射的，即每个输入映射到一个唯一的输出。如果这不是真的，那么算法如何知道是解压回 A 还是 B？
请注意，这仅适用于无损（数据）压缩。例如，可以压缩 2 个图像并获得相同的结果，但前提是图像开始时非常接近。
于 2009-07-17T19:00:54.727 回答
1
好吧，您的问题有点笼统，但是由于您指出了基于文件的压缩算法（一件事是您的 pkzip 标记），所以没有。两种不同的无损压缩算法不可能从不同的输入产生相同的输出。
但是，对于像JPEG这样的有损压缩算法，当然，这当然是一种可能性，但是文件一开始就几乎相同。
例如，获取一个 .PNG 文件，将其另存为 .JPEG，更改一个像素使其在一个通道中变亮或变暗 1 度，将其重新另存为 .JPEG，您就有机会得到两个相同的文件，即使输入不同，尽管略有不同。
所以无损算法，不，这不可能发生。对于有损算法，是的。
于 2009-07-17T19:01:08.767 回答
1
加密散列函数有一个非常具体的要求：使它们很难反转。根据定义，压缩很容易反转，因此对于加密哈希来说它是一个非常糟糕的选择。
编辑：
请注意，当我在上面说“按定义”时，我指的是传统定义。严格来说，MD5、SHA-1 等也可以被认为是压缩算法。
于 2009-07-17T19:16:17.927 回答
0
对于一个像样的加密散列算法来说，输入的一个小的局部变化应该会导致输出的一个大的分散变化。此外，哈希函数是从任意大小的输入到固定大小的输出的映射。
于 2009-07-17T19:30:24.013 回答