使用输入字符模式（或频率）确定霍夫曼树的深度？
Determin Depth of Huffman Tree using Input Character pattern (or Frequency)?
我想作为 this question regarding Huffman tree building 的变体。无论如何，在不绘制树的情况下，是否可以根据输入（或频率）计算霍夫曼树的深度。
如果没有快速的方法，那个问题的答案是怎么找到的？具体示例是：频率为 1 到 10 的 10 输入符号为 5。
如果您正在寻找一个方程来计算频率并给出深度，那么不，不存在这样的方程。证据是存在一组频率，在应用霍夫曼算法时，您可以任意选择这些频率，从而产生不同的深度树！因此，对于某些频率集，"What is the depth of the Huffman tree?" 甚至没有唯一的答案。
一个简单的例子是频率 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 位。
我想作为 this question regarding Huffman tree building 的变体。无论如何，在不绘制树的情况下，是否可以根据输入（或频率）计算霍夫曼树的深度。
如果没有快速的方法，那个问题的答案是怎么找到的？具体示例是：频率为 1 到 10 的 10 输入符号为 5。
如果您正在寻找一个方程来计算频率并给出深度，那么不，不存在这样的方程。证据是存在一组频率，在应用霍夫曼算法时，您可以任意选择这些频率，从而产生不同的深度树！因此，对于某些频率集，"What is the depth of the Huffman tree?" 甚至没有唯一的答案。
一个简单的例子是频率 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 位。