我需要生成部分随机的数字序列，使得序列整体具有一定的熵水平。
例如。如果我将生成的数据提供给gzip，它将能够压缩它。事实上，这将是代码的确切应用，测试数据压缩器。
我用C ++编程这个，我想到的第一个想法是用随机种子初始化一堆std :: mt19937 PRNG并随机选择一个并用它做随机长度模式。每次使用相同的种子重置std :: mt19937，以便它始终生成相同的模式：
#include <iostream>
#include <random>
#include <vector>
int main() {
std::random_device rd;
std::vector<std::mt19937> rngs;
std::vector<int> seeds;
std::uniform_int_distribution<int> patternrg(0,31);
std::uniform_int_distribution<int> lenghtrg(1,64);
std::uniform_int_distribution<int> valuerg(0,255);
for(int i = 0; i < 32; ++i) {
seeds.push_back(rd());
rngs.emplace_back(seeds.back());
}
for(;;) {
// Choose generator and pattern lenght randomly.
auto gen = patternrg(rd);
auto len = lenghtrg(rd);
rngs[gen].seed(seeds[gen]);
for(int i = 0; i < len; ++i) {
std::cout << valuerg( rngs[gen] )<<"\n";
}
}
}
上面的代码是生成可压缩随机性的第一个要求，但第二个要求更难：如何控制级别熵/随机性？
让我写几个你觉得有用的句子。假设我们想用给定的熵对一位进行采样。所以它是0或1，你想要的熵等于e。
H（10 | p）= - p log2（p） - （1 - p）log2（1 - p），其中p是得到1的概率。简单测试 - 在p = 1/2的情况下，将得到熵1 - 最大熵。所以你选择e等于1以下的某个值，求解方程式
-p log2（p） - （1-p）log2（1-p）= e
并回到p，然后你可以开始使用Bernoulli distribution进行采样。简单的演示是here。在C ++中，人们可以使用标准的library routine。
好的，假设你想用给定的熵采样一个字节。它有256个值和熵
H（byte | \ vec {p}）= -Sum（1 ... 256）pi log2（pi）。
同样，如果所有组合都是等概率的（pi = 1/256），则得到-256/256 log2（1/256）= 8，这是最大熵。如果你现在修复你的熵（比方说，我希望它是7），那么pi将有无数的解决方案，没有给定熵的单一唯一实现。
您可以稍微简化一下问题 - 让我们再考虑一个参数情况，其中找到1的概率是p，找到0的概率是（1-p）。因此，从256个结果我们现在得到其中的9个 - 00000000,00000001,00000011,00000111,00001111,00011111,00111111,01111111,111111111。对于每种情况，我们都可以写出概率，计算熵，将其分配给你想要的任何东西和解决回来找到p。
采样相对容易 - 第一步是通过discrete distribution对9种组合进行采样，第二步是使用Fisher-Yates shuffle对字节内的随机位进行采样。
相同的方法可能用于，例如，32位或64位 - 你有33或65个案例，构造熵，分配给你想要的任何东西，找到p，取样其中一个，然后在取样值内洗牌。
现在没有代码，但如果有兴趣，我可能会稍后编写一些代码......
UPDATE
请记住固定熵的另一个特殊属性。即使是单个位的简单情况，如果你试图解决
-p log2（p） - （1-p）log2（1-p）= e
对于给定的e，你将得到两个答案，并且很容易理解为什么 - 方程式是对称的wrt p和1-p（或用0和1替换0和0）。换句话说，对于熵，如果您使用大多数零或大多数零传输信息是无关紧要的。对于像自然文本这样的事情来说并非如此。
你的结构的熵率（根据输出字节值，而不是人类可读的字符）有几个复杂性，但是（对于一些远小于256的生成器），它是一个很好的近似值，它表示它是每个的熵。选择（5位选择序列加上6位长度）除以子序列的平均长度（65/2），或者每个字节可能8位中的0.338位。 （这明显低于普通英文文本。）您可以通过定义更多序列或减少从每个序列中抽取的子序列的典型长度来提高熵率。 （如果子序列通常只有一个字符，或者序列号为数百个，则冲突必然会降低低于此估计值的熵率，并将其限制为每字节8位。）
另一个容易调整的序列类涉及从[0，n]中抽取单个字节，概率p <1 /（n + 1）为0，其他字节可能相同。这给出了熵率H =（1-p）ln（n /（1-p）） - p ln p，它位于[ln n，ln（n + 1）），因此可以通过选择任何所需的速率来选择n然后适当地p。 （如果你想要熵，请记住使用lg而不是ln。）