algorithm - 使用输入字符模式(或频率)确定霍夫曼树的深度？

Question

我想作为 this question regarding Huffman tree building 的变体.无论如何，在不绘制树的情况下，是否可以根据输入(或频率)计算霍夫曼树的深度。

如果没有快速的方法，那个问题的答案是怎么找到的？具体示例是:频率为 1 到 10 的 10 输入符号为 5。

Answer 1

如果您正在寻找一个方程来计算频率并给出深度，那么不，不存在这样的方程。证据是存在一组频率，在应用霍夫曼算法时，您可以任意选择这些频率，从而产生不同的深度树!所以对于“霍夫曼树的深度是多少？”甚至没有唯一的答案。对于某些频率集。

一个简单的例子是频率 1、1、2 和 2 的集合，它可以给出 2 或 3 的深度，具体取决于应用霍夫曼算法时配对的最小频率。

获得答案的唯一方法是应用霍夫曼算法。你可以采取一些捷径来获得深度，因为你不会在最后使用树。但无论如何，您都将有效地构建树。​​

您可以使用熵方程近似深度，或者至少对其设置界限。在某些特殊情况下，边界可能限制得足以为您提供准确的深度。例如。如果所有频率都相等，那么您可以计算深度为符号数的对数底数 2 的上限。

一个很酷的例子表明一个简单的熵界限不足以得到准确的答案是当你对频率使用斐波那契数列时。这确保树的深度是符号数减一。因此频率 1、1、2、3、5、8、13、21、34、55、89、144、233、377 和 610 将导致 14 位的深度，即使最低频率符号的熵是 10.64 位。