霍夫曼编码的符号频数压缩到可用一个字节(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%把握的分析。
首先基于以下两个前提进行讨论：
零频度的字符不存在编码，不出现在Huffman树中，实际使用的频度最低为1。
Huffman树生成算法在遇到森林中多个树的权重相同时，合并深度最低的两个树，保证最终生成的Huffman树总高度最小。
从Huffman树的生成反推。显然合并次数是固定的255次。则如果想制造较长的Huffman树，目标就是很明显的：尽可能让每次合并时，森林中最深树的深度仍能+1。观感上是尽量每次都让单节点并入最长的树。
从[1,1,1]开始，这三个节点肯定能形成树(((1)2(1))3(1))。
则如果想挂入一个叶节点，和根节点3合并形成新的根，这个叶节点的值必须比已存在树中最大的枝叶节点还要大。在这里就是大于1,2,1,1取3，形成以下的树：
1-2-3-6
|||
11[3]
不能小于枝叶节点是当然的。等于也不行，因为如果相等，新加入的节点就会由于深度为0的原因，比已存在的节点在合并中占有优势，从而破坏预计的合并过程。例如在上边的例子中如果敢取2就会……
5
/|
1-23
//|
11[2]
所以按照这个规律生成：
a=[1,2,3,6];b=[1,1,3];
whileb[-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
||||||||||||
113471118294776123199
在叶子权重255的限制下，不能继续生成下去了。此时还剩下243个字符没有使用过，而这243个字符的权重都不能低于199（不破坏已有树的存在性）。
则这243个字符应该会生成一个深度为8的完全二叉树（不是也差不多），然后这个长链挂在其中的某个节点上，很有可能挂在倒数第二层（而不是最底层）。
没有进一步更深入的研究。定性的来看，已经可以估计最后的这个值应该在12+8-1=19左右。