随机字节数组可以解压缩吗？会使用什么算法？

Question

我可以将任何字节数组插入到像 Lempel-Ziv 这样的压缩算法中，然后我将得到一个无损压缩的字节数组。我可以再解压一下。

但是有没有一种算法可以解压缩任何随机字节数组呢？ 我尝试使用 gzip，但返回错误

System.IO.InvalidDataException: 'The archive entry was compressed using an unsupported compression method.'

结果会怎样？ 它会是随机的，但具有重复的模式吗？ 让我知道你的想法！

哦，顺便说一句，这是我使用的代码：

public class Compresser
{
    public static string CompressString(string text)
    {
        byte[] byteArray = Encoding.UTF8.GetBytes(text);

        using (MemoryStream memoryStream = new MemoryStream())
        {
            using (GZipStream gzipStream = new GZipStream(memoryStream, CompressionMode.Compress))
            {
                gzipStream.Write(byteArray, 0, byteArray.Length);
            }

            return Convert.ToBase64String(memoryStream.ToArray());
        }
    }

    public static string DecompressString(string compressedText)
    {
        byte[] byteArray = Convert.FromBase64String(compressedText);

        using (MemoryStream memoryStream = new MemoryStream(byteArray))
        {
            using (GZipStream gzipStream = new GZipStream(memoryStream, CompressionMode.Decompress))
            {
                using (MemoryStream decompressedStream = new MemoryStream())
                {
                    gzipStream.CopyTo(decompressedStream);
                    byte[] decompressedBytes = decompressedStream.ToArray();
                    return Encoding.UTF8.GetString(decompressedBytes);
                }
            }
        }
    }
}

    public class Base64RandomFiller
    {
        private static Random random = new Random();

        public static string GenerateRandomBase64String(int length)
        {
            byte[] randomBytes = new byte[(length * 3) / 4];
            using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
            {
                rng.GetBytes(randomBytes);
            }
            return Convert.ToBase64String(randomBytes);
        }
    }

string randomBase64String = Base64RandomFiller.GenerateRandomBase64String(10);
Console.WriteLine("Random String: " + randomBase64String);

Thread.Sleep(1000);

string decompressedRandomString = Compresser.DecompressString(randomBase64String);
Console.WriteLine("Decompressed Random String: " + decompressedRandomString);

Answer 1

对于 gzip，没有。如果你向它提供随机数据，即使你偶然通过了标头，你最终也会遇到无效的压缩数据，几乎肯定会如此。

当然，随机生成有效的 gzip 流是可能的，但概率微乎其微。这种流最短为 20 字节，其中 42 位实际上可以是任何值，剩下 118 位为单个值。如果生成 20 个随机字节，则有 2^-118 ~ 3x10^-36 的概率它将是有效的 gzip 流。

大多数常用解压缩器都是如此，所有解压缩器都限制了可能的有效比特流集。例如。 xz、zstd、lz4 等。即使您从有效的标头开始，然后从那里向它们提供随机字节，它们最终也会几乎确定地检测到无效数据。即使您以某种方式生成了有效的压缩数据，您也需要通过 32 或 64 位完整性检查。

可以编写一个双射压缩器/解压缩器，其中所有可能的比特流都是有效的。原则上，利用所有可能的压缩比特流可以最大限度地提高压缩效率。然而，与您为改进压缩所做的其他事情相比，这种特定的最大化是无关紧要的，因此您不会发现任何常用的双射压缩器/解压缩器。但它们已经被写下来了。您可以在保存在 Wayback Machine 中的不再出现的网页上找到更多信息。 （考虑向他们捐款。）

对于与加密一起使用的双射压缩器/解压缩器存在争议。然后，仅压缩数据就不会受到纯文本攻击，因为所有比特流都是有效的。然而，在现实世界中，只需在压缩数据之前添加一串随机数据即可解决这个问题。

Brotli 是我所见过的最接近能够解压缩常用随机数据的工具。如果没有标头或完整性检查，则它的随机数据有效概率比此处提到的其他数据高得多。请参阅这个答案，了解为什么随机生成正确的 Brotli 压缩数据的几率约为 5%。