Я хотел бы с помощью алгоритма сгенерировать "несжимаемую" последовательность данных размером X МБ. Я хочу, чтобы это было так, чтобы создать программу, которая измеряет скорость сети через 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. Используйте приличный генератор псевдослучайных чисел 2. Используйте функцию шифрования, такую как AES (реализации можно найти повсюду).
Алго
Если все сделано правильно, генерируемый поток данных будет математически неотличим от случайного шума.
В других ответах указывалось, что случайный шум несжимаем, и хорошие функции шифрования имеют вывод, максимально приближенный к случайному шуму (если вы не знаете ключ дешифрования). Таким образом, хорошим подходом может быть использование генераторов случайных чисел или алгоритмов шифрования для генерации ваших несжимаемых данных.
Подлинно несжимаемые (с помощью любого алгоритма сжатия) существуют цепочки битов (для некоторых формальных определений «несжимаемого»), но даже распознать их невозможно с вычислительной точки зрения, не говоря уже о том, чтобы их генерировать.
Однако стоит отметить, что «случайные данные» несжимаемы только потому, что не существует алгоритма сжатия, который мог бы достичь степени сжатия лучше 1: 1 в среднем по всем возможным случайным данным. Однако для любой конкретной случайно сгенерированной строки может существовать определенный алгоритм сжатия, который действительно обеспечивает хорошую степень сжатия. В конце концов, любая сжимаемая строка должна быть возможна на выходе из генератора случайных чисел, включая такие глупые вещи, как все нули, хотя и маловероятные.
Таким образом, хотя возможность получения «сжимаемых» данных из генератора случайных чисел или алгоритма шифрования, вероятно, исчезающе мала, я бы действительно хотел протестировать данные, прежде чем использовать их. Если у вас есть доступ к алгоритмам сжатия, используемым в VPN-соединении, это будет лучше всего; просто генерируйте данные случайным образом, пока не получите то, что не сжимается. В противном случае, вероятно, будет достаточно просто запустить его с помощью нескольких распространенных инструментов сжатия и проверить, не уменьшается ли размер.
Следующая программа (C / POSIX) производит несжимаемые данные быстро, это должно быть в диапазоне гигабайт в секунду. Я уверен, что можно использовать общую идею, чтобы сделать это еще быстрее (возможно, используя ядро Djb ChaCha с SIMD?).
/* 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-битное целое число со знаком endian на моей машине) в качестве начального ввода хеш-функции и повторно хеширует и объединяет выходные данные до тех пор, пока не будет достигнут желаемый размер файла. Таким образом, содержимое файла является детерминированным (одно и то же число всегда генерирует один и тот же результат), случайно распределенный «мусор» для тестируемого алгоритма сжатия.
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();
}
}
}
}
}
Очень простое решение - сгенерировать случайную строку, а затем сжать ее. Уже сжатый файл несжимаем.
