写一个程序，为给定的英文文本构造一套哈夫曼编码，并计算压缩比

为了编写一个程序为给定的英文文本构造哈夫曼编码并计算压缩比，我们可以遵循以下步骤：

1. **数据预处理**：
- 收集文本并统计每个字符的频率，将字符及其对应的频率存储在一个字典或映射中。

import collections

def preprocess_text(text):
    char_freq = collections.Counter(text)
    return char_freq

2. **构建哈夫曼树**：
- 使用字符频率创建一个哈夫曼树生成器，如HuffmanNode类，包含合并节点和优先级函数。
- 通过递归合并最小频次的节点直到只剩下一个根节点（即空节点）。

class HuffmanNode:
    def __init__(self, freq=None, char=None, left=None, right=None):
        self.freq = freq
        self.char = char
        self.left = left
        self.right = right
    
    # 合并两个节点
    def merge(self, other):
        if self.freq < other.freq:
            return HuffmanNode(other, other.char, self, other.left)
        else:
            return HuffmanNode(self, self.char, other.left, other)

# 构建哈夫曼树
def build_huffman_tree(freqs):
    nodes = [HuffmanNode(freq=freq, char=char) for char, freq in freqs.items()]
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        new_node = nodes.pop(0).merge(nodes.pop(0))
        nodes.append(new_node)
    return nodes[0]

3. **编码过程**：
- 根据哈夫曼树生成编码规则，从左到右遍历，遇到分支走左边记为0，右边记为1。

def generate_codes(root, code=""):
    if not root.left and not root.right:
        return {root.char: code}
    left_code = generate_codes(root.left, code + "0")
    right_code = generate_codes(root.right, code + "1")
    return {**left_code, **right_code}

huffman_tree = build_huffman_tree(preprocess_text(text))
huffman_codes = generate_codes(huffman_tree)

4. **计算压缩比**：
- 将原始文本替换为哈夫曼编码后的形式。
- 计算压缩前后的字节数，压缩比等于压缩后除以压缩前的字节数。

def compress(text, huffman_codes):
    compressed_text = ""
    for char in text:
        compressed_text += huffman_codes[char]
    return compressed_text

compressed_data = compress(text, huffman_codes)
original_size = len(text.encode())
compressed_size = len(compressed_data)

compression_ratio = original_size / compressed_size