我想通过算法生成 X MBytes 的“不可压缩”数据序列。我想要这样,以便创建一个通过 VPN 连接测量网络速度的程序(避免 vpn 内置压缩)。
有谁能够帮我?谢谢!
PS。我需要一个算法,我使用了一个压缩到无法再压缩的文件,但现在我需要以编程方式从头开始生成数据序列。
我想通过算法生成 X MBytes 的“不可压缩”数据序列。我想要这样,以便创建一个通过 VPN 连接测量网络速度的程序(避免 vpn 内置压缩)。
有谁能够帮我?谢谢!
PS。我需要一个算法,我使用了一个压缩到无法再压缩的文件,但现在我需要以编程方式从头开始生成数据序列。
白噪声数据是真正随机的,因此是不可压缩的。
因此,您应该找到生成它的算法(或近似值)。
在 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.
不过,您可以尝试任何类型的随机数生成...
创建统计上难以压缩的数据的一种简单方法就是使用随机数生成器。如果您需要它是可重复的,请修复种子。任何相当好的随机数生成器都可以。具有讽刺意味的是,如果您知道随机数生成器,结果是非常可压缩的:唯一存在的信息是种子。但是,它将击败任何真正的压缩方法。
其他答案指出随机噪声是不可压缩的,并且良好的加密函数具有尽可能接近随机噪声的输出(除非您知道解密密钥)。因此,一个好的方法可能是只使用随机数生成器或加密算法来生成不可压缩的数据。
存在真正不可压缩(通过任何压缩算法)的位串(对于“不可压缩”的某些正式定义),但即使识别它们在计算上也是无法确定的,更不用说生成它们了。
值得指出的是,“随机数据”只是不可压缩的,因为没有压缩算法可以在所有可能的随机数据上实现平均优于 1:1 的压缩比。然而,对于任何特定的随机生成的字符串,可能存在一个特定的压缩算法,它确实实现了良好的压缩比。毕竟,任何可压缩的字符串都应该可以从随机生成器输出,包括像全零这样的愚蠢的东西,但不太可能。
因此,虽然从随机数生成器或加密算法中获取“可压缩”数据的可能性可能微乎其微,但我希望在使用数据之前对其进行实际测试。如果您可以访问最好的 VPN 连接中使用的压缩算法;只是随机生成数据,直到你得到不会压缩的东西。否则,只需通过一些常见的压缩工具运行它并检查大小没有减小可能就足够了。
你有几个选择: 1. 使用像样的伪随机数生成器 2. 使用像 AES 这样的加密函数(随处可见的实现)
算法
如果操作正确,您生成的数据流在数学上将与随机噪声无法区分。
以下程序(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;
}
一个非常简单的解决方案是生成一个随机字符串,然后对其进行压缩。已经压缩的文件是不可压缩的。
对于复制粘贴爱好者,这里有一些 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
我刚刚创建了一个(非常简单且未优化的)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();
}
}
}
}
}