霍夫曼编码的符号频数压缩到可用一个字节(8位)表示时,霍夫曼编码最多能有多少位?

Question

即符号频数在0-255之间,频数越高霍夫曼编码越短,反之越长.这里假设一共有256个不同的字符,我认为如果这256个字符出现的频数都相同的话,它们的霍夫曼编码应该都是8位.而我想问这256个字符出现频数不同的情况下,最长的霍夫曼编码能有多少位?

Answer 1

我也知道了,根据熵来算的.256个字符出现的频数都不一样的情况下,霍夫曼编码为最佳且能得到最长编码位数.
也就是说频数为1-255,总和就是(1+255)*256/2=32768.
其中频数为1的符号需要的编码位数最多,熵为-lg(1/32768)=15,因为实际位数会有(+-)1的出入,所以最多为15+1=16位

Answer 2

以下是没有100%把握的分析。

首先基于以下两个前提进行讨论：

1. 零频度的字符不存在编码，不出现在Huffman树中，实际使用的频度最低为1。
2. Huffman树生成算法在遇到森林中多个树的权重相同时，合并深度最低的两个树，保证最终生成的Huffman树总高度最小。

从Huffman树的生成反推。显然合并次数是固定的255次。则如果想制造较长的Huffman树，目标就是很明显的：尽可能让每次合并时，森林中最深树的深度仍能+1。观感上是尽量每次都让单节点并入最长的树。

从[1, 1, 1]开始，这三个节点肯定能形成树( ( (1) 2 (1) ) 3 (1) )。

则如果想挂入一个叶节点，和根节点3合并形成新的根，这个叶节点的值必须比已存在树中最大的枝叶节点还要大。在这里就是大于1,2,1,1取3，形成以下的树：

1 - 2 - 3 - 6
    |   |   |
    1   1  [3]

不能小于枝叶节点是当然的。等于也不行，因为如果相等，新加入的节点就会由于深度为0的原因，比已存在的节点在合并中占有优势，从而破坏预计的合并过程。例如在上边的例子中如果敢取2就会……

        5
      / |
1 - 2   3
   /  / |
  1  1 [2]

所以按照这个规律生成：

a=[1,2,3,6]; b=[1,1,3];
while b[-1] < 256:
    b.append(max(a[:-1] + b) + 1)
    a.append(a[-1] + b[-1])
print(a) # [1, 2, 3, 6, 10, 17, 28, 46, 75, 122, 198, 321, 520, 842]
print(b) # [1, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322]

这表示了这样一棵树，高度为12，使用了13个叶子节点：

1-2-3-6-10-17-28-46-75-122-198-321-520
  | | |  |  |  |  |  |   |   |   |   |
  1 1 3  4  7 11 18 29  47  76 123 199

在叶子权重255的限制下，不能继续生成下去了。此时还剩下243个字符没有使用过，而这243个字符的权重都不能低于199（不破坏已有树的存在性）。

则这243个字符应该会生成一个深度为8的完全二叉树（不是也差不多），然后这个长链挂在其中的某个节点上，很有可能挂在倒数第二层（而不是最底层）。

没有进一步更深入的研究。定性的来看，已经可以估计最后的这个值应该在12+8-1=19左右。