Huffman树的构造原理

Huffman树的来源

在编码过程中，人们需要尽可能的提高编码效率。例如，对于26个字母的编码，可以轻易地用五位二进制数来编码。然而，这样做会造成很大的空间浪费。于是不难想到，用1~5位二进制数来编码这26个字母。可是，这样的编码存在二义性。如，将a编码为0，b编码为01，c编码为00，d编码为1，对于“0001”这样一串编码，就存在多种解释。而Huffman发明的这个树完美地解决了问题。

Huffman树的构造原理

在一篇英语写成的文章中，每个字母有其各自的出现频率，若用一棵二叉树存储字母，我们希望出现频率较高的字母在二叉树上方，这样可以在遍历时效率更高。于是，我们在统计字母出现次数后，为字母分配相应的权值，权值较高的出现在二叉树上方。同时，二叉树的构造决定了它包含每个字母编码均不同。具体方法是，为每个左结点编码0，为每个右结点编码1，到达字母的0-1路径即组成了该字母的编码。

Huffman树的构造方法

给定一串权值由低到高的叶结点，每次取出两个结点，和已生成森林中无父结点的所有结点共同进行比较，并选出两个权值最小的结点，在森林中以较小结点为左结点，以较大结点为右结点，创建父结点，并将左右结点的权值之和赋予父结点，未进入森林的结点继续参与比较，直至森林形成一棵二叉树，该树即为Huffman树。

根据权值生成Huffman数的过程

给定权值: 2,3,5,7,11,13,17,19，则构造H

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！