algorithm - 证明霍夫曼算法可以在频率大于0.40时产生长度为1的码字。

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
如果我有一组符号和频率：
A-0.1分
B-0.40
C-0.2分
D-0.23
E-0.15
F-0.17
哈夫曼算法将产生只大于长度1的码字。
但当我将频率更改为大于0.40时，它将产生长度为1且更大的码字如何构造一个证明，证明这是任何一组符号的情况，而不仅仅是这一个？

最佳答案

（请注意，您的频率没有加到1；我假设是输入错误）
这里是一个证明的草图，为了使所有的码字大于1位，任何频率都不能大于2/5。Without loss of generality，哈夫曼树必须是这样的：

    a+b+c+d (the sum must be equal to 1)
     /   \
  a+b     c+d
  / \     / \
 a   b   c   d

我们必须证明所有的a，b，c和d都不大于2/5。
wlog（再次）a=b

    2a+c+d
     /   \
   2a     c+d
  / \     / \
 a   a   c   d

让我们找到与Huffman tree一致的d的最大值。根据算法的工作原理，以下不等式成立：
aA2a>=c
2a>=d
我们也用c替换1-d-2a：
aaA>=（1-D）/4
a>=d/2
现在还不清楚这是如何约束a和d，但是可以很容易地在a/d坐标空间中绘制约束。然后，你知道以上四个不等式中哪两个最重要：
D/2<=A从这里开始：
D/2所以d <= 2/5。

关于algorithm - 证明霍夫曼算法可以在频率大于0.40时产生长度为1的码字。，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25959180/