python 霍夫曼树

霍夫曼树（Huffman Tree）是一种用于数据压缩的树形结构。它通过将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而实现对数据的高效压缩。

以下是一个简单的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 sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

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

huffman_tree = build_huffman_tree(freq)
for char, code in huffman_tree:
    print(f"Character: {char}, Code: {code}")

这段代码首先统计了给定文本中每个字符的出现频率，然后使用堆（heap）数据结构构建了霍夫曼树。最后，打印出每个字符对应的霍夫曼编码。