C ++ генератор случайных чисел с предоставленной (по крайней мере оценочной) энтропией
Используя стандартный генератор случайных чисел C ++, я могу более или менее эффективно создавать последовательности с предопределенными распределениями, используя предоставляемые языком инструменты. Как насчет энтропии Шеннона? Можно ли каким-то образом определить выходную энтропию Шеннона для заданной последовательности?
Я попытался провести небольшой эксперимент, сгенерировал достаточно длинную последовательность с линейным распределением и внедрил калькулятор энтропии Шеннона. Результирующее значение от 0,0 (абсолютный порядок) до 8,0 (абсолютный хаос)
template <typename T>
double shannon_entropy(T first, T last)
{
size_t frequencies_count{};
double entropy = 0.0;
std::for_each(first, last, [&entropy, &frequencies_count] (auto item) mutable {
if (0. == item) return;
double fp_item = static_cast<double>(item);
entropy += fp_item * log2(fp_item);
++frequencies_count;
});
if (frequencies_count > 256) {
return -1.0;
}
return -entropy;
}
std::vector<uint8_t> generate_random_sequence(size_t sequence_size)
{
std::vector<uint8_t> random_sequence;
std::random_device rnd_device;
std::cout << "Random device entropy: " << rnd_device.entropy() << '\n';
std::mt19937 mersenne_engine(rnd_device());
std::uniform_int_distribution<unsigned> dist(0, 255);
auto gen = std::bind(dist, mersenne_engine);
random_sequence.resize(sequence_size);
std::generate(random_sequence.begin(), random_sequence.end(), gen);
return std::move(random_sequence);
}
std::vector<double> read_random_probabilities(size_t sequence_size)
{
std::vector<size_t> bytes_distribution(256);
std::vector<double> bytes_frequencies(256);
std::vector<uint8_t> random_sequence = generate_random_sequence(sequence_size);
size_t rnd_seq_size = random_sequence.size();
std::for_each(random_sequence.begin(), random_sequence.end(), [&](uint8_t b) mutable {
++bytes_distribution[b];
});
std::transform(bytes_distribution.begin(), bytes_distribution.end(), bytes_frequencies.begin(),
[&rnd_seq_size](size_t item) {
return static_cast<double>(item) / rnd_seq_size;
});
return std::move(bytes_frequencies);
}
int main(int argc, char* argv[]) {
size_t sequence_size = 1024 * 1024;
std::vector<double> bytes_frequencies = read_random_probabilities(sequence_size);
double entropy = shannon_entropy(bytes_frequencies.begin(), bytes_frequencies.end());
std::cout << "Sequence entropy: " << std::setprecision(16) << entropy << std::endl;
std::cout << "Min possible file size assuming max theoretical compression efficiency:\n";
std::cout << (entropy * sequence_size) << " in bits\n";
std::cout << ((entropy * sequence_size) / 8) << " in bytes\n";
return EXIT_SUCCESS;
}
Во-первых, кажется, что std::random_device::entropy() жестко return 32; в MSVC 2015 (что, вероятно, 8,0 в соответствии с определением Шеннона). Как вы можете убедиться, это не далеко от истины, этот пример всегда близок к 7.9998 …, то есть абсолютному хаосу.
Рабочий пример включен IDEONE (кстати, энтропия их жесткого компилятора равна 0)
Еще один главный вопрос — можно ли создать такой генератор, который генерирует линейно-распределенную последовательность с определенный энтропия, скажем, от 6,0 до 7,0? Может ли это быть реализовано вообще, и если да, если есть какие-то реализации?
Решение
Во-первых, вы рассматриваете теорию Шеннона совершенно неправильно. Его аргумент (как вы его используете) просто «учитывая, вероятно, x (Pr(x)), биты, необходимые для хранения x является -log2 Pr(x), Это не имеет ничего общего с вероятностью x, В связи с этим, вы просматриваете Pr(x) неправильно. -log2 Pr(x) учитывая Pr(x) это должно быть равномерно 1/256 приводит к необходимой битовой пропускной способности 8 биты для хранения. Однако статистика работает не так. Вернитесь к размышлениям о Pr(x) потому что требуемые биты ничего не значат.
Ваш вопрос о статистике. Учитывая бесконечный образец, если и только если распределение соответствует идеальной гистограмме, поскольку размер выборки приближается к бесконечности, вероятность того, что каждая выборка приблизится к ожидаемой частоте. Я хочу дать понять, что вы не ищете «-log2 Pr(x) абсолютный хаос, когда это 8 дано Pr(x) = 1/256. «Равномерное распределение является не хаос. На самом деле, это … ну, единообразный. Его свойства хорошо известны, просты и легко предсказуемы. Вы ищете «Является ли конечный образец набора S удовлетворяющих критериям независимо распределенного равномерного распределения (обычно известного как «Независимо и идентично распределенные данные«или» i.i.d «) из Pr(x) = 1/256«Это не имеет ничего общего с теорией Шеннона и идет намного дальше во времени к базовым теориям вероятности, включающим броски монеты (в данном случае бином с учетом предполагаемой однородности).
Предполагая на мгновение, что любой C ++ 11 <random> генератор соответствует критерию «статистически неотличим от i.i.d.» (что, кстати, эти генераторы не делают), вы можете использовать их для подражать i.i.d. Результаты. Если вам нужен диапазон данных, который может быть сохранен в пределах 6,7 бит (неясно, вы имели в виду 6 или же 7 бит, потому что гипотетически все, что между ними тоже выполнимо), просто масштабируют диапазон. Например…
#include <iostream>
#include <random>
int main() {
unsigned long low = 1 << 6; // 2^6 == 64
unsigned long limit = 1 << 7; // 2^7 == 128
// Therefore, the range is 6-bits to 7-bits (or 64 + [128 - 64])
unsigned long range = limit - low;
std::random_device rd;
std::mt19937 rng(rd()); //<< Doesn't actually meet criteria for i.d.d.
std::uniform_int_distribution<unsigned long> dist(low, limit - 1); //<< Given an engine that actually produces i.i.d. data, this would produce exactly what you're looking for
for (int i = 0; i != 10; ++i) {
unsigned long y = dist(rng);
//y is known to be in set {2^6..2^7-1} and assumed to be uniform (coin flip) over {low..low + (range-1)}.
std::cout << y << std::endl;
}
return 0;
}
Проблема в том, что в то время как <random> классы распределения являются точными, генераторы случайных чисел (предположительно, за исключением std::random_device, но это зависит от системы) не предназначен для того, чтобы выдерживать статистические тесты пригодности как i.i.d. генераторы.
Если вы хотели бы, чтобы это было, внедрите CSPRNG (мое желание — Боб Дженкинс) ИСААК) имеет интерфейс, отвечающий требованиям <random> класс генераторов (вероятно, просто охватывает базовый интерфейс std::random_device это достаточно хорошо).
Чтобы проверить статистически обоснованное «нет» или «мы не можем сказать нет» на предмет соответствия набора определенной модели (и, следовательно, Pr(x) является точным и, следовательно, энтропийная функция Шеннона является точным предсказанием), это совсем другое дело. Как я уже сказал, нет генератора в <random> соответствует этим критериям (кроме может быть std::random_device). Мой совет — исследовать такие вещи, как Центральная предельная теорема, Совершенство-оф-приступа, День рождения-разнос, и так далее.
Чтобы поднять мою точку зрения немного больше, под предположениями вашего вопроса …
struct uniform_rng {
unsigned long x;
constexpr uniform_rng(unsigned long seed = 0) noexcept:
x{ seed }
{ };
unsigned long operator ()() noexcept {
unsigned long y = this->x++;
return y;
}
};
… будет абсолютно соответствовать вашим критериям единообразия (или, как вы говорите, «абсолютный хаос»). Pr(x) наверняка 1/N и биты, необходимые для хранения любого номера набора -log2 Pr(1/N) что бы ни 2 к степени битовой пропускной способности unsigned long является. Тем не менее, он не распространяется независимо друг от друга. Поскольку мы знаем его свойства, вы можете «хранить» всю последовательность, просто сохраняя seed, Сюрприз, все PRNG работают именно так. Поэтому биты, необходимые для хранения вся последовательность PRNG является -log2(1/2^bitsForSeed), По мере роста вашей выборки биты, необходимые для хранения, по сравнению с битами, которые вы можете сгенерировать этой выборкой (иначе говоря, степень сжатия), приближаются к пределу 0,
Другие решения
Я пока не могу комментировать, но я бы хотел начать обсуждение:
Из теории коммуникации / информации может показаться, что вам потребуются вероятностные методы формирования, чтобы достичь того, что вы хотите. Вы должны иметь возможность передавать выходные данные любой функции распределения через формирователь кодирования, который затем должен перераспределять входные данные для конкретной целевой энтропии Шеннона.
Вероятностное формирование созвездия было успешно применено в волоконно-оптической связи: Википедия с некоторыми другими ссылками
Вам не ясно, чего вы хотите достичь, и есть несколько способов понизить энтропию Шеннона для вашей последовательности:
- Корреляция между битами, например положить random_sequence через
простой фильтр. - Отдельные биты не являются полностью случайными.
В качестве примера ниже вы можете сделать байты менее случайными:
std::vector<uint8_t> generate_random_sequence(size_t sequence_size,
int unit8_t cutoff=10)
{
std::vector<uint8_t> random_sequence;
std::vector<uint8_t> other_sequence;
std::random_device rnd_device;
std::cout << "Random device entropy: " << rnd_device.entropy() << '\n';
std::mt19937 mersenne_engine(rnd_device());
std::uniform_int_distribution<unsigned> dist(0, 255);
auto gen = std::bind(dist, mersenne_engine);
random_sequence.resize(sequence_size);
std::generate(random_sequence.begin(), random_sequence.end(), gen);
other_sequence.resize(sequence_size);
std::generate(other_sequence.begin(), other_sequence.end(), gen);
for(size_t j=0;j<size;++j) {
if (other_sequence[j]<=cutoff) random_sequence[j]=0; // Or j or ...
}
return std::move(random_sequence);
}
Я не думаю, что это был ответ, который вы искали — поэтому вам, вероятно, нужно уточнить вопрос больше.