最佳压缩霍夫曼树

Question

我正在编码一个霍夫曼串压缩器，我想确认我正在用我的树做最佳压缩。

我用这样的树：

而是这个还挺树：

我认为，在10个单字符，这是不可能的压缩上8位..

第一个图像真的是最佳的吗？

Answer 1

最基本的想法是添加两个最小的节点，创建一个新的节点，该节点的值是其2个子节点的总和。

尊重此规则直到树根保证产生的树将是最优。

因此，你有没有控制关于树的形状：它完全取决于字符的概率分布。如果概率分布看起来像斐波那契数列，它可能最终会变成一棵退化的树（每级有一个分支）。

因此，使用预先设定的最大深度创建霍夫曼树更复杂，并且需要打破始终添加2个最小节点的通常规则。由此产生的树显然不是最优的。