`
rogerceng
  • 浏览: 6322 次
  • 性别: Icon_minigender_1
  • 来自: 英国利物浦
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

Huffman编码算法及C语言实现(1)

阅读更多

Huffman编码算法的数学模型依赖于Huffman Tree

Huffman Tree的定义?
假设有n个权值{w1,w2,w3......wn},试构造一棵有n个叶子节点的二叉树(节点总数为m=2*n-1),每个叶子带权值为wi,其中WPL(树带权路径)最小的二叉树成为Huffman树或者最优二叉树。在一些判断性问题中,可以利用Huffman树得到最佳的判断算法,比如编制一个将百分制转换为五分制问题(参见《数据结构》清华版p144)。如有10000个输入数据,一般二叉树的判断过程需要31500次判断操作,而最优二叉树只需22000次。

如何构造Huffman Tree?
(1)根据给点的n个权值{w1,w2,w3.....wn}构成n棵二叉树的集合F={T1,T2,T3......Tn},其中每棵二叉树只有个带有权值Wi的根节点,其左右子树为空。
(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一个新二叉树,新根权值为左右子树权值之和。
(3)在F中delete掉这两棵树,插入新二叉树到F中。
(4)重复(2)和(3),直到F中只含一棵树,此数位Huffman Tree。

Huffman编码?
广泛运用在电报中,电报传送将文字转换为由二进制字符组成的字符串。如电文为 ” A B A C C D A" 4个字母只需2个字符可以分别,A B C D 分别为 00 01 10 11,则电文编码成 ”00010010101100“ 。但我们总喜欢编码尽可能的短,则可以采用不等长的编码进行表示,但必须保证任一个字符的编码不是另一个字符编码的前缀,否则无法译码。我可以用二叉树达到这个目的。让A B C D作为二叉树的节点,约定左分支为”0“,右分支为”1“,从根节点到叶子节点的路径上分支组成的字符串为叶子节点字符的编码。如此得到的编码并无前缀问题。同时在电文中,将每个字符出现的次数作为叶子节点的权值,优化该二叉树为最优二叉树使得其WPL值最小,则可以使电文编码最短。

Huffman编码实现:
字符序列为 A B C D,对应的权值为 1,3,6,9,设计Huffman树,并输出对应的Huffman编码。
此算法中Huffman树的存储结构为一个n行4列的二维数组,定义如下:


定义一个HuffmanTree变量HT,初始化HT。将每一个叶子结点的双亲结点,左孩子,右孩子初始化为0。假如有n个叶子结点,则总结点数为m=2*n-1,则还有n-1个非叶结点,也将其双亲结点初始化为0。


 

初始化后的HT数组状态:

 

 

初始化后就可以构造huffman树了,依次选择2个权值最小的叶子结点,分别作为左子树结点和右子树结点,修改它们的双亲结点域,使它们指向同一个非叶子节点,同时其他此结点的权值为左右权值之和。重复操作n-1次,就可以得到一个huffman树。

 

 

 

 

  • 大小: 8 KB
  • 大小: 20.4 KB
  • 大小: 15.3 KB
  • 大小: 27.1 KB
  • 大小: 14.9 KB
0
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics