如何逐位读取二进制文件？哈夫曼算法解压实现求助

核心逻辑 #

文件系统仅支持字节级读写，所以必须先将二进制文件内容读入缓冲区，再从缓冲区中逐位提取，配合哈夫曼树的遍历完成解压流程。

缓冲区分配建议 #

• 无需过度纠结大小，直接选用**4KB（4096字节）**作为缓冲区容量即可——这是操作系统通用的页大小，读写效率最优。
• 可直接用栈数组或动态分配内存：比如 char buffer[4096]; 或者 char* buffer = malloc(4096);，动态分配的内存记得用完释放。

从缓冲区提取位的具体实现 #

需要维护三个状态变量跟踪位读取进度：

1. unsigned char current_byte：当前正在解析的字节
2. int bit_pos：当前字节中已处理的位位置（从7到0，对应字节的高位到低位，和哈夫曼编码的输出顺序一致）
3. size_t bytes_read：fread 从文件读取到缓冲区的字节数

示例代码片段 #

// 初始化状态变量
int bit_pos = 7;
size_t bytes_read = 0;
size_t buffer_idx = 0;
unsigned char current_byte;
char buffer[4096];

FILE* compressed_file = fopen("compressed.bin", "rb");
FILE* output_file = fopen("decompressed.txt", "w");

// 预读第一块数据到缓冲区
bytes_read = fread(buffer, 1, sizeof(buffer), compressed_file);
if (bytes_read > 0) {
    current_byte = buffer[buffer_idx++];
}

// 哈夫曼树遍历核心循环
Node* current_node = huffman_root; // 你的哈夫曼树根节点指针
while (1) {
    // 提取当前位：1 或 0
    int bit = (current_byte >> bit_pos) & 1;
    bit_pos--;

    // 根据位值移动到对应子节点
    current_node = bit == 0 ? current_node->left : current_node->right;

    // 到达叶子节点，写入字符并重置到根节点
    if (current_node->is_leaf) {
        fputc(current_node->ch, output_file);
        current_node = huffman_root;
    }

    // 当前字节处理完毕，切换到下一个字节
    if (bit_pos < 0) {
        if (buffer_idx >= bytes_read) {
            // 缓冲区已读完，读取下一块数据
            bytes_read = fread(buffer, 1, sizeof(buffer), compressed_file);
            buffer_idx = 0;
            if (bytes_read == 0) break; // 文件读取完毕，退出循环
        }
        current_byte = buffer[buffer_idx++];
        bit_pos = 7;
    }

    // 关键：处理压缩末尾的填充位
    // 压缩时为了字节对齐补的0，解压前要先从文件中读取填充位数，处理到有效位后立即停止，避免解析无效数据
}

fclose(compressed_file);
fclose(output_file);

必注意事项 #

• 填充位处理：压缩最后一个字节时补的无效0，必须在压缩时将填充位数存入文件（比如开头或结尾），解压时先读取该数值，到对应位置就终止解析。
• 哈夫曼树还原：解压前必须先从压缩文件中读取序列化的哈夫曼树信息（比如字符频率表、节点结构），否则无法构建遍历用的树结构。
• 位序一致性：确保解压时的位读取顺序和压缩时的编码顺序完全一致（比如都是高位优先）。

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