Huffman树与Huffman编码的Python实现
共 20930字，需浏览 42分钟
·
2024-05-07 22:32
在之前的文章二叉树的Python实现和二叉搜索树（BST）的Python实现中，笔者分别介绍了二叉树与二叉搜索树的Python实现。本文将在此基础上，介绍Huffman树和Huffman编码的实现。
Huffman树
首先，我们先来看下什么是
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
其中涉及到的概念如下：
树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和
结点的带权路径长度：是指该结点到树根之间的路径长度与该结点上权的乘积
我们来看个例子：
叶子结点为a,b,c,d,e，图中这颗树的带权路径长度为
4 * 2 + 4 * 2 + 2 * 3 + 3 * 3 + 7 *2 = 45
那么，如何来构建Huffman树呢？
Huffman树的构造(Huffman Algorithm)算法如下：
根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空；
在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和；
在F中删除这两棵树,同时将新的二叉树加入F中；
重复2、3, 直到F只含有一棵树为止(得到哈夫曼树)。
利用我们之前实现的二叉树代码（参考文章 二叉搜索树（BST）的Python实现 中的二叉树实现代码），我们接着使用Python代码来实现Huffman树：
from binary_tree import BTree
values = [7, 19, 2, 6, 32, 3, 21, 10]
tree_list = [BTree(i) for i in values]
while len(tree_list) != 1:
# 每个节点的数值
values = [tree.data for tree in tree_list]
# 从Node_list取两个节点数值最小的节点，并删除这两个节点
min_value_tree = tree_list.pop(values.index(min(values)))
values.pop(values.index(min(values)))
sec_min_value_tree = tree_list.pop(values.index(min(values)))
values.pop(values.index(min(values)))
# 创建二叉树
root_value = min_value_tree.data + sec_min_value_tree.data
root = BTree(root_value)
root.left = min_value_tree
root.right = sec_min_value_tree
# 在原来的Node_list中添加新的root节点
tree_list.append(root)
root.print_tree(label=True)
# 前序遍历，中，左，右
root.pre_order()
print()
# 中序遍历，左，中，右
root.in_order()
print()
# 后序遍历，左，右，中
root.post_order()
print()
# 层次遍历
print(root.level_order())
构建的Huffman树如下：
输出结果为：
100 40 19 21 60 28 11 5 2 3 6 17 7 10 32
19 40 21 100 2 5 3 11 6 28 7 17 10 60 32
19 21 40 2 3 5 6 11 7 10 17 28 32 60 100
[[100], [40, 60], [19, 21, 28, 32], [11, 17], [5, 6, 7, 10], [2, 3]]
Huffman编码
Huffman树的一个重要应用是Huffman编码，而Huffman编码常用于数据解压缩。
Huffman coding
在实际使用Huffman数进行编码过程中，我们可以考虑对基本的文字单位（比如字母、汉字或者NLP中的token）按出现次数作为结点权重，去构建一颗Huffman树。此时，在这棵树中，以左子树路径为0，以右子树路径为1。
这样我们就能得到叶子结点的编码，此时该编码为前缀编码（任何一个字符的编码都不能是另一个字符编码的前缀）。
我们来看下面的例子（以字符串ABCACCDAEAE为例）：
首先我们对二叉搜索树（BST）的Python实现中的二叉树进行改成，新增获取叶子结点方法以及二叉树可视化方法修改（将标签L, R改为0, 1），如下：
# @file: binary_tree.py
class BTree(object):
# 初始化
def __init__(self, data=None, left=None, right=None):
self.data = data # 数据域
self.left = left # 左子树
self.right = right # 右子树
self.dot = Digraph(comment='Binary Tree')
...
# 获取叶子节点
@property
def leaves(self):
if self.data is None:
return []
if self.left is None and self.right is None:
return [self]
return self.left.leaves + self.right.leaves
# 利用Graphviz进行二叉树的可视化
def print_tree(self, save_path='./Binary_Tree.gv', label=False):
# colors for labels of nodes
colors = ['skyblue', 'tomato', 'orange', 'purple', 'green', 'yellow', 'pink', 'red']
# 绘制以某个节点为根节点的二叉树
def print_node(node, node_tag):
# 节点颜色
color = sample(colors,1)[0]
if node.left is not None:
left_tag = str(uuid.uuid1()) # 左节点的数据
self.dot.node(left_tag, str(node.left.data), style='filled', color=color) # 左节点
label_string = '0' if label else '' # 是否在连接线上写上标签，表明为左子树
self.dot.edge(node_tag, left_tag, label=label_string) # 左节点与其父节点的连线
print_node(node.left, left_tag)
if node.right is not None:
right_tag = str(uuid.uuid1())
self.dot.node(right_tag, str(node.right.data), style='filled', color=color)
label_string = '1' if label else '' # 是否在连接线上写上标签，表明为右子树
self.dot.edge(node_tag, right_tag, label=label_string)
print_node(node.right, right_tag)
# 如果树非空
if self.data is not None:
root_tag = str(uuid.uuid1()) # 根节点标签
self.dot.node(root_tag, str(self.data), style='filled', color=sample(colors,1)[0]) # 创建根节点
print_node(self, root_tag)
self.dot.render(save_path) # 保存文件为指定文件
Huffman编码示例：
from binary_tree import BTree
from collections import Counter
# string字符串至少含有两个不同的字符
string = 'ABCACCDAEAE'
counter_dict = Counter(string)
print('各字符出现次数：', counter_dict)
# 返回一个数组的最小值，及其对应的下标
def min_and_index(array):
f_minimum = float('inf')
flag = None
for i in range(len(array)):
if array[i] < f_minimum:
f_minimum = array[i]
flag = i
return f_minimum, flag
# create Huffman Tree
tree_list = [BTree(i) for i in counter_dict.values()]
while len(tree_list) != 1:
# 每个节点的数值
values = [tree.data for tree in tree_list]
# 从Node_list取两个节点数值最小的节点，并删除这两个节点
_, index = min_and_index(values)
min_value_node = tree_list.pop(index)
values.pop(index)
_, index = min_and_index(values)
sec_min_value_node = tree_list.pop(index)
values.pop(index)
# 创建二叉树
root_value = min_value_node.data + sec_min_value_node.data
root = BTree(root_value)
root.left = min_value_node
root.right = sec_min_value_node
# 在原来的Node_list中添加新的root节点
tree_list.append(root)
values.append(root)
root.print_tree(label=True)
# print(root.leaves)
# Huffman Coding
queue = [root]
# node_dict: 节点及其对应的Huffman编码组成的字典
node_dict = {root: ''}
while queue:
node = queue.pop(0)
if node.left is not None:
queue.append(node.left)
node_dict[node.left] = node_dict[node] + '0'
if node.right is not None:
queue.append(node.right)
node_dict[node.right] = node_dict[node] + '1'
# 叶子节点及其对应的Huffman编码
for node in root.leaves:
print(node.data, '--->', node_dict[node])
# code_dict: 单个字符及其对应的Huffman编码
code_dict = {}
for char in counter_dict.keys():
for node in root.leaves:
if counter_dict[char] == node.data and node_dict[node] not in code_dict.values():
code_dict[char] = node_dict[node]
break
print(code_dict)
输出的结果为:
各字符出现次数： Counter({'A': 4, 'C': 3, 'E': 2, 'B': 1, 'D': 1})
2 ---> 00
1 ---> 010
1 ---> 011
3 ---> 10
4 ---> 11
{'A': '11', 'B': '010', 'C': '10', 'D': '011', 'E': '00'}
构建的Huffman树如下图：
由上可知，对于各个字符的编码方式为：A=11, B=010, C=10, D=011, E=00.
观察上述的编码方式可知，这种编码方式是前缀编码（每个字母都是叶子结点，没有一个叶子结点在另一个叶子结点的路径上），因此可以用来做字符串的编解码。而且在满足前缀编码的前提下，Huffman编码的编码效率是最高的，即所用的0-1字符数最少，这就是Huffman编码的魅力。
这里，让我们停下脚步来想一想字符串编解码的问题。一种常见的编解码方式为等长编码，比如对于字符串ABCACCDAEAE，共5个字母，因此如果使用0-1编码的话，每个字符需使用3位编码，此时整个字符串需用11 * 3 = 33位编码，这种编码方式效率并不是最高的。
我们来看看Huffman编码的结果：
from math import floor, log2
# 对原字符串进行Huffman编码
coded_string = ''
for char in string:
coded_string += code_dict[char]
print('压缩后的字符串为%s.' % coded_string)
# 一般方法的编码位数
if bin(len(counter_dict)).count('1') == 1 or len(counter_dict) == 1:
bites = floor(log2(len(counter_dict)))
else:
bites = floor(log2(len(counter_dict))) + 1
# print(bites)
# 一般方法的编码的总位数
original_code_bites = len(string) * bites
# 计算压缩比
ratio = original_code_bites/len(coded_string)
print('一般方法编码后的字符串长度为%s.' % original_code_bites)
print('Huffman编码后的字符串长度为%s.' % len(coded_string))
print('压缩比为%s.' % round(ratio, 3))
输出结果为：
{'A': '11', 'B': '010', 'C': '10', 'D': '011', 'E': '00'}
压缩后的字符串为110101011101001111001100.
一般方法编码后的字符串长度为33.
Huffman编码后的字符串长度为24.
压缩比为1.375.
而对于字符串'BCDEFGhHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'+'A'*10000000，其压缩比达到惊人的6.0。
Huffman decoding
有了Huffman编码，自然也需要对编码后的字符串进行解码。Huffman解码的思想是十分简单的，因为是前缀编码，对于编码后的字符串后，从头开始遍历，直到碰到叶子结点暂停，这样解码出一个字符，如此循环，直到编码后字符串结尾。
我们写一个示例的Huffman解码的Python代码：
code_dict = {'A': '11', 'B': '010', 'C': '10', 'D': '011', 'E': '00'}
secret_string = "110101011101001111001100"
# Huffman Decoding
decoded_string = ''
while secret_string:
for char, code in code_dict.items():
if secret_string.startswith(code):
decoded_string += char
secret_string = secret_string[len(code):]
break
print(decoded_string)
输出结果为ABCACCDAEAE。
注意观察，这样的解码代码效率是比较低的，使用了双重循环，对于长字符串的解码，效率是很低的。我们在本文的txt文件压缩实战部分来演示如何使用bitarray模块来提升Huffman解码效率，从而提升文件的编/解码效率。
其它用途
Huffman树和Huffman编码还有其他用途，其中之一便是刚才讲述过的文件编解码。其它用途列举如下：
判别条件
对于如下的分类判别树（if-else条件）：
如果学生的总成绩数据有10000条，则5％的数据需 1 次比较，15％的数据需 2 次比较，40％的数据需 3 次比较，40％的数据需 4 次比较，因此 10000 个数据比较的次数为：
10000 (5％＋2×15％＋3×40％＋4×40％)＝31500次
而如果使用Huffman数，则可将判别次数减少至22000次，这样可以提升判别树的效率。
word2vec
在NLP中的word2vec算法（一种用于获取词向量的算法）中，对从隐藏层到输出的softmax层这里的计算量进行了改进。为了避免要计算所有词的softmax概率，word2vec采样了霍夫曼树来代替从隐藏层到输出softmax层的映射。
这是Huffman树在NLP领域中的一个精彩应用！
txt文件压缩实战
ok，讲了这么多，我们来看看Huffman编码在文件压缩领域中的作用（也是它的主战场）了。
在这里，我们使用Python中的bitarray模块来提升Huffman编/解码的效率。
import json
from binary_tree import BTree
from collections import Counter
from bitarray import bitarray
# string字符串至少含有两个不同的字符
with open('test2.txt', 'r') as f:
string = f.read()
print('原始文件中的前100个字符：', string[:100])
counter_dict = Counter(string)
print(counter_dict)
# 返回一个数组的最小值，及其对应的下标
def min_and_index(array):
f_minimum = float('inf')
flag = None
for i in range(len(array)):
if array[i] < f_minimum:
f_minimum = array[i]
flag = i
return f_minimum, flag
# create Huffman Tree
tree_list = [BTree(i) for i in counter_dict.values()]
while len(tree_list) != 1:
# 每个节点的数值
values = [tree.data for tree in tree_list]
# 从Node_list取两个节点数值最小的节点，并删除这两个节点
_, index = min_and_index(values)
min_value_node = tree_list.pop(index)
values.pop(index)
_, index = min_and_index(values)
sec_min_value_node = tree_list.pop(index)
values.pop(index)
# 创建二叉树
root_value = min_value_node.data + sec_min_value_node.data
root = BTree(root_value)
root.left = min_value_node
root.right = sec_min_value_node
# 在原来的Node_list中添加新的root节点
tree_list.append(root)
values.append(root)
# Huffman Coding
queue = [root]
# node_dict: 节点及其对应的Huffman编码组成的字典
node_dict = {root: ''}
while queue:
node = queue.pop(0)
if node.left is not None:
queue.append(node.left)
node_dict[node.left] = node_dict[node] + '0'
if node.right is not None:
queue.append(node.right)
node_dict[node.right] = node_dict[node] + '1'
# code_dict: 单个字符及其对应的Huffman编码
code_dict = {}
for char in counter_dict.keys():
for node in root.leaves:
if counter_dict[char] == node.data and node_dict[node] not in code_dict.values():
code_dict[char] = node_dict[node]
break
# 对原字符串进行Huffman编码
coded_string = ''
for char in string:
coded_string += code_dict[char]
# write the result to a file
with open('test2.bin', 'wb') as f:
bitarray(coded_string).tofile(f)
# write the code_dict to a json file
with open('code_dict.json', 'w') as f:
json.dump(code_dict, f)
输出结果为（由于篇幅原因，counter_dict变量只显示了前几个字符）:
原始文件中的前100个字符： 凡人修仙传 第二千三百零一章-第二千三百五十章 第两千三百零一章 再见灵王 话音刚落，他也不等一干空鱼人再说什么，就一张口，喷出那颗山海珠。 此珠方一飞出，立刻迎风滴溜溜的转动而起，一抹艳丽霞光从上面
Counter({'，': 8278, '一': 5472, '的': 5226, '。': 4718, ' ': 3260, '了': 2659, '不': 1929, '道': 1545, '是': 1543, '在': 1362, '这': 1287, '人': 1284, '”': 1283, '大': 1270})
原始文件test2.txt大小为453K，而编码后的test2.bin文件大小为166K，压缩效果较好。如果我们使用Linux中的tar命令: tar -zcvf test2.tar.gz test2.txt，压缩后的test2.tar.gz文件大小为183K。
接下来，我们使用code_dict.json对test2.bin进行Huffman解码，示例代码如下：
import json
from bitarray import bitarray
# read json file
with open('code_dict.json', 'r') as f:
code_dict = json.loads(f.read())
string = bitarray()
with open('test2.bin', 'rb') as fh:
string.fromfile(fh)
secret_string = string[:len(string) - 8] + bitarray(string[len(string) - 8:].to01().strip('0'))
new_code_dict = {key: bitarray(value) for key, value in code_dict.items()}
# Huffman decoding effectively
dec = secret_string.decode(new_code_dict)
print('编码文件解码后的前100个字符：', ''.join(dec)[:100])
输出结果为：
编码文件解码后的前100个字符： 凡人修仙传 第二千三百零一章-第二千三百五十章 第两千三百零一章 再见灵王 话音刚落，他也不等一干空鱼人再说什么，就一张口，喷出那颗山海珠。 此珠方一飞出，立刻迎风滴溜溜的转动而起，一抹艳丽霞光从上面
与原始文件一致。
总结
总结下，本文主要介绍了Huffman树和Huffman编码的原理和Python代码，并介绍了他们的用途，最后再介绍了txt文件压缩实战。
参考文献
霍夫曼编码: https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
哈夫曼（huffman）树和哈夫曼编码: https://www.cnblogs.com/kubixuesheng/p/4397798.html
word2vec原理(二) 基于Hierarchical Softmax的模型: https://www.cnblogs.com/pinard/p/7243513.html
Decoding a Huffman code with a dictionary: https://stackoverflow.com/questions/33089660/decoding-a-huffman-code-with-a-dictionary