2016 - 2024

感恩一路有你

哈夫曼树带权路径长度算法 怎样求哈夫曼树的平均编码长度?

浏览量:2834 时间:2021-03-13 12:36:55 作者:admin

怎样求哈夫曼树的平均编码长度?

创建一个结构数组,每个成员都有一个指向结构的指针,左,右,权重值。随机初始化值。将每个节点的左侧和右侧设置为null。从阵列中随机选取三个节点,让其中一个节点的左右两侧分别指向另外两个节点。等等。(节点是否被使用,要自己判断,顶点也要自己记住。数组应该是奇数(有一个结束节点,需要2N-1个节点)。用指针查找路径的长度,从节点开始,直到指针为空。

怎样求哈夫曼树的平均编码长?怎样求哈夫曼树?

假设用于通信2113的消息由字符集{a、B、C、D、e、F、G、H}中的5261个字母组成,消息中出现这八个字母的概率为4102,即{0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10}。哈夫曼码1653可以从上面的编码表中得到:A:1001 B:01 C:10111 D:1010 e:11 F:10110 G:00 h:1000,三位二进制等长编码的平均长度为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%,平均压缩比为13%。由于定长码已经使用了相同的位数,这个条件保证了任何字符的码都不会成为其他码的前缀,所以这种情况只发生在变长码中,我们必须用一个条件来制作常规长度码。这个条件是,如果我们想成为压缩码,可变长度的代码必须是前缀码。所谓前缀码,是指任何一个字符的编码不能是另一个字符编码的前缀。

哈夫曼树带权路径长度算法 哈夫曼树等长编码怎么求 哈夫曼树编码怎么写

版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。