哈夫曼编码码长怎么算

Question

如题所述

Answer 1

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。

霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。

实际应用中

除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。

按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。

Answer 2

假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}. (1)为这8个字母设计哈夫曼编码。 (2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少? 解： (1)哈夫曼编码 根据上图可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000 (2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87% 其平均码长是等长码的87%。 所以平均压缩率为13%。 记得刚学哈夫曼树的时候还做过一道简单的题,好象是关于分数统计输入的,找不到题目了. 参考资料： http://51zk.csai.cn/sjjg/200609041055411573.htm
求采纳本回答被提问者采纳

Answer 3

有需要做后期

Answer 4

用二进制算

Answer 5

哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 内容来自 www.stl.vc 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。定长变码需要300,000位，而按表中变长编码方案，文件的总码长为： （45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000。 比用定长码方案总码长较少约45%。 内容来自 www.stl.vc 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 编码的前缀性质可以使译码方法非常简单。 表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。 平均码长定义为： C++编程网 本文来自C++编程网 C++编程网 使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。 在书上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。 算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn) 。 C++编程网 以下是代码: C++编程网 package greedy; www.stl.vc class HaffuManNode implements java.lang.Comparable{ public int compareTo(Object o) { if(f<((HaffuManNode)o).f) { return -1; } else if(f>((HaffuManNode)o).f) { return 1; } else { return 0; } } private double f; private HaffuManNode left; private HaffuManNode right; public HaffuManNode() { f=0; left=right=null; } public HaffuManNode(double f) { this.f=f; left=right=null; } 本文来自C++编程网 public double getF() { return f; } public void setF(double f) { this.f = f; } public HaffuManNode getLeft() { return left; } public void setLeft(HaffuManNode left) { this.left = left; } public HaffuManNode getRight() { return right; } public void setRight(HaffuManNode right) { this.right = right; } www.stl.vc } www.stl.vc