霍夫曼编码的符号频数压缩到可用一个字节(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]