简单的哈夫曼编码实现

哈夫曼编码是一种用于无损数据压缩的熵编码算法。它的基本思想是：根据字符出现的频率，为频率高的字符分配较短的编码，而为频率低的字符分配较长的编码。这样，整个文件中的平均编码长度会减少，从而实现压缩。

下面是一个简单的哈夫曼编码实现步骤：

1. 统计字符频率：遍历文件，统计每个字符出现的频率。
2. 构建哈夫曼树：根据字符频率，使用优先队列（最小堆）构建哈夫曼树。每次从优先队列中取出两个最小频率的节点，合并成一个新的节点，新节点的频率为这两个节点的频率之和，然后将新节点放回优先队列。重复这个过程，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
3. 生成哈夫曼编码：从根节点开始，向左子树走标记为0，向右子树走标记为1，直到叶子节点，此时的路径就是该叶子节点对应字符的哈夫曼编码。
4. 编码文件：遍历文件，将每个字符替换为其对应的哈夫曼编码。

下面是一个简单的哈夫曼编码实现的Python代码：

import heapq
from collections import defaultdict

def huffman_encoding(data):
    # 统计字符频率
    freq = defaultdict(int)
    for char in data:
        freq[char] += 1

    # 构建哈夫曼树
    heap = [[weight, [char, ""]] for char, weight in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair = '0' + pair
        for pair in hi[1:]:
            pair = '1' + pair
        heapq.heappush(heap, [lo + hi] + lo[1:] + hi[1:])

    # 生成哈夫曼编码
    huff_tree = heap
    huff_code = {char: code for char, code in huff_tree[1:]}

    # 编码文件
    encoded_data = "".join(huff_code[char] for char in data)
    return encoded_data, huff_code

data = "hello, world!"
encoded_data, huff_code = huffman_encoding(data)
print("Encoded data:", encoded_data)
print("Huffman codes:", huff_code)

这段代码首先统计输入字符串中每个字符的频率，然后根据频率构建哈夫曼树，接着生成哈夫曼编码，最后将输入字符串中的每个字符替换为其对应的哈夫曼编码。