基于哈夫曼编码的无损文件压缩器

用最小堆（优先队列）构建哈夫曼树，实现任意文件的 100% 无损 压缩 / 解压，配套自定义 .huf 二进制文件格式、命令行工具、Gradio 可视化界面与性能 benchmark。

功能特性

• 无损压缩 / 解压：文本、二进制文件均可，round-trip 100% 还原
• 自定义 .huf 文件格式：紧凑二进制头（非 pickle），可移植、可校验
• 批量处理：支持多文件 / 整个目录的批量压缩与解压，--skip-existing 轻量断点续传
• 规范哈夫曼编码：文件头只存「符号 + 码长」（不存完整编码），解压时按规范规则重建，头部更小
• CRC32 完整性校验：压缩时写入原始数据校验和，解压时验证，数据损坏可立即发现
• 流式处理大文件：两遍扫描 + 分块读写，内存 O(1) 不随文件大小增长（处理 30MB 文件内存增量 < 5MB）
• 异常处理：文件不存在、空文件、编码表损坏、魔数不匹配等均有友好提示
• 哈夫曼树可视化：Gradio 界面内用 matplotlib 绘制编码树与编码表
• 性能 benchmark：多种类型 / 多种大小的压缩率与耗时对比
• 单元测试：9 个 pytest 用例覆盖空文件 / 单符号 / 256 全字节 / 随机二进制等边界

技术栈

模块	依赖
核心算法	Python 标准库（heapq / struct / collections），零第三方依赖
命令行	argparse（标准库）
可视化界面	gradio + matplotlib + pandas
配置	python-dotenv（.env）
测试	pytest

目录结构

huffman/
├── huffman.py          # 核心库：建树、编码表、位级读写、.huf 序列化、压缩/解压
├── cli.py              # 命令行入口（compress / decompress / info，支持批量）
├── app.py              # Gradio 可视化界面
├── benchmark.py        # 压缩率 / 耗时对比
├── tests/
│   └── test_roundtrip.py   # pytest 无损测试
├── requirements.txt    # 依赖清单
└── .env                # 配置（输出目录、端口、benchmark 大小）

快速开始

核心压缩 / 解压为纯标准库，无需安装任何依赖即可运行：

# 单文件压缩
python cli.py compress 文件.txt -o 文件.txt.huf

# 单文件解压
python cli.py decompress 文件.txt.huf -o 还原.txt

# 查看压缩文件信息
python cli.py info 文件.txt.huf

# 批量压缩多个文件到 out/ 目录
python cli.py compress a.txt b.txt --output-dir out/

# 压缩整个目录
python cli.py compress --dir testdata --output-dir out/

# 批量解压目录下所有 .huf（跳过已存在的还原文件）
python cli.py decompress --dir out --output-dir restored/ --skip-existing

启动图形界面（需 gradio / matplotlib / pandas）：

pip install -r requirements.txt
python app.py          # 浏览器打开 http://127.0.0.1:7860

运行测试与性能对比：

python -m pytest tests/ -v
python benchmark.py     # 多种大小/类型性能对比
python make_demo.py     # 一键四类数据压缩率演示

.huf 文件格式

自定义紧凑二进制格式（不使用 pickle，避免冗余与不可移植性），采用规范哈夫曼编码（头部仅存码长）：

+----------+----------+----------+-----------------------+--------+--------+
| MAGIC 4B | 原大小 8B | 条数 2B  | 每条: 符号 1B + 码长 1B | 补位 1B | 数据体 |
+----------+----------+----------+-----------------------+--------+--------+

解压时先按「码长 + 符号」排序用规范规则重建编码、逆向重建哈夫曼树，再逐位遍历解码，实现无损还原。

benchmark 实测

数据	1 KB	100 KB	1 MB
英文文本	0.61	0.52	0.52
中文文本	0.81	0.65	0.65
重复字节	0.23	0.21	0.21
随机二进制	1.80	1.01	1.00

压缩率 = 压缩后 / 压缩前，越小越好。随机二进制几乎不可压缩（趋近 1），符合信息论——哈夫曼编码只消除符号频率不均衡带来的冗余。

简历亮点

• 手写二进制文件格式（而非调用现成序列化库），体现对底层存储格式的理解
• 规范哈夫曼编码（Canonical Huffman）：头部仅存码长、按规范规则重建编码，进一步压缩头部体积
• CRC32 完整性校验：解压时校验数据完整性，损坏文件可被准确识别
• 流式 / 分块处理大文件：两遍扫描算法，内存 O(1) 不随文件大小增长，可处理远超内存的文件
• 解压时逆向重建编码树逐位解码，而非简单查表
• 覆盖空文件 / 单符号 / 256 全字节 / 随机二进制等边界场景的测试
• 小文件因编码表头开销反而变大——这是哈夫曼编码的固有特性，能讲出这一点体现理解深度

未来扩展

• 断点续传（当前 --skip-existing 为轻量实现）
• 多线程压缩 / 解压（流式分块天然适合并行）
• 多文件归档为单一 .huf（类似 tar）