侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

Python完成哈夫曼树编码过程及原理详解

Python  /  管理员 发布于 7年前   321

哈夫曼树原理

秉着能不写就不写的理念,关于哈夫曼树的原理及其构建,还是贴一篇博客吧。

https:///article/97396.htm

其大概流程

哈夫曼编码代码

# 树节点类构建class TreeNode(object):  def __init__(self, data):    self.val = data[0]    self.priority = data[1]    self.leftChild = None    self.rightChild = None    self.code = ""# 创建树节点队列函数def creatnodeQ(codes):  q = []  for code in codes:    q.append(TreeNode(code))  return q# 为队列添加节点元素,并保证优先度从大到小排列def addQ(queue, nodeNew):  if len(queue) == 0:    return [nodeNew]  for i in range(len(queue)):    if queue[i].priority >= nodeNew.priority:      return queue[:i] + [nodeNew] + queue[i:]  return queue + [nodeNew]# 节点队列类定义class nodeQeuen(object):  def __init__(self, code):    self.que = creatnodeQ(code)    self.size = len(self.que)  def addNode(self,node):    self.que = addQ(self.que, node)    self.size += 1  def popNode(self):    self.size -= 1    return self.que.pop(0)# 各个字符在字符串中出现的次数,即计算优先度def freChar(string):  d ={}  for c in string:    if not c in d:      d[c] = 1    else:      d[c] += 1  return sorted(d.items(),key=lambda x:x[1])# 创建哈夫曼树def creatHuffmanTree(nodeQ):  while nodeQ.size != 1:    node1 = nodeQ.popNode()    node2 = nodeQ.popNode()    r = TreeNode([None, node1.priority+node2.priority])    r.leftChild = node1    r.rightChild = node2    nodeQ.addNode(r)  return nodeQ.popNode()codeDic1 = {}codeDic2 = {}# 由哈夫曼树得到哈夫曼编码表def HuffmanCodeDic(head, x):  global codeDic, codeList  if head:    HuffmanCodeDic(head.leftChild, x+'0')    head.code += x    if head.val:      codeDic2[head.code] = head.val      codeDic1[head.val] = head.code    HuffmanCodeDic(head.rightChild, x+'1')# 字符串编码def TransEncode(string):  global codeDic1  transcode = ""  for c in string:    transcode += codeDic1[c]  return transcode# 字符串解码def TransDecode(StringCode):  global codeDic2  code = ""  ans = ""  for ch in StringCode:    code += ch    if code in codeDic2:      ans += codeDic2[code]      code = ""  return ans# 举例string = "AAGGDCCCDDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA"t = nodeQeuen(freChar(string))tree = creatHuffmanTree(t)HuffmanCodeDic(tree, '')print(codeDic1,codeDic2)a = TransEncode(string)print(a)aa = TransDecode(a)print(aa)print(string == aa)

接下来就是一段一段分析代码

1.树结点类的构建:

共有5个属性:结点的值,结点的优先度,结点的左子结点,结点的右子结点,结点值的编码(这个没有什么好说的,这些属性都是被需要的)

2.创建树结点队列函数:

对于所有的字母结点,我们将其组成一个队列,这里使用list列表来完成队列的功能。将所有树节点够放进列表中,当然传进来的是按优先度从小到大已排序的元素列表

3.为队列添加节点元素,并保证优先度从大到小排列:

当有新生成的结点时,需将其插入列表,并放在合适位置,使队列依然时按优先度从小打到排列的。

4.结点队列类定义:

创建类初始化时需要传进去的是一个列表,列表中的每个元素是由字母与优先度组成的元组。元组第一个元素是字母,第二个元素是优先度(即在文本中出现的次数)

类初始化化时,调用“创建树结点队列函数”,队列中的每个元素都是一个树结点。

类中还包含一个队列规模属性以及另外两个操作函数:添加结点函数和弹出结点函数。

添加结点函数直接调用之前定义的函数即可,输入的参数为队列和新结点,并且队列规模加一

弹出第一个元素则直接调用列表的pop(0)函数,同时队列规模减一

5.计算文本中个字母的优先度,即出现的次数:

定义一个字典,遍历文本中的每一个字母,若字母不在字典里说明是第一次出现,则定义该字母为键,另键值为1,若在字典里有,则只需将相应的键值加一。 遍历后就得到了每个字母出现的次数。

6.由哈夫曼树得到编码表:

这里定义了两个全局字典,用于存放字母编码,一个字典用于编码,另一个字典用于解码,这样程序操作起来比较方便。

这里主要就是遍历,运用的是二叉树的中序遍历。如果明白中序遍历的化,就能看懂这里的代码,每递归到深一层的时候,就在后面多加一个‘0'(左子树)或‘1'(右子树)。

中序遍历我在上一篇博客中讲的还算可以吧,不懂的可以参考一下,否则就可以略过这一段。

这一段是哈夫曼编码的关键,也是难点,希望能够好好理解一下,也是对递归的一个理解。这一点没问题的话,我觉得哈夫曼树真的挺简单的!!!

7.字符串编码,字符串解码:

这两段我就不详细说了,应为已经有编码与解码的字典了,所以对应每一个字母直接在字典里找就好了,而且字典的寻找速度还是相当快的。

差不多了,例子就不举了,确实哈夫曼树比之前的什么八皇后问题还有KMP问题简单多了。

最后向Huffman大神致敬,祝各位学有所成。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。


  • 上一条:
    Python 二叉树的层序建立与三种遍历实现详解
    下一条:
    Python秒算24点实现及原理详解
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 在python语言中Flask框架的学习及简单功能示例(0个评论)
    • 在Python语言中实现GUI全屏倒计时代码示例(0个评论)
    • Python + zipfile库实现zip文件解压自动化脚本示例(0个评论)
    • python爬虫BeautifulSoup快速抓取网站图片(1个评论)
    • vscode 配置 python3开发环境的方法(0个评论)
    • 近期文章
    • 智能合约Solidity学习CryptoZombie第三课:组建僵尸军队(高级Solidity理论)(0个评论)
    • 智能合约Solidity学习CryptoZombie第二课:让你的僵尸猎食(0个评论)
    • 智能合约Solidity学习CryptoZombie第一课:生成一只你的僵尸(0个评论)
    • 在go中实现一个常用的先进先出的缓存淘汰算法示例代码(0个评论)
    • 在go+gin中使用"github.com/skip2/go-qrcode"实现url转二维码功能(0个评论)
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2016-10
    • 2016-11
    • 2018-04
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2022-01
    • 2023-07
    • 2023-10
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客