Huffman压缩文件

### Huffman 文件压缩方法及其实现

#### 1. 压缩原理概述
Huffman 编码是一种基于字符频率的无损数据压缩算法。通过对输入文件中的字符进行频率分析，构建一棵二叉树（即霍夫曼树），其中频率较高的字符分配较短的编码，而频率较低的字符则分配较长的编码[^1]。

#### 2. 构建霍夫曼树的过程
首先统计待压缩文件中各个字符出现的频次，并以此为基础创建节点列表。接着按照以下步骤逐步构建霍夫曼树：

- 将所有单个字符作为叶子结点加入优先队列；
- 反复取出两个权值最小的节点组合成新的父节点，直到只剩下一个根节点为止；此时得到的就是完整的霍夫曼树。

import heapq
from collections import defaultdict, Counter


def build_huffman_tree(frequencies):
    heap = [[weight, [symbol, ""]] for symbol, weight in frequencies.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))

#### 3. 字符串编码转换
一旦获得了霍夫曼树之后就可以遍历这棵树来获取每个字符对应的唯一编码字符串。对于每一个字符，在其路径上左转记作`0`右转记作`1`从而形成最终的编码表。

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

#### 4. 数据存储优化
为了提高压缩效率，通常会对经过霍夫曼编码后的位序列进一步处理——比如每8比特打包成一字节保存至磁盘。这样可以充分利用字节边界减少冗余空间浪费。

def compress(encoded_data):
    current_byte = 0
    bits_filled_in_current_byte = 0
    byte_array = bytearray()

    for bit in encoded_data:
        current_byte <<= 1
        if int(bit) == 1:
            current_byte |= 1
        
        bits_filled_in_current_byte += 1
    
        if bits_filled_in_current_byte == 8:
            byte_array.append(current_byte)
            current_bitstring = ''
            current_byte = 0
            bits_filled_in_current_byte = 0
            
    if bits_filled_in_current_byte != 0:
        byte_array.append(current_byte << (8 - bits_filled_in_current_byte))

    return bytes(byte_array)

#### 5. 解压流程说明
解压操作正好相反：先读取已压缩的数据流恢复原始的霍夫曼编码形式，再依据之前建立好的映射关系逐位解析回原来的明文内容。值得注意的是，在实际应用当中还需要额外记录一些元信息以便于正确还原原文件结构。