当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 讲师博文 > 哈夫曼算法原理

哈夫曼算法原理 时间:2018-12-17      来源:华清远见

1952年, David A. Huffman提出了一个不同的算法,这个算法可以为任何的可能性提供出一个理想的树。香农-范诺编码(Shanno-Fano)是从树的根节点到叶子节点所进行的的编码,哈夫曼编码算法却是从相反的方向,暨从叶子节点到根节点的方向编码的。

为每个符号建立一个叶子节点,并加上其相应的发生频率

当有一个以上的节点存在时,进行下列循环:

把这些节点作为带权值的二叉树的根节点,左右子树为空

选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

把权值最小的两个根节点移除

将新的二叉树加入队列中.

最后剩下的节点暨为根节点,此时二叉树已经完成。

示例:

哈夫曼算法原理,嵌入式学科
哈夫曼算法原理,嵌入式学科

在这种情况下,D,E的最低频率和分配分别为0和1,分组结合概率的0.28205128。现在最低的一双是B和C,所以他们就分配0和1组合结合概率的0.33333333在一起。这使得BC和DE所以0和1的前面加上他们的代码和它们结合的概率最低。然后离开只是一个和BCDE,其中有前缀分别为0和1,然后结合。这使我们与一个单一的节点,我们的算法是完整的

 

上一篇:IPC机制之管道

下一篇:上位机是什么

热点文章推荐
华清学员就业榜单
高薪学员经验分享
热点新闻推荐
前台专线:010-82525158 企业培训洽谈专线:010-82525379 院校合作洽谈专线:010-82525379 Copyright © 2004-2022 北京华清远见科技集团有限公司 版权所有 ,京ICP备16055225号-5京公海网安备11010802025203号

回到顶部