哈夫曼编码

来自计算思维百科
跳转至: 导航搜索

哈夫曼树,也称最优二叉树,是一种对符号的编码方式,利用哈夫曼树,可以实现哈夫曼编码算法。

基本概念

哈夫曼树:是一种带权路径长度最短的树, 即权值最小的结点远离根结点,权值最大的结点越靠近根结点。

哈夫曼树的构造算法如下:

(1)由给定的n个权值{W1,W2,….Wn},构成n棵只有根结点的二叉树集合F={T1,T2,…Tn} ,每个结点的左右子树均为空。

(2)在二叉树集合F中,找两个根结点的权值最小和次小的树,作为左、右子树构造一棵新的二叉树,新二叉树的根结点的权重为左右子树根结点的权重之和。

(3)在二叉树的集合F中,删除作为左右子树的两个二叉树,并将新二叉树加入到集合F中。

(4)重复执行(2)和(3)直到集合F中只剩下一棵二叉树为止。这棵二叉树就是要构造的哈夫曼树。

使用方法及步骤

例如,给定一组权值{1,3,6,9}按照哈夫曼构造的算法对集合的权重构造哈夫曼的过程如下:

应用案例

应用1- 数据通信

案例:哈夫曼编码常应用于数据通信中,在数据传送中,需要将字符转换为二进制的字符串。

例如,假设传送的电文是ABDAACDA,电文中有A、B、C、D四种字符,如果规定A、B、C、D的编码分别为00、01、10、11,则上面的电文代码为0001110000101100,总共16个二进制数。

在传送电文时,希望电文的代码尽可能的短。如果按照每个字符进行长度不等进行编码,将出现频率高的字符采用尽可能短的编码,则电文的代码长度就会减少。可以利用哈夫曼树对电文进行编码,最后得到的编码就是长度最短的编码。

解决步骤: 按照哈夫曼编码的构造方法,字符集合为{A,B,C,D},各个字符相应的出现次数为{4,1,1,2},这些字符作为叶子结点构成的哈夫曼树如图:

可以体现的计算思维

转化方法能够将一个问题由难化易,由繁化简,由复杂化简单的过程。哈夫曼编码体现了计算思维的优化特点。