“不可压缩的”数据序列

Question

我想通过算法生成 X MB 的“不可压缩”数据序列。我希望这样做是为了创建一个通过 VPN 连接测量网络速度的程序（避免 VPN 内置压缩）。

有人可以帮助我吗？谢谢！

附言。我需要一个算法，我已经使用了一个压缩到无法再压缩的文件，但现在我需要以编程方式从头开始生成数据序列。

Answer 1

白噪声数据是真正随机的，因此不可压缩。

因此，您应该找到一种生成它（或近似值）的算法。

在 Linux 中试试这个：

# dd if=/dev/urandom bs=1024 count=10000 2>/dev/null | bzip2 -9 -c -v > /dev/null
(stdin): 0.996:1, 8.035 bits/byte, -0.44% saved, 10240000 in, 10285383 out.

你可以尝试任何类型的随机数生成......

Answer 2

创建统计上难以压缩的数据的一种简单方法就是使用随机数生成器。如果您需要它可重复，请修复种子。任何相当好的随机数生成器都可以。具有讽刺意味的是，如果您知道随机数生成器，则结果的可压缩性令人难以置信：唯一存在的信息就是种子。然而，它会击败任何真正的压缩方法。

Answer 3

其他答案指出随机噪声是不可压缩的，好的加密函数的输出尽可能接近随机噪声（除非您知道解密密钥）。因此，一个好的方法可能是仅使用随机数生成器或加密算法来生成不可压缩的数据。

真正不可压缩（通过任何压缩算法）的位串是存在的（对于“不可压缩”的某些正式定义），但即使识别它们在计算上也是无法确定的，更不用说生成它们了。

值得指出的是，“随机数据”之所以不可压缩，是因为没有一种压缩算法可以对所有可能的随机数据平均实现优于 1:1 的压缩比。然而，对于任何特定随机生成的字符串，可能有一种特定的压缩算法确实能够实现良好的压缩比。毕竟，任何可压缩字符串都应该可以从随机生成器输出，包括像全零这样的愚蠢的东西，尽管不太可能。

因此，虽然从随机数生成器或加密算法中获取“可压缩”数据的可能性可能微乎其微，但我想在使用数据之前对其进行实际测试。如果您有权访问 VPN 连接中使用的压缩算法，那是最好的；只是随机生成数据，直到得到无法压缩的数据。否则，只需通过一些常见的压缩工具运行它并检查大小是否不会减小可能就足够了。

Answer 4

您有几个选择：
1. 使用合适的伪随机数生成器
2. 使用像 AES 这样的加密函数（随处可见的实现）

Algo

1. 提出您想要的任何密钥。全零就好了。
2. 创建一个空块
3. 使用密钥加密该块
4. 输出该块
5. 如果您需要更多数据，请转到 3

如果操作正确，您生成的数据流在数学上将与随机噪声无法区分。

Answer 5

以下程序（C/POSIX）快速生成不可压缩的数据，它应该在每秒千兆字节的范围内。我确信可以使用一般思想来使其更快（也许使用带有 SIMD 的 Djb 的 ChaCha 核心？）。

/* public domain, 2013 */

#include <stdint.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

#define R(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
static void salsa_scrambler(uint32_t out[16], uint32_t x[16])
{
    int i;
    /* This is a quickly mutilated Salsa20 of only 1 round */
    x[ 4] ^= R(x[ 0] + x[12],  7);
    x[ 8] ^= R(x[ 4] + x[ 0],  9);
    x[12] ^= R(x[ 8] + x[ 4], 13);
    x[ 0] ^= R(x[12] + x[ 8], 18);
    x[ 9] ^= R(x[ 5] + x[ 1],  7);
    x[13] ^= R(x[ 9] + x[ 5],  9);
    x[ 1] ^= R(x[13] + x[ 9], 13);
    x[ 5] ^= R(x[ 1] + x[13], 18);
    x[14] ^= R(x[10] + x[ 6],  7);
    x[ 2] ^= R(x[14] + x[10],  9);
    x[ 6] ^= R(x[ 2] + x[14], 13);
    x[10] ^= R(x[ 6] + x[ 2], 18);
    x[ 3] ^= R(x[15] + x[11],  7);
    x[ 7] ^= R(x[ 3] + x[15],  9);
    x[11] ^= R(x[ 7] + x[ 3], 13);
    x[15] ^= R(x[11] + x[ 7], 18);
    for (i = 0; i < 16; ++i)
        out[i] = x[i];
}

#define CHUNK 2048

int main(void)
{
    uint32_t bufA[CHUNK];
    uint32_t bufB[CHUNK];
    uint32_t *input = bufA, *output = bufB;
    int i;

    /* Initialize seed */
    srand(time(NULL));
    for (i = 0; i < CHUNK; i++)
        input[i] = rand();

    while (1) {
        for (i = 0; i < CHUNK/16; i++) {
            salsa_scrambler(output + 16*i, input + 16*i);
        }
        write(1, output, sizeof(bufA));

        {
            uint32_t *tmp = output;
            output = input;
            input = tmp;
        }
    }
    return 0;
}

Answer 6

一个非常简单的解决方案是生成一个随机字符串，然后对其进行压缩。
已经压缩的文件是不可压缩的。

Answer 7

对于复制粘贴爱好者，这里有一些 C# 代码来生成具有（几乎）不可压缩内容的文件。代码的核心是 MD5 哈希算法，但任何加密性强（最终结果中良好的随机分布）哈希算法都可以完成这项工作（SHA1、SHA256 等）。

它只是使用文件号字节（在我的机器中为 32 位小端序有符号整数）作为哈希函数的初始输入，并重新哈希和连接输出，直到达到所需的文件大小。因此，文件内容是确定性的（相同的数字总是生成相同的输出），对于正在测试的压缩算法来说是随机分布的“垃圾”。

    using System;
    using System.IO;
    using System.Linq;
    using System.Security.Cryptography;

    class Program {
    static void Main( string [ ] args ) {

        GenerateUncompressableTestFiles(
            outputDirectory  : Path.GetFullPath( "." ),
            fileNameTemplate : "test-file-{0}.dat", 
            fileCount        : 10,
            fileSizeAsBytes  : 16 * 1024
        );

        byte[] bytes = GetIncompressibleBuffer( 16 * 1024 );

    }//Main

    static void GenerateUncompressableTestFiles( string outputDirectory, string  fileNameTemplate, int fileCount, int fileSizeAsBytes ) {

       using ( var md5 = MD5.Create() ) {

          for ( int number = 1; number <= fileCount; number++ ) {

              using ( var content = new MemoryStream() ) {

                    var inputBytes = BitConverter.GetBytes( number );

                    while ( content.Length <= fileSizeAsBytes ) {

                        var hashBytes = md5.ComputeHash( inputBytes );
                        content.Write( hashBytes );
                        inputBytes = hashBytes;

                        if ( content.Length >= fileSizeAsBytes ) {
                            var file = Path.Combine( outputDirectory, String.Format( fileNameTemplate, number ) );
                            File.WriteAllBytes( file, content.ToArray().Take( fileSizeAsBytes ).ToArray() );
                        }

                    }//while

               }//using

            }//for

       }//using

    }//GenerateUncompressableTestFiles

    public static byte[] GetIncompressibleBuffer( int size, int seed = 0 ) { 

       using ( var md5 = MD5.Create() ) {

            using ( var content = new MemoryStream() ) {

                var inputBytes = BitConverter.GetBytes( seed );

                while ( content.Length <= size ) {

                    var hashBytes = md5.ComputeHash( inputBytes );
                    content.Write( hashBytes );
                    inputBytes = hashBytes;

                    if ( content.Length >= size ) {
                        return content.ToArray().Take( size ).ToArray();
                    }

                }//while

            }//using

        }//using

        return Array.Empty<byte>();

    }//GetIncompressibleBuffer 


    }//class

Answer 8

我刚刚创建了一个（非常简单且未优化）C# 控制台应用程序，用于创建不可压缩的文件。
它扫描文件夹中的文本文件（扩展名 .txt），并为每个文本文件创建一个具有相同名称和大小的二进制文件（扩展名 .bin）。
希望这对某人有帮助。
这是 C# 代码：

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var files = Directory.EnumerateFiles(@"d:\MyPath\To\TextFile\", "*.txt");
            var random = new Random();
            foreach (var fileName in files)
            {
                var fileInfo = new FileInfo(fileName);
                var newFileName = Path.GetDirectoryName(fileName) + @"\" + Path.GetFileNameWithoutExtension(fileName) + ".bin";
                using (var f = File.Create(newFileName))
                {
                    long bytesWritten = 0;
                    while (bytesWritten < fileInfo.Length)
                    {
                        f.WriteByte((byte)random.Next());
                        bytesWritten++;
                    }
                    f.Close();
                }
            }
        }
    }
}