通過觀察輸入分佈

Question

識別更多可壓縮數據集，這可能是這裏的問題的重複：Predict Huffman compression ratio without constructing the tree

所以基本上，我有兩個數據集具有相同的變量，但不同的概率概率分佈。現在，有沒有辦法通過查看變量分佈，我可以在某種程度上自信地說數據集在通過霍夫曼編碼實現後會獲得比另一個更高的壓縮比？

我遇到的解決方案之一是使用條件熵計算上限，然後計算平均代碼長度。在使用上述方法之前，我還可以探索其他方法嗎？

非常感謝。

Answer 1

我不知道「某種程度上自信地」意味着什麼，但是通過計算鏈接問題中所做的零階熵，您可以獲得每個集合的壓縮大小的下限概率的總和乘以概率的對數）。那麼較低的熵很可能產生比較高的熵更短的霍夫曼編碼。這是不確定的，因爲我相信可以拿出一個反例。

如果您想在另一端對其進行解碼，您還需要發送代碼本身的描述，這會增加比較的摺痕。但是，如果數據比代碼描述大得多，那麼噪聲就會丟失。

簡單地生成代碼，編碼數據和代碼描述非常快。最好的解決方案是做到這一點，並直接比較結果數量。