huffman编码【python】【算法】

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。该方法完全依据字符出现概率来构造整体平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

霍夫曼编码的主要步骤如下：

1. 根据文本内容，进行字符频次统计。
2. 根据频次统计字典，构建霍夫曼树。
   • 树的左节点值不能小于右边节点的值。
   • 当又有节点的值相同时，深度大的节点放在左边。
   • 非叶子节点的值等于两个子节点的值之和。
3. 根据霍夫曼树得到霍夫曼编码字典。
   • 左边路径的值定义为 0，右边路径的值定义为 1。
   • 从根节点开始遍历到达叶子节点，将经过的路径值按照遍历顺序连接起来就是单个字符的编码值。
4. 根据编码字典对文本按照顺序进行编码。

示例代码如下：

# huffman 树的节点
from collections import Counter

from sortedcontainers import SortedList


class TreeNode:
	def __init__(self, name, val):
		self.name = name
		self.value = val
		self.left = None
		self.right = None
		self.len = 1

	def increase_len(self):
		self.len += 1


# 构建 huffman 树
def construct_huffman(plaintext):
	# 统计频次
	chars_freq = Counter(plaintext)
	# 指定排序规则：从小到大排序，频次相同的节点，len 值大的往后排
	nodes = SortedList((TreeNode(k, v) for k, v in chars_freq.items()),
	                   key=lambda x: (x.value, x.len))
	while len(nodes) > 1:
		first_min_node = nodes.pop(0)
		second_min_node = nodes.pop(0)
		# 创建一个新节点
		new_node = TreeNode("", first_min_node.value + second_min_node.value)
		# 为新节点挂上左右叶子
		new_node.left = second_min_node
		new_node.right = first_min_node
		# 更新新节点的深度
		new_node.len = max(first_min_node.len, second_min_node.len)
		# 将新节点插入到排序列表中
		nodes.add(new_node)

	return nodes.pop(0)


# 获取 huffman 编码字典
def get_huffman_code_dict(root):
	code_dict = {}

	# 递归获取编码
	def get_code(node, code):
		if not node:
			return
		if not node.left and not node.right:
			code_dict[node.name] = code
		get_code(node.left, code + "0")
		get_code(node.right, code + "1")

	get_code(root, "")
	return code_dict


# huffman 编码
def huffman_encode(plaintext):
	root = construct_huffman(plaintext)
	code_dict = get_huffman_code_dict(root)
	return "".join(code_dict.get(c) for c in plaintext), code_dict


# huffman 解码
def huffman_decode(ciphertext, code_dict):
	result = []
	while ciphertext:
		for k, v in code_dict.items():
			if ciphertext.startswith(v):
				result.append(k)
				ciphertext = ciphertext[len(v):]
				break
	return "".join(result)


# 测试
root = construct_huffman("编程语言，编程")
ciphertext, code_dict = huffman_encode("编程语言，编程")
print(ciphertext)
decode_text = huffman_decode("1001001000111001", code_dict)
print(decode_text)

上述代码定义了huffman_encode函数用于对文本进行霍夫曼编码，函数返回编码的字符串和霍夫曼编码字典。函数huffman_decode 用于对编码字符串进行解码。

注意，你可以根据实际情况替换上述代码中的测试数据。