专栏首页算法与编程之美Python|Huffman编码的python代码实现

Python|Huffman编码的python代码实现

1.Huffman编码简介

Huffman编码是依靠Huffman树来实现的,Huffman树是带全路径长度最小的二叉树。

树的带权路径长度为所有叶子节点的权值与到根节点路径长度的乘积之和,公式为:

Huffman编码以根节点到叶子节点的路径来编码的,左为0,右为1

1.1Huffman编码示意图

由这个huffman树得出得huffman编码为:a011,b100,c0001,d00001,e11,f101,g000000,h0010,i010,j0011,k000001。

2.代码思路

用python实现这个需要注意两点,一是根据叶子节点的权值也就是编码字母的值来反向建立huffman树。二是通过建立好的huffman树生成huffman编码。

建立huffman树的主要思路是在给的权值中选最小的和第二小建立节点。将它俩的和放入之前的权值列表再选择其中最小和第二小的,以此循环。

生成huffman编码的思路是用一个列表记录其路径,左为0右为1。当然,为了Huffman树唯一,规定左孩子的值必须小于等于右孩子的值。

3.python代码

#节点类
 class Node(object):
     def  __init__(self,name=None,value=None):
         self._name=name
         self._value=value
         self._left=None
         self._right=None
 #哈夫曼树类
 class HuffmanTree(object):
     #根据Huffman树的思想:以叶子节点为基础,反向建立Huffman树
     def __init__(self,char_weights):
         self.a=[Node(part[0],part[1])  for part in char_weights]  #根据输入的字符及其频数生成叶子节点
         while len(self.a)!=1:
             self.a.sort(key=lambda  node:node._value,reverse=True)
              c=Node(value=(self.a[-1]._value+self.a[-2]._value))
             c._left=self.a.pop(-1)
             c._right=self.a.pop(-1)
             self.a.append(c)
         self.root=self.a[0]
         self.b=list(range(10))       #self.b用于保存每个叶子节点的Haffuman编码,range的值只需要不小于树的深度就行
     #用递归的思想生成编码
     def pre(self,tree,length):
         node=tree
         if (not node):
             return
         elif node._name:
             x=str(node._name) + '的编码为:'
             for i in range(length):
                 x+=str(self.b[i])
             print(x)
             return
         self.b[length]=0
         self.pre(node._left,length+1)
         self.b[length]=1
         self.pre(node._right,length+1)
      #生成哈夫曼编码
     def get_code(self):
         self.pre(self.root,0)
 if __name__=='__main__':
     #输入的是字符及其频数
      char_weights=[('a',7),('b',19),('c',2),('d',6),('e',32),('f',3),('g',21),('h',10)]
     tree=HuffmanTree(char_weights)
     tree.get_code()

4.总结

Huffman树与Huffman编码都是以二叉树为依托的,二叉树是数据结构中非常重要的一环,用python来实现它不仅能将这个知识吃透彻,还能锻炼自己的编程能力。还能偷点小懒,可以不用笔算了输入字母的权值,一秒出答案。

END

编 辑 | 王楠岚

责 编 | 王自强

本文分享自微信公众号 - 算法与编程之美(algo_coding),作者:王自强

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python|520表白神器

    众所周知,5月20日为“520”情人节,这一天也是即将到来,大家都希望与自己的男神女神过一个浪漫的情人节。但是还有很多像小编这样的单身狗,不知道如何向自己的男神...

    算法与编程之美
  • Python|动态规划与回溯求数字个数

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n

    算法与编程之美
  • Python|面向对象编程的类和实例

    Python是一门动态语言,面向对象编程是一个我们必须掌握的重点,而类和实例又是面向对象中的重要概念,由于类是抽象的模板,有点不好理解,所以有很多人不能很好的使...

    算法与编程之美
  • 项目演练 | Python制作一个圣诞抽奖程序,原来如此简单

    下周我们公司的圣诞 Party 活动安排有抽奖环节,由于不方便采用手机抽奖,且目前选用的电脑端在线抽奖会出现卡顿情况,最近我就尝试着用 Python 实现抽奖功...

    龙哥
  • Scrapy爬取知乎------获取用户主页信息

    新建一个scrapy项目,scrapy startproject zhihuspider

    andrew_a
  • iOS---UICollectionView自定义流布局实现瀑布流效果

    用户1941540
  • pygame-KidsCanCode系列jumpy-part2-加速度与摩擦力

    上一节,我们整理了一个游戏开发的新框架(即:Game类),本节将运用这个框架,实现基本的加速度及摩托力效果。

    菩提树下的杨过
  • 从0到1使用python开发一个半自动答题小程序的实现

    最近每天都有玩微信读书上面的每日一答的答题游戏,完全答对12题后,可以瓜分无限阅读卡。但是从小就不太爱看书的我,很难连续答对12道题,由此,产生了写一个半自动答...

    砸漏
  • Python PyQt5模块实现窗口GUI界面代码实例

    PyQt5是基于Digia公司强大的图形程式框架Qt5的python接口,由一组python模块构成。PyQt5本身拥有超过620个类和6000函数及方法。在可...

    砸漏
  • PyQt5 文本输入框自动补全QLineEdit的实现示例

    QStandardItemModel可以用作标准Qt数据类型的存储库。它是模型/视图类之一,是Qt的模型/视图框架的一部分。

    砸漏

扫码关注云+社区

领取腾讯云代金券