哈夫曼(哈夫曼树全路径长度)

哈夫曼，哈夫曼树全路径长度？

先构造哈夫曼树： 17 / \ 8 9 / \ 3 6 / \1 2所以带权路径长度WPL = （1+2）*3 + 6*2 + 8*1 = 29

前缀编码怎么判断？

1.若要设计长短不等的编码，则其中的任意一个字符的编码都必须不是另一个字符的编码的前缀，这种编码称为前缀编码。

2.判断一个编码是不是前缀编码，可以根据定义，即看每个字符的编码是不是和其他字符编码的前边的数字一样。

3.我们要挨个判断每个字符，从A开始。A的编码为0，只有一个数字。那么在B，C，D的编码中从前往后看一个数字分为1，1，1。1不等于0。则A的编码符合前缀编码要求。

4.然后判断B的编码是否是其他字母的编码的前缀。B的编码10明显不是C，D编码的前缀，所以B的编码符合前缀编码要求。

5.接下来判断C的编码。C编码为110，明显不是一位编码和两位编码的前缀。对于D编码111来说，从前到后并不包含110。所以C的编码符合前缀编码要求。

6.最后判断D的编码。同理，C编码从左数的头三个数字都不等于111，那两个连位数都不够的编码就更甭提了。所以D的编码符合前缀编码要求。最终，这四个编码属于前缀编码。

设哈夫曼树的叶子结点总数为m？

哈夫曼树是二叉树，且结点的度只有两种，一种是度为0的叶子节点，另一种则是度为2的内部结点，不存在度为1 的结点，根据二叉树的性质（好像是性质3）度为0的结点和度为2 的结点的关系:n0=n2+1很容易算出；叶子结点总数为m的哈夫曼树的总结点数为：2m-1

有人听说过哈夫曼三进制编码吗？

我最近在学信息论，不知道楼主是否在问哈夫曼3进制编码流程，我目前的理解是这样的： 设信源有Q个符号，m为m进制，这里是三进制的话就取3，还有一个变量k(后面再解释这个变量的意义)

1、对信源符号按概率大小进行排序

2、计算X = m + k(m-1) = 3 + k(3 - 1) = 3 + 2 k (3进制的情况) （这一步的目的是：计算如果每一步都是3个数进行编码，所需要的符号数目） 3、取一个使X>=Q的k，k可以取无数多个，但是我们取其中的最小值。 4、s = X - Q （这一步的目的是：计算我们目前拥有的符号数目与每一步都用3个符号进行编码时所需要的符号数目相差多少个） 5、则m-s的数值就是m进制哈夫曼编码第一部所需要取的符号个数。 （既然我们与理想状况相差s个，那我们第一步就用m-s个进行编码吧） k其实就是信源缩减的次数。 说的有点绕，理一理思路我再回来更口语化地修改答案。 例题： 信源有8个信源符号，所以X = 3 + 2 * 3 = 9 > 8 理想情况下是9个，但是我们只有8个符号，设差距设为s 则 s = 9 - 8 = 1 因此第一步取：m-s = 3 - 1 = 2个符号来编码。

哈夫曼编码是什么进制数？

哈夫曼编码是一种属性结构，利用的是二进制进行的编码方式。