Python如何学习哈夫曼树构建数据结构？

本文共计3170个文字，预计阅读时间需要13分钟。

前言本章节主要介绍哈夫曼树及其编码，包括哈夫曼树的基本概念、构造方法、代码实现以及Python示例。

1. 基本概念哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，也称为最优二叉树。其特点是：树中所有叶子结点都带有权值，且没有路径长度相等的叶子结点。

哈夫曼树编码是一种基于哈夫曼树的编码方式，可以有效地降低数据传输的冗余度，提高数据压缩比。

2. 构造方法哈夫曼树的构造方法如下：（1）将所有叶子结点按照权值从小到大排序；（2）将排序后的两个叶子结点合并，形成一个新的父结点，其权值为两个叶子结点权值之和；（3）将新的父结点插入到排序后的叶子结点序列中；（4）重复步骤（2）和（3），直到只剩下一个结点，即为哈夫曼树的根结点。

3. 代码实现以下是用Python实现哈夫曼树的示例代码：

pythonclass Node: def __init__(self, char, freq): self.char=char self.freq=freq self.left=None self.right=None

def merge_nodes(left, right): merged=Node(None, left.freq + right.freq) merged.left=left merged.right=right return merged

def build_huffman_tree(char_freq): nodes=[Node(char, freq) for char, freq in char_freq.items()] while len(nodes) > 1: nodes.sort(key=lambda x: x.freq) left=nodes.pop(0) right=nodes.pop(0) merged=merge_nodes(left, right) nodes.append(merged) return nodes[0]

def get_huffman_code(node, prefix=, code={}): if node is None: return code if node.char is not None: code[node.char]=prefix get_huffman_code(node.left, prefix + 0, code) get_huffman_code(node.right, prefix + 1, code) return code

示例：哈夫曼树编码char_freq={'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}huffman_tree=build_huffman_tree(char_freq)huffman_code=get_huffman_code(huffman_tree)print(huffman_code)

4. 哈夫曼树编码以下是用Python实现哈夫曼树编码的示例代码：

pythondef huffman_encode(text, code): encoded_text= for char in text: encoded_text +=code[char] return encoded_text

示例：哈夫曼树编码应用text=this is an example for huffman encodingencoded_text=huffman_encode(text, huffman_code)print(encoded_text)

前言

本篇章主要介绍哈夫曼树及哈夫曼编码，包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码，并用Python实现。

1. 基本概念

哈夫曼树$$(Huffman(Huffman(Huffman $$Tree)Tree)Tree)，又称为最优二叉树，指的是带权路径长度最小的二叉树。树的带权路径常记作：
$$

其中，$$nnn为树中叶子结点的数目，$$wkw_kwk​为第$$kkk个叶子结点的权值，$$lkl_klk​为第$$kkk个叶子结点与根结点的路径长度。

带权路径长度是带权结点和根结点之间的路径长度与该结点的权值的乘积。有关带权结点、路径长度的概念请参阅这篇博客。

对于含有$$nnn个叶子结点的哈夫曼树，其共有$$2n−12n-12n−1个结点。因为在构造哈夫曼树的过程中，每次都是以两颗二叉树为子树创建一棵新的二叉树，因此哈夫曼树中不存在度为1的结点，即$$n1=0n_1=0n1​=0，由二叉树的性质可知，叶子结点数目$$n0=n2+1n_0=n_2+1n0​=n2​+1，所以$$n2=n0−1n_2=n_0-1n2​=n0​−1，总结点数目为$$n=n0+n1+n2=n+n−1=2n−1n=n_0+n_1+n_2=n+n-1=2n-1n=n0​+n1​+n2​=n+n−1=2n−1。

2. 构造过程及实现

给定$$nnn棵仅含根结点的二叉树$$T1,T2,…,TnT_1,T_2,\dots,T_nT1​,T2​,…,Tn​，它们的权值分别为$$w1,w2,…,wnw_1,w_2,\dots,w_nw1​,w2​,…,wn​，将它们放入到一个集合$$FFF中，即$$F={T1,T2,…,Tn}F=\{T_1,T_2,\dots,T_n\}F={T1​,T2​,…,Tn​}；然后在集合$$FFF中选取两棵权值最小的根结点构造一棵新的二叉树，使新二叉树的根结点的权值等于其左、右子树根结点的权值之和；再然后将选中的那两个结点从集合$$FFF中删除，将新的二叉树添加到$$FFF中；继续重复上述操作，直至集合$$FFF中只剩一棵二叉树为止。

比如$$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)\}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”这一串信息，我们并不会直接以这种形式进行发送，而是将其编码成计算机能够识别的二进制形式。根据编码类型可将其分为固定长度编码和可变长度编码，顾名思义，固定长度编码就是编码后的字符长度都相同，可变长度编码就是编码后的字符长度不相同。这两种类型有什么区别呢？我们来举例说明一下：

  AA BB CC DD EE FF GG 固定长度编码 000000 001001 010010 011011 100100 101101 110110 可变长度编码 00 11 0101 1010 1111 101101 110110

$$“ABCDEFG”“ABCDEFG”“ABCDEFG”这条信息使用固定长度编码后的长度为21，使用可变长度编码后的长度为14，报文变短，报文的传输效率会相应的提高。但如果传送的字符为$$“BD”“BD”“BD”，按可变长度编码后的报文为$$“111”“111”“111”，但是在译码是就会出现$$“BBB”,“BD”,“DB”“BBB”,“BD”,“DB”“BBB”,“BD”,“DB”多种结果，因此采用可变长度编码时需要注意任一字符不能是其他字符的前缀，符合这样的可变长度编码称为前缀编码。

报文最短可以引申到二叉树路径最短，即构造前缀编码的实质就是构造一棵哈夫曼树，通过这种形式获得的二进制编码称为哈夫曼编码。这里的权值就是报文中字符出现的概率，出现概率越高的字符我们用越短的字符表示。

以下表中的字符及其出现的概率为例来实现哈夫曼编码：

字符 AA BB CC DD EE FF GG HH 出现概率 0.010.01 0.430.43 0.150.15 0.020.02 0.030.03 0.210.21 0.070.07 0.08 哈夫曼编码 101010101010 00 110110 101011101011 1010010100 111111 10111011 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数据结构之哈夫曼树内容请搜索易盾网络以前的文章或继续浏览下面的相关文章希望大家以后多多支持易盾网络！