CompressKit

主题

Huffman 编码 ​

Huffman 编码使用变长前缀码：出现频率高的符号用短码，频率低的用长码。 它构造的二叉树在所有前缀码中平均码长最短，满足 H ≤ L < H + 1（H 为熵）。

工作原理 ​

每次合并两个频率最小的节点，自底向上构建二叉树；从根到叶的路径即为编码 （左 0、右 1）。频率相同时按符号值排序，保证同一输入得到同一棵树、同一份输出。

cpp
struct Node {
    uint32_t symbol = 0;
    uint64_t freq = 0;
    int32_t left = -1;   // -1 = 无孩子
    int32_t right = -1;
};
// 节点存于 vector<Node> arena，用下标当左右孩子，避免指针管理。

本仓库实现 ​

  • 节点存于 vector<Node> arena，用下标代替指针。
  • 频率相同时按符号值排序，保证确定性输出（同一输入 → 同一比特流）。
  • 单符号输入特殊处理：码长为 1，编码为 0。
  • 频率为 0 的符号跳过，不参与编码。
  • 空输入合法：频率表只有 EOF 符号，写入 magic + 频率表 + EOF 码 + CRC。

文件格式 ​

字段大小描述
Magic4 字节HFM2 (0x48 0x46 0x4D 0x32)
频率表大小4 字节小端 uint32（始终 257）
频率表257 × 4 字节小端 uint32 数组（符号 0-255 + EOF）
编码数据可变位流，填充到字节边界
CRC-324 字节小端序，覆盖此前全部字节；解码前强制校验

命令行用法 ​

bash
./build/huffman_cpp encode input.txt output.huf
./build/huffman_cpp decode output.huf restored.txt

动手实验 ​

以下命令默认已执行 make build 与 make test-data；数字为 2.0.0 实测值，量级不应变化。

实验 1：验证熵界 H ≤ L < H + 1 ​

bash
make stats

输出中 huffman 行的 bits/byte 应比 entropy 列高约 0.02（textlike 语料）。 Huffman 码长是整数，无法恰好等于熵，但平均码长一定落在 [H, H+1) 区间内—— 这是最优前缀码的数学保证，make stats 让你直接看到它。

实验 2：整数码长的代价（偏斜分布） ​

bash
python3 -c "
import random; random.seed(42)
open('/tmp/skew.bin','wb').write(bytes(
    ord('A') if random.random() < 0.9 else ord('B') for _ in range(1048576)))"
./build/huffman_cpp encode /tmp/skew.bin /tmp/skew.huf
./build/arithmetic_cpp encode /tmp/skew.bin /tmp/skew.aen
ls -l /tmp/skew.huf /tmp/skew.aen

Huffman 约 145 KB，算术编码约 61 KB。原因：频率表里还有 EOF 符号（频率 1）， 树变成三叶，B 被迫用 2 比特。每个符号至少 1 比特是前缀码的硬限制， 偏斜越极端，这个差距越大。

实验 3：单符号输入的退化 ​

bash
python3 -c "open('/tmp/ones.bin','wb').write(b'A' * 1048576)"
./build/huffman_cpp encode /tmp/ones.bin /tmp/ones.huf
./build/rle_cpp encode /tmp/ones.bin /tmp/ones.rle
ls -l /tmp/ones.huf /tmp/ones.rle

Huffman 约 132 KB（1 MiB × 1 bit/符号 + 表头），RLE 仅 13 字节（一个行程对）。 同一输入、两种算法、一万倍的差距——选对算法比调参数重要得多。

实验 4：CRC 完整性 ​

bash
cp /tmp/skew.huf /tmp/skew-broken.huf
printf '\xff' | dd of=/tmp/skew-broken.huf bs=1 seek=2000 conv=notrunc
./build/huffman_cpp decode /tmp/skew-broken.huf /tmp/out.bin; echo "exit=$?"

解码应失败并输出 checksum mismatch。流内任何字节被改动（包括频率表） 都会被 CRC-32 拦下，绝不会静默解出错误数据。

复杂度 ​

方面复杂度说明
时间（构建树）O(σ log σ)σ = 字母表大小（最大 256）
时间（编码/解码）O(n)n = 输入长度
空间O(σ)频率表 + 树

注意事项 ​

  • 码长必须为整数，因此不如算术编码逼近熵；接近均匀分布时优势不明显。
  • 频率表固定约 1 KiB 开销，对小文件不划算。
  • 对随机数据接近 1× 压缩率（仅增加表头开销）。
  • 详见 基准测试 与 架构概览。