通过观察输入分布

Question

识别更多可压缩数据集，这可能是这里的问题的重复：Predict Huffman compression ratio without constructing the tree

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

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

非常感谢。

Answer 1

我不知道“某种程度上自信地”意味着什么，但是通过计算链接问题中所做的零阶熵，您可以获得每个集合的压缩大小的下限概率的总和乘以概率的对数）。那么较低的熵很可能产生比较高的熵更短的霍夫曼编码。这是不确定的，因为我相信可以拿出一个反例。

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

简单地生成代码，编码数据和代码描述非常快。最好的解决方案是做到这一点，并直接比较结果数量。