通过观察输入分布来识别更多可压缩数据集

Question

这可能是这里问题的重复：Predict Huffman compression ratio without constructing the tree

所以基本上，我有两个具有相同变量但不同概率的数据集的概率分布。现在，有没有什么办法可以通过查看变量分布，在某种程度上自信地说数据集在通过霍夫曼编码实现时会实现比另一个更高的压缩率？

我遇到的解决方案之一是使用条件熵计算上限，然后计算平均代码长度。在使用上述方法之前，我是否可以探索其他任何方法？

非常感谢。

Answer 1

我不知道 "to some degree confidently" 是什么意思，但是您可以通过计算链接问题中的零阶熵来获得每个集合的压缩大小的下限（负的概率之和乘以概率的对数）。那么较低的熵很可能比较高的熵产生更短的霍夫曼编码。不确定，因为我相信有人可以想出一个反例。

如果您想在另一端对其进行解码，您还需要发送代码本身的描述，这会增加比较的难度。但是，如果数据比代码描述大得多，那么就会在噪音中丢失。

简单的生成代码、编码数据、代码描述，速度非常快。最好的解决方案是这样做，并直接比较结果位数。