赫夫曼算法是啥玩意啊？？

  

记得第一次听说哈夫曼编码这个词的时候是在大一上信息与信号处理课上，那时觉得它很深奥，老师只是稍微提了一下这个而已，自己也没有去查找过相关的资料，它到底是什么玩意也不太清楚，通过自己写的一个可视化赫夫曼编码知道了哈夫曼编码的一些应用，知道它的原理就会就会觉得它没有什么，但是假如哈夫曼没有提出这种算法，你会想到这么算不？有时候看到一个理论总觉得简单，就好像牛顿被苹果砸了一下就发现了万有引力定律，但是想想，如果砸的是你，你是否也会发现万有引力定律呢？呵呵，扯远了，我想说的是，哈夫曼算法并不是偶然的，而是哈夫曼经过长期的钻研才总结出来的。

那好，说一下我自己对哈夫曼算法的理解，其实哈夫曼算法形象一点来说就是一颗带权路径长度最小的二叉树也叫做哈弗曼树。哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，故称其为哈夫曼算法。那么是如何创建出一颗哈弗曼树呢？比如有5个权值v1=1,v2=1,v3=3,v4=5,v5=8,创建哈弗曼时，我们就得将这n个数从小到大排序，为了好说明，这里的权值都是排序好了的，首先以v1和v2为叶子，他们的权值之和为根节点v6=2,再将v6与剩下的排序，再去取出两个权值最小的v6和v3为叶子，他们的和v7=5为根节点，依此类推，直到全部的节点都用完，那么一颗哈弗曼树就建成啦！

哈弗曼算法的最大用途是哈弗曼编码，用于数据压缩，信息时代，人们对使用计算机获取信息、处理信息的依赖性越来越高。计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体。大数据量的图像信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。压缩关键在于编码，如果在对数据进行编码时，对于常见的数据，编码器输出较的码字；而对于少见的数据则用较长的码字表示，就能够实现压缩。

可以这么说很多的数据都是经过哈弗曼编码进行压缩的，可见哈弗曼算法的重要性，下面是我自己写的一个简单的哈弗曼编码软件，可能bug是有的，让大家看看他的界面效果：

  

 

 

 

         其实现在自己应用哈弗曼算法也不是很多，以后可能会用来做压缩软件····

评论

1 楼 freewxy 2010-08-17  

great！！