时间:2020-09-27 python教程 查看: 956
前言
本篇章主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码,并用Python实现。
1. 基本概念
哈夫曼树
其中,
带权路径长度是带权结点和根结点之间的路径长度与该结点的权值的乘积。有关带权结点、路径长度的概念请参阅这篇博客。
对于含有
2. 构造过程及实现
给定
比如
代码实现:
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. 哈夫曼编码
在数据通信时,假如我们要发送
A | B | C | D | E | F | G | |
---|---|---|---|---|---|---|---|
固定长度编码 | 000 | 001 | 010 | 011 | 100 | 101 | 110 |
可变长度编码 | 0 | 1 | 01 | 10 | 11 | 101 | 110 |
报文最短可以引申到二叉树路径最短,即构造前缀编码的实质就是构造一棵哈夫曼树,通过这种形式获得的二进制编码称为哈夫曼编码。这里的权值就是报文中字符出现的概率,出现概率越高的字符我们用越短的字符表示。
以下表中的字符及其出现的概率为例来实现哈夫曼编码:
字符 | A | B | C | D | E | F | G | H |
---|---|---|---|---|---|---|---|---|
出现概率 | 0.01 | 0.43 | 0.15 | 0.02 | 0.03 | 0.21 | 0.07 | 0.08 |
哈夫曼编码 | 101010 | 0 | 110 | 101011 | 10100 | 111 | 1011 | 100 |
代码实现就是在哈夫曼树的基础上加一个编码的函数:
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]))
总结
到此这篇关于Python描述数据结构学习之哈夫曼树篇的文章就介绍到这了,更多相关Python数据结构之哈夫曼树内容请搜索python博客以前的文章或继续浏览下面的相关文章希望大家以后多多支持python博客!