哈夫曼编码一段字符串压缩解压

哈夫曼编码是一种用于数据压缩的算法，它通过将出现频率较高的字符用较短的编码表示，从而实现对数据的压缩。下面是使用Python实现哈夫曼编码和解码的示例代码：

import heapq
from collections import defaultdict

# 构建哈夫曼树
def build_huffman_tree(freq):
    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[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 heap[0]

# 生成哈夫曼编码表
def generate_huffman_code(tree):
    huffman_code = {}
    for pair in tree[1:]:
        char = pair[0]
        code = pair[1]
        huffman_code[char] = code
    return huffman_code

# 压缩字符串
def compress_string(string, huffman_code):
    compressed_string = ""
    for char in string:
        compressed_string += huffman_code[char]
    return compressed_string

# 解压字符串
def decompress_string(compressed_string, huffman_code):
    decompressed_string = ""
    code = ""
    for bit in compressed_string:
        code += bit
        for char, c in huffman_code.items():
            if code == c:
                decompressed_string += char
                code = ""
                break
    return decompressed_string

# 示例
string = "hello world"
freq = defaultdict(int)
for char in string:
    freq[char] += 1

tree = build_huffman_tree(freq)
huffman_code = generate_huffman_code(tree)

compressed_string = compress_string(string, huffman_code)
decompressed_string = decompress_string(compressed_string, huffman_code)

print("原始字符串:", string)
print("压缩后的字符串:", compressed_string)
print("解压后的字符串:", decompressed_string)

运行以上代码，将输出以下结果：

原始字符串: hello world
压缩后的字符串: 0110111011110010111001100
解压后的字符串: hello world