Huffman编码的Python的实现

基本原理及步骤

Huffman编码是一种贪心算法，用于无损数据压缩。它基于字符在数据中出现的频率来构建编码，频率高的字符使用较短的编码，而频率低的字符使用较长的编码。这种方式的目的是减少数据的大小，因为最常见的字符使用最短的编码，从而在整体上减少了所需的位数。
实现Huffman编码的原理如下：

1. 频率统计：
   • 如果输入数据是一个字符串，代码会遍历这个字符串，统计每个字符出现的次数。
   • 如果输入数据是一个字典，它应该包含字符及其对应的频率。代码会直接使用这个字典。
2. 构建优先队列：
   • 根据字符的频率，创建一个优先队列（最小堆），每个元素是一个列表，包含字符的频率和字符本身，以及一个初始为空的编码。
3. 构建Huffman树：
   • 当优先队列中至少有两个元素时，重复以下步骤：
     • 从队列中弹出两个具有最低频率的元素（它们将成为新的树的左右子节点）。
     • 创建一个新的内部节点，其频率是这两个节点频率的和。
     • 将这两个节点作为新节点的子节点，左节点的编码前缀为“0”，右节点的编码前缀为“1”。
     • 将新节点添加回优先队列。
   • 这个过程会一直重复，直到队列中只剩下一个元素，这个元素就是Huffman树的根节点。
4. 生成Huffman编码：
   • 一旦Huffman树构建完成，从根节点开始遍历树，为每个字符生成一个唯一的二进制编码。
   • 左子节点的路径标记为“0”，右子节点的路径标记为“1”。
5. 编码数据：
   • 使用生成的Huffman编码表，将原始数据中的每个字符替换为其对应的二进制编码。
   • 生成的二进制编码字符串就是压缩后的数据。
6. 解码数据：
   • 解码过程需要使用相同的Huffman编码表。
   • 从压缩数据开始，逐位读取，根据Huffman编码表回溯到对应的字符。
   • 每当找到一个匹配的编码，就将对应的字符添加到解码数据中，并继续处理剩余的位。
     Huffman编码的关键优势在于它是一种前缀编码方法，即没有任何一个编码是另一个编码的前缀，这确保了编码的唯一可解性。这种方法在理论上可以达到最小冗余度，即Shannon熵，是效率最高的编码方式之一。

python_28">python实现

python">import heapq  # 导入heapq模块，用于创建优先队列# 使用哈夫曼编码压缩文本数据的函数
def huffman_encode(data):"""使用哈夫曼编码压缩文本数据。:param data: 待压缩的文本数据:return: 压缩后的二进制数据和哈夫曼编码表"""if isinstance(data, str):# 如果data是一个字符串，计算每个字符的频率frequency = {}for char in data:frequency[char] = frequency.get(char, 0) + 1else:# 如果data是一个频率字典，检查其值的总和是否为1if sum(data.values()) != 1:raise ValueError("data is frequency `dict`,must sum values is 1 ")frequency = data# 创建优先队列，每个元素是一个列表 [weight, [char, code]]heap = [[weight, [char, ""]] for char, weight in frequency.items()]heapq.heapify(heap)  # 将列表转换为最小堆# 构建哈夫曼树while len(heap) > 1:lo = heapq.heappop(heap)  # 弹出权重最小的节点hi = heapq.heappop(heap)  # 弹出权重次小的节点for pair in lo[1:]:pair[1] = "0" + pair[1]  # 将左子节点的编码前缀设置为0for pair in hi[1:]:pair[1] = "1" + pair[1]  # 将右子节点的编码前缀设置为1heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])  # 合并节点并重新加入堆# 生成哈夫曼编码huffman_codes = {pair[0]: pair[1] for pair in heap[0][1:]}# 编码数据, 如果形参是频率字典，则会按照字典中字符的顺序输出encoded_data = "".join(huffman_codes[char] for char in data)return encoded_data, huffman_codes  # 返回压缩后的数据和编码表# 使用哈夫曼编码表解码压缩的二进制数据的函数
def huffman_decode(encoded_data, huffman_codes):"""使用哈夫曼编码表解码压缩的二进制数据。:param encoded_data: 压缩后的二进制数据:param huffman_codes: 哈夫曼编码表，其键是字符，值是对应的编码:return: 解码后的原始数据"""# 反转哈夫曼编码表，使得编码成为键，字符成为值reverse_codes = {code: char for char, code in huffman_codes.items()}# 初始化解码数据decoded_data = ""# 当前正在处理的编码片段current_code = ""# 遍历编码数据的每一位for bit in encoded_data:current_code += bit  # 添加当前位到编码片段# 检查当前编码片段是否在反转编码表中if current_code in reverse_codes:decoded_data += reverse_codes[current_code]  # 添加对应的字符到解码数据current_code = ""  # 重置编码片段return decoded_data  # 返回解码后的数据if __name__ == "__main__":# 示例# input_data = "ABRACADABRA!"input_data = {"A": 0.20,"B": 0.19,"C": 0.17,"D": 0.17,"E": 0.14,"F": 0.10,"G": 0.03,}# input_data = (#     "A" * 20 + "B" * 19 + "C" * 18 + "D" * 17 + "E" * 15 + "F" * 10 + "G" * 1# )# input_data = "ABBCCCDDDE"print("Original data:\t", input_data)encoded_data, huffman_codes = huffman_encode(input_data)print("Encoded data:\t", encoded_data)print("Huffman codes:\t", huffman_codes)decoded_data = huffman_decode(encoded_data, huffman_codes)print("Decoded data:\t", decoded_data)

输出如下：

python">Original data:   {'A': 0.2, 'B': 0.19, 'C': 0.17, 'D': 0.17, 'E': 0.14, 'F': 0.1, 'G': 0.03}
Encoded data:    010011011110110011000
Huffman codes:   {'B': '00', 'A': '01', 'G': '1000', 'F': '1001', 'E': '101', 'C': '110', 'D': '111'}
Decoded data:    ABCDEFG