用卡方判别压缩数据和随机数据

Question

我试图找到一些测量，以识别和区别压缩和随机数据。我首先通过计算这类数据的熵来尝试，在这两种情况下，熵值都非常高(几乎是最大值)，因此这种方法似乎不起区别作用。

我读过关于卡方算法的文章，但我从未使用过它(实际上，我在解释结果时仍然存在一些问题)。有谁知道这个算法能带来更好的结果吗？

Answer 1

NIST工具是一个很好的起点。

没有一个通用的算法总是能区分压缩数据和随机数据。

但是，如果您想要尝试x-平方测试，您可以计算所有字节值的频率的直方图(您在数据中看到多少个字节，看到多少个字节，等等)，然后使用x-平方测试来测试这是否偏离了您对均匀随机数据的期望。

Answer 2

这是一个迟来的答案，但我最近让原因做了一些熵估计，并计算了一些chis。

对于上下文，在均匀分布的随机字节中，目标chi为~255，导致p值~ 0.5。由于随机性的一个定义是可压缩性，因此不能将压缩文件与真正的随机文件区分开来。不过，请注意的是可能的压缩级别。压缩文件需要控制和格式结构，这将显著区别于完全随机的文件。这些控制结构在chi测试中抛出计算出的p值。因此，一些压缩数据的例子：-

.zip p < 0.0001
.jpg p < 0.0001
.png p < 0.0001

记住，随机数据的平均值是p~ 0.5。更具体地说，对这些p值的Kolmogorov-Smirnov检验应该看到它们均匀地分布在0到1之间。所以在这一点上，我的回答是，是的，你可以用chi检验来识别随机数据。

但是压缩算法有了改进，我发现了fp8，这是一个PAQ8导数。这是我发现的最强大的压缩程序，可以很容易地编译。相同的文件现在显示以下chis已被fp8压缩：

.zip.fp8 p = 0.93
.jpg.fp8 p = 0.14
.png.fp8 p = 0.38

在表面证据上，这些压缩文件产生的chi p值与完全随机数据一致。所以我的最后答案是否定的，你不能用气测试来区分随机数据和压缩数据。

对chi和p的进一步了解可能是这里。