Python实现Huffman压缩：频率表嵌入及树重建异常求助

方案一：嵌入频率表（更简单可靠） #

实现思路 #

ASCII字符共256个，每个字符的频率用4字节无符号整数存储（最大可表示4294967295次出现，覆盖绝大多数场景），总开销仅256*4=1024字节，完全可接受。借助Python的struct模块实现整数与字节流的互转，解决大整数无法直接转bytearray的问题。

压缩时写入频率表 #

import struct

def write_frequency_table(file, freq_table):
    # freq_table为长度256的列表，索引对应ASCII码，值为字符出现次数
    for freq in freq_table:
        # 打包为4字节小端整数，解压时需用对应格式解析
        file.write(struct.pack('<I', freq))

解压时读取频率表 #

def read_frequency_table(file):
    freq_table = []
    for _ in range(256):
        bytes_data = file.read(4)
        freq = struct.unpack('<I', bytes_data)[0]
        freq_table.append(freq)
    return freq_table

读取到频率表后，直接用原始逻辑重建Huffman树即可，逻辑简单不易出错。

方案二：修复当前Huffman树二进制串的生成与重建逻辑 #

你的代码存在三个核心问题，修复后即可正常重建树：

问题1：比特串补0未记录，解压时多余0破坏树结构 #

生成字节数组时，若比特串长度不是8的倍数，直接补0但未记录补0数量，导致解压时树的二进制串被填充多余0，破坏结构。

修复后的__create_bytes函数

import struct

def __create_bytes(self, bitstring):
    # 处理树的二进制串
    tree_bits = self.huffman_tree_binary
    tree_len = len(tree_bits)
    # 计算需要补的0的数量，凑成8的倍数
    tree_pad = (8 - tree_len % 8) % 8
    tree_bits += '0' * tree_pad
    
    # 处理压缩数据的比特串
    data_pad = (8 - len(bitstring) % 8) % 8
    bitstring += '0' * data_pad
    
    byte_array = bytearray()
    # 先写入树的原始长度（4字节），方便解压时拆分
    byte_array.extend(struct.pack('<I', tree_len))
    # 写入补0的数量
    byte_array.append(tree_pad)
    byte_array.append(data_pad)
    
    # 写入树的字节数据
    for i in range(0, len(tree_bits), 8):
        byte = tree_bits[i:i+8]
        byte_array.append(int(byte, 2))
    
    # 写入压缩数据的字节数据
    for i in range(0, len(bitstring), 8):
        byte = bitstring[i:i+8]
        byte_array.append(int(byte, 2))
    
    return byte_array

问题2：生成树时多余的"00"标记导致重建错误 #

调用生成树代码时末尾添加的self.huffman_tree_binary += "00"是多余的，会让重建时尝试创建不存在的节点，直接删除该行：

huffman_tree_root = self.huffman_tree.pop()
current_huffman_code = ""
self.__create_huffman_codes(huffman_tree_root, current_huffman_code)
# 删除 self.huffman_tree_binary += "00" 这行

问题3：树重建逻辑与生成逻辑不匹配 #

生成树时每个节点先输出"0"标记，叶子节点额外输出"1"+8位字符编码；重建时的递归逻辑需要严格对应这个流程。

修复后的重建代码

import struct

def huffman_decompress(self):
    with open('compressed.bin', 'rb') as f:
        # 读取树的原始长度
        tree_len_bytes = f.read(4)
        tree_len = struct.unpack('<I', tree_len_bytes)[0]
        # 读取补0数量
        tree_pad = ord(f.read(1))
        data_pad = ord(f.read(1))
        
        # 读取所有字节并转为完整比特串
        bytes_data = f.read()
        bitstring = ''.join([bin(byte)[2:].rjust(8, '0') for byte in bytes_data])
        
        # 提取树的比特串并去掉补的0
        self.huffman_tree_binary = list(bitstring[:tree_len + tree_pad][:-tree_pad])
        # 提取压缩数据的比特串并去掉补的0
        data_bits = bitstring[tree_len + tree_pad:][:-data_pad]
        
        # 重建Huffman树
        self.huffman_tree_root = self.__rebuild_huffman_tree()
        
        # 后续解压数据逻辑...

def __rebuild_huffman_tree(self):
    if not self.huffman_tree_binary:
        return None
    # 读取节点标记"0"
    self.huffman_tree_binary.pop(0)
    node = Node(None)
    
    # 判断是否为叶子节点
    if self.huffman_tree_binary and self.huffman_tree_binary[0] == "1":
        self.huffman_tree_binary.pop(0)
        # 读取8位字符编码
        bits = ''.join([self.huffman_tree_binary.pop(0) for _ in range(8)])
        node.char = int(bits, 2)
        return node
    
    # 非叶子节点，递归创建左右子树
    node.left = self.__rebuild_huffman_tree()
    node.right = self.__rebuild_huffman_tree()
    return node

修复后生成与重建逻辑完全对应，即可正确还原Huffman树，实现无损解压。

内容的提问来源于stack exchange，提问作者whalebeach