«несжимаемая» последовательность данных

Question

Я хотел бы сгенерировать «несжимаемую» последовательность данных размером X МБ через алгоритм. Я хочу именно так, чтобы создать программу, которая измеряет скорость сети через VPN-соединение (избегая встроенного сжатия vpn).

Кто-нибудь может мне помочь? Спасибо!

PS. Мне нужен алгоритм, я использовал файл, сжатый до такой степени, что он больше не может быть сжат, но теперь мне нужно сгенерировать последовательность данных с нуля программно.

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. Comeс любым ключом, который вы хотите.Все нули в порядке.
2. Создание пустого блока
3. Шифрование блока с помощью ключа
4. Вывод блока
5. Если вам нужно больше данных, перейдите к 3

Если все сделано правильно, созданный вами поток данных будет математически неотличим от случайного шума.

Answer 5

Следующая программа (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;
}

Answer 6

Очень простое решение - создать случайную строку и затем сжать ее. Уже сжатый файл несжимаемый.

Answer 7

Я только что создал (очень простое и не оптимизированное) консольное приложение 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();
                }
            }
        }
    }
}