使用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;
}
首先，似乎在MSVC 2015中将
std::random_device::entropy()硬编码为return 32;(根据Shannon定义可能为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的独立分布的均匀分布(通常称为“Independently and Identically Distributed Data”或“i.i.d”)的标准？”这与香农的理论无关，并且在时间上可以追溯到涉及硬币翻转的基本概率论(在这种情况下，给定假定均匀性为binomial)。
暂时假设任何C++ 11 Pr(x) = 1/256生成器都满足“与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>分发类是准确的，但随机数生成器(大概是 <random> 除外，但这是系统特定的)不是为了承受i.i.d的适用性统计测试而设计的。生成器。如果您愿意的话，可以实现一个CSPRNG(我的最爱是Bob Jenkins的ISAAC)，该接口(interface)具有满足生成器
std::random_device类的要求的接口(interface)(可能仅覆盖<random>的基本接口(interface)就足够了)。要测试统计数据集是否遵循特定模型是否合理(“否”或“我们不能说不”)(因此
std::random_device是准确的，因此Shannon的熵函数是准确的预测)，这完全是另外一回事。就像我说的，Pr(x)中没有任何生成器满足这些条件(也许<random>除外)。我的建议是对Central limit theorem，Goodness-of-fit，Birthday-spacing等进行研究。在您提出问题的假设下，我的观点要多一点...
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;
}
};
……绝对可以满足您的统一标准(或您所说的“绝对困惑”)。
std::random_device最肯定是Pr(x)，存储任意数量的集合所需的位是1/N，等于-log2 Pr(1/N)的位宽的幂2。但是，它不是独立分布的。因为我们知道它的属性，所以您可以通过简单地存储unsigned long来“存储”它的整个序列。令人惊讶的是，所有PRNG都以这种方式工作。因此，存储PRNG整个序列所需的位是seed。随着样本的增长，存储所需的位与生成该样本的位(即压缩率)接近-log2(1/2^bitsForSeed)的限制。关于c++ - 具有提供的(至少估计的)熵的C++随机生成器，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42038239/