设计一个哈夫曼树编码

哈夫曼树编码是一种用于数据压缩的算法，它通过构建一棵哈夫曼树来实现对数据的压缩。下面是一个简单的实现：

1. 统计各个字符出现的频率，生成字符和频率的列表。
2. 将字符和频率列表按照频率从小到大排序。
3. 从频率最小的两个字符开始构建哈夫曼树，将它们合并成一个节点，并将它们的频率相加作为该节点的频率。
4. 将新生成的节点插入到字符和频率列表中，重新按照频率从小到大排序。
5. 重复步骤3和4，直到只剩下一个节点为止，这个节点就是哈夫曼树的根节点。
6. 根据哈夫曼树的结构，生成每个字符的编码，将每个字符的编码存储在一个编码表中。

下面是一个 Python 实现的例子：

import heapq
import collections
from collections import Counter

# 构建哈夫曼树
def build_huffman_tree(freq_map):
    heap = [[freq, [char, ""]] for char, freq in freq_map.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]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(heap)[1:], key=lambda x: (len(x[-1]), x))

# 统计字符频率
def get_char_frequency(string):
    return collections.Counter(string)

# 生成编码表
def generate_code_table(char_freq):
    huffman_tree = build_huffman_tree(char_freq)
    code_table = {}
    for pair in huffman_tree:
        code_table[pair[0]] = pair[1]
    return code_table

# 压缩数据
def compress(string, code_table):
    compressed = ""
    for char in string:
        compressed += code_table[char]
    return compressed

# 解压数据
def decompress(string, code_table):
    decompressed = ""
    code = ""
    for bit in string:
        code += bit
        if code in code_table.values():
            decompressed += list(code_table.keys())[list(code_table.values()).index(code)]
            code = ""
    return decompressed

# 测试
string = "hello world"
char_freq = get_char_frequency(string)
code_table = generate_code_table(char_freq)
compressed = compress(string, code_table)
decompressed = decompress(compressed, code_table)
print("原字符串：", string)
print("压缩后：", compressed)
print("解压后：", decompressed)

以上代码中，`build_huffman_tree()` 函数用于构建哈夫曼树，`get_char_frequency()` 函数用于统计字符出现的频率，`generate_code_table()` 函数用于生成编码表，`compress()` 函数用于压缩数据，`decompress()` 函数用于解压数据。