哈夫曼编码代码简单易懂

哈夫曼编码是一种可变长度编码，它通过对字符进行不等长编码来压缩数据。对于出现频率较高的字符，它们的编码比较短，而出现频率较低的字符则编码比较长。这种编码方法可以有效地减少数据的存储空间。下面是一个简单易懂的哈夫曼编码的示例代码：

import heapq
from collections import defaultdict

# 哈夫曼树节点类
class Node:
    def __init__(self, freq, char=None):
        self.freq = freq
        self.char = char
        self.left = None
        self.right = None

    # 定义小于号操作符，用于堆排序
    def __lt__(self, other):
        return self.freq < other.freq

# 构建哈夫曼树
def build_huffman_tree(freq_dict):
    heap = []
    for char, freq in freq_dict.items():
        heapq.heappush(heap, Node(freq, char))
    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        new_node = Node(node1.freq + node2.freq)
        new_node.left, new_node.right = node1, node2
        heapq.heappush(heap, new_node)
    return heap

# 递归遍历哈夫曼树，并生成编码表
def traverse_huffman_tree(node, code_table, code=''):
    if node.char:
        code_table[node.char] = code
    else:
        traverse_huffman_tree(node.left, code_table, code + '0')
        traverse_huffman_tree(node.right, code_table, code + '1')

# 哈夫曼编码主函数
def huffman_encode(string):
    freq_dict = defaultdict(int)
    for char in string:
        freq_dict[char] += 1
    root = build_huffman_tree(freq_dict)
    code_table = {}
    traverse_huffman_tree(root, code_table)
    encoded_string = ''
    for char in string:
        encoded_string += code_table[char]
    return encoded_string, code_table

# 哈夫曼解码主函数
def huffman_decode(encoded_string, code_table):
    decoded_string = ''
    current_code = ''
    for bit in encoded_string:
        current_code += bit
        for char, code in code_table.items():
            if code == current_code:
                decoded_string += char
                current_code = ''
                break
    return decoded_string

以上代码中，`build_huffman_tree`函数用于构建哈夫曼树；`traverse_huffman_tree`函数用于遍历哈夫曼树，并生成编码表；`huffman_encode`函数用于对输入字符串进行哈夫曼编码；`huffman_decode`函数用于对编码后的字符串进行解码。