如果我有一组符号和频率：A-0.1B-0.40C-0.2D-0.23E-0.15F-0.17
霍夫曼算法将产生仅比长度1大的码字。
但是，当我将频率更改为大于0.40时，它将产生长度为1或更大的码字。如何构建一个证明，证明任何一组符号都是这样，而不仅仅是这个符号？
（请注意，您的频率不会加1；我认为这是一个拼写错误）
这里是一个证明的草图，即要使所有码字大于1位，任何频率都不能大于2/5。在不失一般性的情况下，huffman树必须如下所示：
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<=c<=d.
2a+c+d
/
2a c+d
/ /
a a c d
让我们找到与这个Huffman树一致的d的最大值。根据算法的工作原理，以下不等式成立：
- a<=c
- a<=d
- 2a>=c
- 2a>=d
让我们也用1-d-2a:替换c
- a<=（1-d）/3
- a<=d
- a>=（1-d）/4
- a>=d/2
目前还不清楚这是如何约束a和d的，但您可以很容易地在a/d坐标空间中绘制约束。那么，你知道上面四个不等式中哪两个最重要：
d/2<=a<=（1-d）/3
从这里：
d/2<=（1-d）/3
所以d <= 2/5。
如果您有三个任何频率的符号，您将得到一个长度为1的代码和两个长度为2的代码。例如，它们都可能具有1/3的概率，即小于0.4。
这里是一个简单的反例，断言有四个符号，它们的概率导致长度为1的代码，其中所有概率都小于0.4:
a - 0.34
b - 0.33
c - 0.17
d - 0.16
通过简单地分解概率，可以很容易地构造具有相同属性的较长代码。例如：
a - 0.34
b - 0.33
c - 0.17
d - 0.08
e - 0.08