Python描述数据结构之哈夫曼树篇

发表于:2020-9-08 09:38  作者:夏悠然然   来源:CSDN

字体: | 上一篇 | 下一篇 |我要投稿 | 推荐标签: 软件开发 Python

  本篇主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码,并用Python实现。
  1. 基本概念
  哈夫曼树(Huffman(Huffman Tree)Tree),又称为最优二叉树,指的是带权路径长度最小的二叉树。树的带权路径常记作:
   
  
  2. 构造过程及实现
  在集合FF中选取两棵权值最小的根结点构造一棵新的二叉树,使新二叉树的根结点的权值等于其左、右子树根结点的权值之和;再然后将选中的那两个结点从集合FF中删除,将新的二叉树添加到FF中;继续重复上述操作,直至集合FF中只剩一棵二叉树为止。
  比如F={(A,3),(B,7),(C,2),(D,11),(E,13),(F,15),(G,9)}F={(A,3),(B,7),(C,2),(D,11),(E,13),(F,15),(G,9)},它构造出来的哈夫曼树就是下面这棵二叉树:
  代码实现:
  class HuffmanTreeNode(object):
      def __init__(self):
          self.data = '#'
          self.weight = -1
          self.parent = None
          self.lchild = None
          self.rchild = None
  class HuffmanTree(object):
      def __init__(self, data_list):
          self.nodes = []
          # 按权重从大到小进行排列
          for val in data_list:
              newnode = HuffmanTreeNode()
              newnode.data = val[0]
              newnode.weight = val[1]
              self.nodes.append(newnode)
          self.nodes = sorted(self.nodes, key=lambda node: node.weight, reverse=True)
          print([(node.data, node.weight) for node in self.nodes])
      def CreateHuffmanTree(self):
          # 这里注意区分
          # TreeNode = self.nodes[:]  变量TreeNode, 这个相当于深拷贝, TreeNode变化不影响nodes
          # TreeNode = self.nodes     指针TreeNode与nodes共享一个地址, 相当于浅拷贝, TreeNode变化会影响nodes
          TreeNode = self.nodes[:]
          if len(TreeNode) > 0:
              while len(TreeNode) > 1:
                  letfTreeNode = TreeNode.pop()
                  rightTreeNode = TreeNode.pop()
                  newNode = HuffmanTreeNode()
                  newNode.lchild = letfTreeNode
                  newNode.rchild = rightTreeNode
                  newNode.weight = letfTreeNode.weight + rightTreeNode.weight
                  letfTreeNode.parent = newNode
                  rightTreeNode.parent = newNode
                  self.InsertTreeNode(TreeNode, newNode)
              return TreeNode[0]
      def InsertTreeNode(self, TreeNode, newNode):
          length = len(TreeNode)
          if length > 0:
              temp = length - 1
              while temp >= 0:
                  if newNode.weight < TreeNode[temp].weight:
                      TreeNode.insert(temp+1, newNode)
                      return True
                  temp -= 1
          TreeNode.insert(0, newNode)
  3. 哈夫曼编码
  在数据通信时,假如我们要发送“ABCDEFG”“ABCDEFG”这一串信息,我们并不会直接以这种形式进行发送,而是将其编码成计算机能够识别的二进制形式。根据编码类型可将其分为固定长度编码和可变长度编码,顾名思义,固定长度编码就是编码后的字符长度都相同,可变长度编码就是编码后的字符长度不相同。这两种类型有什么区别呢?我们来举例说明一下:
  “ABCDEFG”“ABCDEFG”这条信息使用固定长度编码后的长度为21,使用可变长度编码后的长度为14,报文变短,报文的传输效率会相应的提高。但如果传送的字符为“BD”“BD”,按可变长度编码后的报文为“111”“111”,但是在译码是就会出现“BBB”,“BD”,“DB”“BBB”,“BD”,“DB”多种结果,因此采用可变长度编码时需要注意任一字符不能是其他字符的前缀,符合这样的可变长度编码称为前缀编码。
  报文最短可以引申到二叉树路径最短,即构造前缀编码的实质就是构造一棵哈夫曼树,通过这种形式获得的二进制编码称为哈夫曼编码。这里的权值就是报文中字符出现的概率,出现概率越高的字符我们用越短的字符表示。
  以下表中的字符及其出现的概率为例来实现哈夫曼编码:
  代码实现就是在哈夫曼树的基础上加一个编码的函数:
      def HuffmanEncode(self, Root):
          TreeNode = self.nodes[:]
          code_result = []
          for index in range(len(TreeNode)):
              temp = TreeNode[index]
              code_leaf = [temp.data]
              code = ''
              while temp is not Root:
                  if temp.parent.lchild is temp:
                      # 左分支
                      code = '0' + code
                  else:
                      # 右分支
                      code = '1' + code
                  temp = temp.parent
              code_leaf.append(code)
              code_result.append(code_leaf)
          return code_result
  测试结果如下:
  if __name__ == '__main__':
      tree_obj = HuffmanTree([('A', 0.01), ('B', 0.43), ('C', 0.15), ('D', 0.02), ('E', 0.03), ('F', 0.21), ('G', 0.07), ('H', 0.08)])
      huf_tree = tree_obj.CreateHuffmanTree()
      huf_code = tree_obj.HuffmanEncode(huf_tree)
      for index in range(len(huf_code)):
          print('{0}: {1}'.format(huf_code[index][0], huf_code[index][1]))

  本文内容不用于商业目的,如涉及知识产权问题,请权利人联系51Testing小编(021-64471599-8017),我们将立即处理

评 论

论坛新帖

顶部 底部


建议使用IE 6.0以上浏览器,800×600以上分辨率,法律顾问:上海信义律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2021, 沪ICP备05003035号
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪公网安备 31010102002173号

51Testing官方微信

51Testing官方微博

扫一扫 测试知识全知道