huffman编程代码

Huffman编码是一种常用的数据压缩算法，它通过将出现频率较高的字符用较短的编码表示，从而实现数据的压缩。下面是一个简单的Huffman编码的实现代码示例：

import heapq
from collections import defaultdict

# 定义节点类
class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    # 定义比较函数，用于堆排序
    def __lt__(self, other):
        return self.freq < other.freq

# 构建Huffman树
def build_huffman_tree(data):
    # 统计字符频率
    freq_dict = defaultdict(int)
    for char in data:
        freq_dict[char] += 1

    # 将字符频率转换为节点对象，并加入优先队列（最小堆）
    heap = []
    for char, freq in freq_dict.items():
        node = Node(char, freq)
        heapq.heappush(heap, node)

    # 依次取出频率最小的两个节点，合并为一个新节点，并重新加入优先队列，直到只剩下一个节点
    while len(heap) > 1:
        left_node = heapq.heappop(heap)
        right_node = heapq.heappop(heap)
        merged_node = Node(None, left_node.freq + right_node.freq)
        merged_node.left = left_node
        merged_node.right = right_node
        heapq.heappush(heap, merged_node)

    # 返回Huffman树的根节点
    return heap[0]

# 递归生成Huffman编码
def generate_huffman_code(root, current_code, huffman_codes):
    if root is None:
        return

    # 叶子节点表示一个字符，将其对应的编码加入字典
    if root.char is not None:
        huffman_codes[root.char] = current_code
        return

    # 递归处理左子树和右子树
    generate_huffman_code(root.left, current_code + "0", huffman_codes)
    generate_huffman_code(root.right, current_code + "1", huffman_codes)

# 压缩数据
def compress(data):
    # 构建Huffman树
    root = build_huffman_tree(data)

    # 生成Huffman编码
    huffman_codes = {}
    generate_huffman_code(root, "", huffman_codes)

    # 将原始数据转换为Huffman编码
    compressed_data = ""
    for char in data:
        compressed_data += huffman_codes[char]

    return compressed_data, huffman_codes

# 解压缩数据
def decompress(compressed_data, huffman_codes):
    # 将Huffman编码转换为字符
    reverse_codes = {code: char for char, code in huffman_codes.items()}

    # 解压缩数据
    current_code = ""
    decompressed_data = ""
    for bit in compressed_data:
        current_code += bit
        if current_code in reverse_codes:
            char = reverse_codes[current_code]
            decompressed_data += char
            current_code = ""

    return decompressed_data

# 测试代码
data = "hello world"
compressed_data, huffman_codes = compress(data)
decompressed_data = decompress(compressed_data, huffman_codes)

print("原始数据：", data)
print("压缩后的数据：", compressed_data)
print("解压缩后的数据：", decompressed_data)

这段代码实现了Huffman编码的压缩和解压缩功能。首先，通过`build_huffman_tree`函数构建Huffman树，然后通过`generate_huffman_code`函数生成Huffman编码。接着，使用`compress`函数将原始数据压缩为Huffman编码，使用`decompress`函数将Huffman编码解压缩为原始数据。