深度为 1 的霍夫曼代码树小于字母数

Question

我需要用 n 个字母创建一个霍夫曼编码树，并使树的深度为 n-1。

我试着让所有频率都相等，但它对某些 n 值不起作用。

有什么具体的方法可以解决吗

Answer 1

要使树深度 n-1，您需要按如下方式设置概率：对于第 ii 个字母，概率应为 2^ii，其中 ii = 1,2,3,4,...。最后一个字母的概率应该刚好等于 1.

例子

对于字母表 0、1、2、3，给出以下概率：

p_0 = 0.5
p_1 = 0.25
p_2 = 0.125
p_3 = 1 - 0.5 -0.25 -0.125 = 0.125

三者如下所示：

O
|----------|
0(0)       O
           |----------|
           1(10)      O
                      |----------|
                      2(110)     3(111)

在字母表中添加另一个字母会将概率更改为：

p_0 = 0.5
p_1 = 0.25
p_2 = 0.125
p_3 = 0.0625
p_4 = 0.0625

新树看起来像：

O
|----------|
0(0)       O
           |----------|
           1(10)      O
                      |----------|
                      2(110)     O
                                 |----------|
                                 3(1110)    4(1111)

Answer 2

用最小总和来做到这一点的频率集是对卢卡斯数的修改。

卢卡斯数列以 2, 1 开头，每个数都是前两个数的和（就像斐波那契数列一样，它以 1, 1 开头）。

2 1 3 4 7 11 18 29 47 ...

要获得最长的霍夫曼编码，请将初始的 2 替换为 1, 1:

1 1 1 3 4 7 11 18 29 47 ...

n 频率序列将产生 maximal-length 霍夫曼码 n-1 位。

depth-nine 树是：

深度为 1 的霍夫曼代码树小于字母数

Huffman Code Tree with Depth 1 less than number of letters

algorithm

huffman-code

例子