哈夫曼解析

一、Huffman 编码的理论基础

Huffman 编码是一种最优前缀码——给定字符频率分布，它生成的变长编码使得期望码长最小，且没有任何一个编码是另一个编码的前缀（前缀性保证解码无歧义）。

1.1 前缀码与 Kraft 不等式

设字符集为 {c_1, c_2, …, c_n}，对应码长为 l_1, l_2, …, l_n。存在前缀码的充要条件是 Kraft 不等式成立：
∑(2^(-l_i)) ≤ 1

必要性证明思路：将每个编码映射到二叉树的一条路径（0 = 左子树，1 = 右子树）。前缀性意味着没有编码是另一个的祖先——所有编码对应的叶子节点互不包含。深度为 l_i 的叶子节点”占据”了 2^(-l_i) 的叶子空间比例。所有叶子不重叠，比例之和不超过 1。

充分性证明思路：给定满足 Kraft 不等式的码长序列，可以按码长升序贪心地为每个码字分配一条二叉树路径（优先取左子树的空闲路径），必定成功——因为 Kraft 条件恰好保证了空间充足。

1.2 Huffman 的最优性

定理：Huffman 算法生成的编码在所有前缀码中使期望码长达到最小。

交换论证（Exchange Argument）证明轮廓：

引理 1：在最优编码树中，频率最低的两个字符一定位于最深的位置（否则交换可以降低期望码长）。
引理 2：频率最低的两个字符可以共享同一个父节点而不影响最优性（因为它们在最优树中已经是最深的，合并它们产生的新”虚拟字符”频率为两者之和）。
引理 3：将含 n 个字符的最优编码问题转化为含 n-1 个字符的问题（合并两个最低频率字符），递归地应用 Huffman 算法即得全局最优。

合并最低频率的两个字符相当于贪心选择——这恰好是该问题具有最优子结构和贪心选择性质的体现。

1.3 Huffman 编码的理论性能边界

对于单符号编码（逐符号编码），Huffman 的期望码长 L 满足：
H(X) ≤ L < H(X) + 1

其中 H(X) = ∑ p_i · (-log₂ p_i) 是信源熵。这 +1 bit 的上界在符号独立的情况下无法突破。但实际数据中的符号不是独立的——字符之间存在上下文相关性。这解释了为何 Huffman 编码单独使用压缩率不及上下文自适应编码。

---

二、Huffman 编码的算法实现

2.1 标准 Huffman 树构建

HUFFMAN(freq[1..n]):
    // 1. 初始化含 n 个叶子节点的最小堆
    Q = MIN-HEAP()
    for i = 1 to n:
        Q.insert(NODE(freq[i], char=characters[i]))

    // 2. 反复合并频率最低的两个节点
    while Q.size > 1:
        left  = Q.extract_min()
        right = Q.extract_min()
        parent = NODE(freq = left.freq + right.freq,
                      left = left, right = right)
        Q.insert(parent)

    // 3. 最后的节点即 Huffman 树根
    return Q.extract_min()

// 4. 从根 DFS 分配编码：走左分支加 0，走右分支加 1

时间复杂度：堆初始化为 O(n)，每次 extract_min 和 insert 为 O(log n)，共 2n-2 次操作，总复杂度 O(n log n)。

2.2 C++ 实现

#include <queue>
#include <unordered_map>
#include <vector>
#include <string>

struct HuffNode {
    char ch;
    int freq;
    HuffNode *left, *right;
    HuffNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    HuffNode(int f, HuffNode* l, HuffNode* r) : ch(0), freq(f), left(l), right(r) {}
};

struct Compare {
    bool operator()(HuffNode* a, HuffNode* b) { return a->freq > b->freq; }
};

std::unordered_map<char, std::string> buildHuffman(
    const std::unordered_map<char, int>& freq
) {
    std::priority_queue<HuffNode*, std::vector<HuffNode*>, Compare> pq;

    for (auto& [ch, f] : freq) {
        pq.push(new HuffNode(ch, f));
    }

    while (pq.size() > 1) {
        auto left = pq.top(); pq.pop();
        auto right = pq.top(); pq.pop();
        pq.push(new HuffNode(left->freq + right->freq, left, right));
    }

    std::unordered_map<char, std::string> codes;
    std::function<void(HuffNode*, std::string)> dfs =
        [&](HuffNode* node, std::string code) {
            if (!node) return;
            if (!node->left && !node->right) {
                codes[node->ch] = code.empty() ? "0" : code;  // 单字符特殊处理
                return;
            }
            dfs(node->left, code + '0');
            dfs(node->right, code + '1');
        };
    dfs(pq.top(), "");
    return codes;
}

边界情况：当只有一种字符时，Huffman 编码退化为 "0"（1 比特表示），解码时必须确保这是唯一可能的解释。

---

三、Canonical Huffman Code

真实的压缩格式（JPEG、DEFLATE、PNG）几乎从不存储完整的 Huffman 树（空间开销太大），而是使用规范 Huffman 编码——只需存储每个符号的码长，编码值按确定性的规则重新生成。

3.1 规范 Huffman 的性质

1. 码长升序排列：短码的数值小于长码的数值
2. 相同码长的编码是连续的整数值
3. 从较短码长过渡到较长码长时：first_code[L] = (first_code[L-1] + count[L-1]) << 1

3.2 规范 Huffman 的重建算法

// 输入: bit_lengths[0..255] = 每个 symbol 的码长（0 表示该符号未出现）
// 输出: codes[0..255] = 每个 symbol 的 Huffman 码字
void generateCanonicalCodes(
    const uint8_t bit_lengths[256],
    uint32_t codes[256]
) {
    // 1. 统计每种码长的符号数（bl_count[len] = 码长为 len 的符号数）
    uint16_t bl_count[16] = {0};  // 最长码长 ≤ 15
    for (int i = 0; i < 256; i++) {
        if (bit_lengths[i] > 0) bl_count[bit_lengths[i]]++;
    }

    // 2. 计算每种码长的起始码
    uint32_t code = 0;
    uint32_t next_code[16] = {0};
    for (int bits = 1; bits <= 15; bits++) {
        code = (code + bl_count[bits - 1]) << 1;
        next_code[bits] = code;
    }

    // 3. 按符号顺序分配码字（只分配码长 > 0 的符号）
    for (int i = 0; i < 256; i++) {
        int len = bit_lengths[i];
        if (len > 0) {
            codes[i] = next_code[len]++;
        }
    }
}

关键点：规范 Huffman 码字的 bit 序在存储时需要反转——编码时将最低有效位先写入，解码时按此序还原。这与 DEFLATE 和 JPEG 规范一致。反转的原因：bit 流通常是 LSB first（低位在前），而规范的构建是按 MSB first（高位在前）进行的。

---

四、Huffman 编码在图像格式中的应用

4.1 JPEG 中的 Huffman 编码

JPEG 压缩管线中，经过 DCT → 量化 → Zig-Zag 扫描后，系数被编码为（run-length, category）对，然后使用 Huffman 编码进一步压缩。

DC 系数的差分编码

相邻 8×8 块的 DC 系数高度相关，JPEG 对 DC 系数采用 DPCM（差分编码）：
ΔDC_i = DC_i - DC_{i-1}

差分值的编码分为两步：

1. 查表确定 Δ 值的 magnitude category（如 category=3 表示 -7～-4 或 4～7）
2. category 本身用 Huffman 编码（DC Huffman 表），category 内的 VLI（Variable Length Integer）用 category 个 bit 直接编码

AC 系数的游程编码

Zig-Zag 扫描后，非零 AC 系数之前有连续多个零。JPEG 将 (run_length, category) 组合编码为一个 Huffman 码字——即 run/category 联合查表（AC Huffman 表）。EOB（End Of Block）是一个特殊 Huffman 码字，表示块中剩余所有系数全为零。

ZRL（Zero Run Length）：当 run_length 超过 15 时，使用 ZRL（run=15, category=0）编码 16 个连续的零，然后继续编码剩余的零。

4.2 DEFLATE 中的 Huffman 编码

DEFLATE（用于 gzip、PNG、ZIP、HTTP Content-Encoding）采用 LZ77 + Huffman 的两级压缩：

1. LZ77 产生两种输出：(a) literal 字节 (b) (length, distance) 匹配对
2. literal 值和 length 值合并为一个 alphabet（0-285），用一棵 Huffman 树编码
3. distance 值（0-29）用另一棵 Huffman 树编码

DEFLATE 引入动态 Huffman 码——根据数据的实际统计动态构建 Huffman 树，并将码长表编码进压缩流。与”固定 Huffman 码”相比，动态码通常压缩率更高，但需要在流中传输码长表。

DEFLATE 对 Huffman 码长表本身再进行一层 run-length 编码（使用重复码——重复 3-6 次或 7-138 次），进一步压缩描述 Huffman 码长的开销。

4.3 PNG IDAT 中的 Huffman

PNG 的 IDAT chunk 数据使用 DEFLATE 格式压缩（RFC 1951）。在 filter byte 之后的所有像素数据都经过 DEFLATE 压缩。PNG 的滤波（Predictor）在压缩前对每一行做预处理（如 Sub、Up、Average、Paeth），提高了相邻像素的相似性，进而提高 Huffman 的压缩效果。

---

五、Huffman 解码器实现

5.1 逐 bit 解码

uint8_t decodeSymbol(const HuffNode* root, BitReader& reader) {
    const HuffNode* node = root;
    while (!node->isLeaf()) {
        int bit = reader.readBit();
        node = bit == 0 ? node->left : node->right;
    }
    return node->ch;
}

缺点：每解码一个 bit 需要一次分支判断——对于高吞吐场景，速度不够。

5.2 查表法解码（Table Lookup）

对于固定数量的前导 bits（如 8～10 bits），预先建立查找表：

struct DecodeEntry {
    uint8_t symbol;     // 解码出的字符
    uint8_t length;     // 实际消耗的 bit 数（≤ 查找表位宽）
};

DecodeEntry table[256];  // 8-bit 查找表（对于码长 ≤ 8 的符号）
// 对于码长 > 8 的符号，需要二级查找表
DecodeEntry table2[...]; // 二级表

void buildLookupTable(const uint8_t bit_lengths[256]) {
    uint32_t codes[256];
    generateCanonicalCodes(bit_lengths, codes);

    for (int sym = 0; sym < 256; sym++) {
        int len = bit_lengths[sym];
        if (len == 0) continue;
        if (len <= 8) {
            // 填充一级表：该码字所有可能的后缀
            uint32_t prefix = codes[sym] << (8 - len);  // 补齐到 8 bits
            uint32_t suffix_count = 1 << (8 - len);
            for (uint32_t suffix = 0; suffix < suffix_count; suffix++) {
                table[prefix | suffix] = {sym, (uint8_t)len};
            }
        }
        // len > 8 的符号：使用二级表
    }
}

uint8_t decodeSymbolFast(BitReader& reader) {
    uint32_t peek = reader.peekBits(8);
    DecodeEntry entry = table[peek];
    reader.consumeBits(entry.length);
    return entry.symbol;
}

查表法的优缺点：一次解 8 bit，可以一次查表完成短码的解码；对长码（超过查表位宽）需采用二级查表或多级查表。DEFLATE 使用 9-bit 的初始查找表，JPEG 因码长 ≤ 16 通常使用 8-bit 查找表 + 二级表。

5.3 多级表查找优化

对于码长分布范围大的情况（如 DEFLATE 中最长码长 15），使用单级 15-bit 表需要 32768 个条目（不实际）。多级表策略：

1. 在码长[1, 8]范围内使用 8-bit 一级表
2. 码长 > 8 的符号，在一级表中使用”逃逸”标记，指向二级表
3. 二级表根据剩余的 bits 索引

---

六、Huffman 在 Android NDK 上的实战

6.1 JNI 接口设计

extern "C" JNIEXPORT jbyteArray JNICALL
Java_com_example_compress_HuffmanCompressor_compress(
    JNIEnv* env, jobject /* this */, jbyteArray input
) {
    // 1. 获取输入数据
    jsize len = env->GetArrayLength(input);
    jbyte* data = env->GetByteArrayElements(input, nullptr);

    // 2. 频率统计
    int freq[256] = {0};
    for (int i = 0; i < len; i++) freq[(uint8_t)data[i]]++;

    // 3. 构建 Huffman 树
    auto codes = buildHuffmanFromFreq(freq);

    // 4. 编码
    BitWriter writer;
    // 先写码长表 (256 bytes)
    for (int i = 0; i < 256; i++) writer.writeBits(codes[i].length(), 8);
    // 再写原始字节数
    writer.writeBits(len, 32);
    // 写编码后的数据
    for (int i = 0; i < len; i++)
        writer.writeCode(codes[(uint8_t)data[i]]);

    env->ReleaseByteArrayElements(input, data, 0);

    // 5. 返回压缩后的数据
    auto compressed = writer.toByteArray();
    jbyteArray result = env->NewByteArray(compressed.size());
    env->SetByteArrayRegion(result, 0, compressed.size(),
                            (jbyte*)compressed.data());
    return result;
}

6.2 BitWriter / BitReader 实现

class BitWriter {
    std::vector<uint8_t> buf;
    uint32_t current = 0;
    int bitsUsed = 0;

public:
    void writeBits(uint32_t value, int numBits) {
        for (int i = numBits - 1; i >= 0; i--) {
            current = (current << 1) | ((value >> i) & 1);
            if (++bitsUsed == 8) { buf.push_back(current); current = 0; bitsUsed = 0; }
        }
    }
    void flush() { if (bitsUsed > 0) { current <<= (8 - bitsUsed); buf.push_back(current); } }
    std::vector<uint8_t> toByteArray() { flush(); return buf; }
};

class BitReader {
    const uint8_t* data;
    size_t size, bytePos = 0;
    int bitPos = 0;

public:
    BitReader(const uint8_t* d, size_t s) : data(d), size(s) {}
    int readBit() {
        if (bytePos >= size) return -1;
        int bit = (data[bytePos] >> (7 - bitPos)) & 1;
        if (++bitPos == 8) { bitPos = 0; bytePos++; }
        return bit;
    }
};

---

七、Huffman 编码的局限性及现代替代方案

7.1 理论限制

Huffman 对于单符号编码，期望码长 L 满足 H(X) ≤ L < H(X) + 1。这个 +1 bit 的上界在符号独立的情况下无法突破。但实际数据中的符号不是独立的——字符间存在上下文相关性。

7.2 算术编码 vs Huffman

算术编码将整个消息编码为一个 [0, 1) 区间的实数，不需要为每个符号分配整数个 bit。其期望码长可以达到 H(X) ≤ L < H(X) + 2/n（n 为消息长度），比 Huffman 的 +1 bit 更接近熵下界。

现代压缩格式（H.264/H.265 的 CABAC、JPEG 2000、JPEG XL、Brotli、Zstandard）均采用算术编码或其自适应变体。Huffman 的持续存在主要是因为：专利历史（算术编码长期受 IBM 专利限制）、解码速度（Huffman 的查表法解码非常快）、格式兼容性（JPEG、PNG、DEFLATE 的海量存量文件）。

7.3 ANS（Asymmetric Numeral Systems）

ANS 是 2014 年左右流行起来的新型熵编码，兼具 Huffman 的速度和算术编码的压缩率。Facebook 的 Zstandard（RFC 8878）采用了 Finite State Entropy（FSE），即 tANS（tabled ANS）的一种实现，其压缩率接近算术编码，解码速度与 Huffman 在同一数量级。Apple 的 LZFSE 也使用 ANS。ANS 被认为是当前最优秀的通用熵编码方法。

ANS 的核心思想：将消息编码为一个自然数 x。编码时，将符号 s 和当前状态 x 映射为新状态 x’ = C(x, s)；解码时，从 x’ 恢复 s 和 x = D(x’)。通过精心设计编码表 C 使得 x’ 的分布近似于 P(s)，从而实现接近熵的压缩率。

---

面试常考问题

Q1：Huffman 编码为什么是最优的？用交换论证简要证明。

首先，最优前缀树中频率最低的两个符号一定在最深层（若不然，与之交换深度可以降低期望码长）。其次，这两个最低频率符号可以共享父节点合并为一个”超级符号”而不影响最优性。由此将 n 符号问题归约为 n-1 符号问题，Huffman 算法的贪心过程恰好完成此归约，因此得到的编码是最优的。

Q2：规范 Huffman 编码和标准 Huffman 编码的差异？为什么真实格式用规范版？

标准 Huffman 需存储完整树结构。规范 Huffman 只需存储每个符号的码长（256 bytes 即完整描述码表），接收端按确定性的重建算法恢复所有码字。规范版存储开销大幅降低，且码长表本身可进一步被 run-length 编码压缩——这正是 DEFLATE 的做法。

Q3：Huffman 编码的压缩率为什么不如算术编码？

Huffman 对每个符号分配整数个 bit，即使符号概率为 0.01，也必须分配 ≥1 bit，产生的最优码长期望为 ∑ p_i · ceil(-log₂ p_i)，而熵下界是 ∑ p_i · (-log₂ p_i)。当符号概率不是 2 的幂次时，Huffman 的舍入误差（fractional bit waste）无法避免。算术编码将整个消息编码为一个实数，符号的编码位数可以是分数的，几乎达到熵下界。

Q4：在 Android 中实现 Huffman 压缩，Java 和 Native 差异大吗？

较大。Huffman 编码涉及大量位操作（shift, OR, masking），Java 中所有位操作都涉及 int/long 的 boxing 推断和数组边界检查。NDK 的 C++ 实现可以用 uint8_t* 直接操作字节数组，避免 JNI 调用开销。实测在 1MB 文本压缩中，native 版本通常快 3-5 倍。另外 native 端的 BitWriter/BitReader 可以利用 ARM NEON 的 vector bit-shift 指令进一步优化。

Q5：为什么 DEFLATE 要对 Huffman 码长表再进行 run-length 编码？

DEFLATE 支持动态 Huffman 码，需要在压缩流中传输 256+ 个符号的码长。当大量符号的码长为 0（未出现在输入中）时，逐符号写码长（256 bytes）效率低。Run-length 编码用重复码表示”连续 N 个符号的码长为 0（或重复某个码长）”，将码长表的描述从数百字节压缩到几十字节。这是”压缩描述压缩数据的元数据”的典型案例。

---

八、Huffman 编码在特定 Android 场景中的应用

8.1 APK 压缩中的 DEFLATE 使用

APK 本质上是一个 ZIP 文件，ZIP 内部的每个文件条目可以使用 DEFLATE 或 stored（未压缩）模式。DEFLATE 使用 Huffman + LZ77：

ZIP 文件格式中的 DEFLATE 条目：
[local file header] [DEFLATE compressed data] [data descriptor]

Android 构建工具（AAPT2）默认对 resources.arsc 和 classes.dex 使用最大压缩级别（9），对已压缩的媒体文件（PNG、JPEG、MP3）使用 stored 模式（不重新压缩以避免膨胀）。

8.2 WebP 格式的 Huffman 使用

WebP 的压缩模式中使用 Huffman 编码（在 VP8 视频压缩框架下）：

WebP 有损模式 = VP8 视频帧（内部使用 Huffman 编码变换系数）
WebP 无损模式 = 创新算法，不使用 Huffman（使用不同的熵编码）

Android 4.0+ 原生支持 WebP，4.2+ 支持透明 WebP。Glide/Coil 使用 BitmapFactory 或 libwebp 解码 WebP，其中 Huffman 解码在 native 层完成。

8.3 Brotli 压缩与 Android

Android 5.0+ 支持 Brotli 压缩作为 Web 内容编码。Brotli 使用基于上下文的 Huffman 编码（与 DEFLATE 相似但码表更复杂）：

Brotli 与 DEFLATE 的 Huffman 差异：
- Brotli 使用静态 Huffman 码表（预定义的），动态码表（根据数据生成），和混合模式
- Brotli 的 Huffman 码长可达 15 bits（与 DEFLATE 相同）
- Brotli 使用 2D 上下文模型——当前符号的 Huffman 编码取决于前一个符号的上下文
- 压缩率：Brotli 通常比 DEFLATE 高出 20%-26%（文本数据）

九、Huffman 编码的性能优化技巧

9.1 频率排序优化

在构建 Huffman 树时，使用桶排序（counting sort）代替堆排序用于频率排序：

// 桶排序优化：O(n) vs 堆排序 O(n log n)
// 适用于 256 个符号的 alphabet（字节）
void sortByFreq(HuffNode* nodes[256], int freq[256]) {
    // 频率范围 [1, 256]，使用计数排序
    std::vector<HuffNode*> buckets[MAX_FREQ + 1];  // 按频率分桶
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) buckets[freq[i]].push_back(new HuffNode(i, freq[i]));
    }
    // 按频率升序取出
    int idx = 0;
    for (int f = 1; f <= MAX_FREQ; f++) {
        for (HuffNode* node : buckets[f]) nodes[idx++] = node;
    }
}

9.2 SIMD 加速位操作

使用 ARM NEON 指令加速 BitWriter/BitReader 的位操作：

// 使用 NEON 一次处理 128 bits（16 bytes）
// 比逐 byte 处理快 5-10x
#include <arm_neon.h>

void writeBitsSIMD(uint8_t* dest, const uint32_t* codes, const uint8_t* lengths, int n) {
    // NEON 向量化位写入
    // uint8x16_t 一次处理 16 个字节
}

9.3 内存池优化

频繁的 new/delete HuffNode 会加重 GC 压力。在 JNI 层使用对象池：

class HuffNodePool {
    std::vector<HuffNode> pool;  // 预分配所有节点
    int nextFree = 0;
public:
    HuffNodePool(int maxNodes) : pool(maxNodes) {}
    HuffNode* alloc(char ch, int freq) {
        if (nextFree >= pool.size()) return nullptr;
        pool[nextFree] = HuffNode(ch, freq);
        return &pool[nextFree++];
    }
};

十、实践：Huffman 压缩 vs zlib vs zstd 的 Android 场景对比

算法	压缩率	压缩速度	解压速度	Android 支持
纯 Huffman	低（熵+1 bit）	快	极快	需自行实现
zlib (DEFLATE)	中	中	中	系统自带（java.util.zip）
zstd	高	快	极快	需引入 .so（~300KB）
Brotli	最高	慢	中	Android 5.0+ (Web)

对于日志压缩、APK 内资源压缩：

• 日志实时压缩：zstd（压缩速度和解压速度都很快）
• APK 内资源：DEFLATE/zlib（兼容性最好，无需额外依赖）
• 自定义二进制协议：Canonical Huffman（16 bytes 码长表，开销最小）
• 网络传输：Brotli（最高的文本压缩率）

---

参考

• Huffman, D.A. (1952). “A Method for the Construction of Minimum-Redundancy Codes”
• RFC 1951: DEFLATE Compressed Data Format Specification
• JPEG Standard (ITU-T T.81): Annex C — Huffman tables
• PNG Specification (ISO/IEC 15948): Section 5.4 — Filtering, Section 5.5 — Compression (DEFLATE)
• Duda, J. (2013). “Asymmetric Numeral Systems: Entropy Coding Combining Speed of Huffman Coding with Compression Rate of Arithmetic Coding”
• Introduction to Algorithms (CLRS), 3rd ed. Chapter 16.3 — Huffman Codes