王永明
有趣的赫夫曼树
来源:黄朝阳     发布时间: 2019-04-16      浏览次数:357

字号:

美国有个数学家叫赫夫曼,60年前他根据数据的使用概率,发明了一个二叉树叫赫夫曼树。这个赫夫曼树被用在了数据压缩上,被称为赫夫曼编码,这是后来压缩的基础。 他解决的问题主要思想是:根据元素出现的概率,获得最优解。 举例如下:学生考试成绩出来后,会根据考试成绩分等级,极优秀,优秀,中等,及格,不及格。如果我们按照普通逻辑进行判断时,通常是: 

if (Score < 60) { printf("不及格"); } else if (Score < 70) { printf("及格"); } else if (Score < 80) { printf("中等"); } else if (Score < 90) { printf("优秀"); } else if (Score < 100) { printf("极优秀"); }但是按照分数的分布概率,优秀:30%,中等:40%,及格:15%,极优秀:10%,不及格:5%如果先判断优秀,中等,再判断极优秀,极优秀,不及格,则可以提高很多效率。赫夫曼树就是根据概率来生成的二叉树。转换成二叉树区别如下: 从根节点出发,遍历每一个叶子节点,是的到达节点时走的链接树乘以节点(nodeLinkNum * weight)对应的权重之和最小如:sum = 1*5+2*15+3*40+4*30+4*10显然,左图和右图总和不一样,左图的和大于右图. 那给你一组数字,怎么构造一个赫夫曼树呢?1.先把所有的数据节点,从小到大依次排列,成为一个有序列表2.取出前面两个节点,让这两个节点的权重数据相加得到一个和,令这个和为根节点,这个两个节点的小的为其左孩子,大的为其右孩子3.令这个和节点替换掉前面的两个节点,并重新排序,生成一个有序列表4.不断重复第二步,第三步。直到所有的节点都被用完,得到一个排序结果,此时生成的二叉树,就是赫夫曼树。  赫夫曼树的实际应用:压缩数据数据在计算机的表示形式是0,1,那么一串字符串的表示是怎么样的呢例如ABCDEF编码如下:那么要表示字符串“BADCADFEED”的二进制为:“001000011010000011101100100011”。但是ABCDEF做为基本字符,在这串字符串中的出现概率是不一样的,那么我们是否可以以概率做为字符权重,对字符生成赫夫曼树呢 假设六个字母的频率为A 27,B 8,C 15,D15,E 30,F 5,合起来正好是100%。那就意味着,我们完全可以重新按照赫夫曼树来规划它们。  将权值左分支改为0,右分支改为1后的赫夫曼树。 根据重新编码后为:1001010010101001000111100(共25个字符)而原来的字符编码为:“001000011010000011101100100011”(共30个字符)压缩了近17% 解压时,按照同样的规则,还原原字符串。  

  • 相关内容: