哈夫曼树介绍大家好,我是bigsai。原以为哈夫曼树、哈夫曼编码很难,结果它很简单啊老铁们! 哈夫曼树、哈夫曼编码很多人可能听过,但是可能并没有认真学习了解,今天这篇就比较详细的讲一下哈夫曼树。 首先哈夫曼树是什么? 哈夫曼树的定义:给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree),哈夫曼树是带权路径长度最短的树。权值较大的结点离根较近。 那这个树长啥样子呢?例如开始2,3,6,8,9权值节点构成的哈夫曼树是这样的: 从定义和图上你也可以发现下面的规律:
你可能会好奇这么一个哈夫曼树是怎么构造的,其实它是按照一个贪心思想和规则构造,而构造出来的这个树的权值最小。这个规则下面会具体讲解。 哈夫曼树非常重要的一点: WPL计算方法: WPL=求和(Wi * Li)其中Wi是第i个节点的权值(value)。Li是第i个节点的长(深)度. 例如上面 2,3,6,8,9权值节点构成的哈夫曼树的WPL计算为(设根为第0层): 比如上述哈夫曼树的 既然了解了哈夫曼树的一些概念和WPL的计算方式,下面看看哈夫曼树的具体构造方式吧! 哈夫曼树构造初始给一个森林有n个节点。我们主要使用贪心的思想来完成哈夫曼树的构造:
在具体实现上,找到最小两个节点需要排序操作,我们来看看2,6,8,9,3权值节点构成哈夫曼树的过程。 初始时候各个节点独立,先将其排序(这里使用优先队列),然后选两个最小节点(抛出)生成一个新的节点,再将其加入优先队列中,此次操作完成后优先队列中有5,6,8,9节点 重复上面操作,这次结束 队列中有11,8,9节点(排序后8,9,11) 否则继续加入队列进行排序。重复上述操作,直到队列为空。 在计算带权路径长度WPL的时候,需要重新计算高度(从下往上),因为哈夫曼树是从下往上构造的,并没有以常量维护高度,可以构造好然后计算高度。 具体代码实现(仅供参考) import java.util.ArrayDeque; 输出结果:
哈夫曼编码除了哈夫曼树你听过,哈夫曼编码你可能也听过,但是不一定了解它是个什么玩意儿,哈夫曼编码其实就是哈夫曼树的一个非常重要的应用,在这里就简单介绍原理并不详细实现了。 哈夫曼编码定义:哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。 哈夫曼编码的目的是为了减少存储体积,以一个连续的字符串为例,抛开编程语言中实际存储,就拿
这个字符串来说,在计算机中如果每个字符都是定长存储(假设长为4的二进制存储),计算机只知道0和1的二进制,假设
那么上面字符串可以用二进制存储是这样的
如果每个字符编码等长,那么就没有存储空间优化可言,都是单个字符长度 * 字符个数。但是如果每个字符编码不等长,那么设计的开放性就很强了。 比如一个字符串 如果设计 如果设计 如果设计 你看,在计算机的01二进制世界中,明显第二种比第一种优先,第三种又比第二种优先。所以,设计编码要考虑让出现多的尽量更短,出现少的稍微长点没关系。 但是,你需要考虑的一个问题是,二进制开始0,1,01,10,11这个顺序 ,如果来了001它到底是0,0,1还是0,01呢?所以编码不等长的时候你要考虑到这个编码要有唯一性不能出现歧义。这个怎么搞呢? 简单啊,计算机只知道01二进制,而二叉树刚好有左右两个节点,至于一个字符它如果是对应叶子节点,那么就可以直接确定,也就是这个数值如果映射成一个二叉树字符不能存在非叶子节点上。 所以,哈夫曼编码具体流程就很清晰了,先统计字符出现的次数,然后将这个次数当成权值按照上面介绍的方法构造一棵哈夫曼树,然后树的根不存,往左为0往右为1每个叶子节点得到的二进制数字就是它的编码,这样频率高的字符在上面更短在整个二进制存储中也更节省空间。 结语哈夫曼树还是比较容易理解,主要构造利用贪心算法的思想去从下往上构建,哈夫曼编码相信看了你也有所收获,有兴趣可以自己实现一下哈夫曼编码的代码(编码、解码) |
|
来自: taotao_2016 > 《计算机》