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

编  辑   |   王楠岚

责  编   |   王自强

where2go 团队

   

微信号:算法与编程之美          

长按识别二维码关注我们!

温馨提示: 点击页面右下角 “写留言”发表评论,期待您的参与!期待您的转发!

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章