哈夫曼解析

一、Huffman 编码的理论基础

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

1.1 前缀码与 Kraft 不等式

设字符集为 ${c_1, c_2, \ldots, c_n}$，对应码长为 $l_1, l_2, \ldots, l_n$。存在前缀码的充要条件是 Kraft 不等式成立：
$$\sum_{i=1}^{n} 2^{-l_i} \leq 1$$

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

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

1.2 Huffman 的最优性

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

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

引理 1：在最优编码树中，频率最低的两个字符一定位于最深的位置（否则交换可以降低期望码长）。
引理 2：频率最低的两个字符可以共享同一个父节点而不影响最优性（因为它们在最优树中已经是最深的，合并它们产生的新”虚拟字符”频率为两者之和）。
引理 3：将含 $n$ 个字符的最优编码问题转化为含 $n-1$ 个字符的问题（合并两个最低频率字符），递归地应用 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
ASSIGN_CODES(root, code):
    if root.is_leaf:
        code_table[root.char] = code
    else:
        ASSIGN_CODES(root.left,  code + '0')
        ASSIGN_CODES(root.right, code + '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 的性质

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

3.2 规范 Huffman 的重建算法

// 输入: bit_lengths[0..255] = 每个 symbol 的码长
// 输出: codes[0..255] = 每个 symbol 的 Huffman 码字
void generateCanonicalCodes(
    const uint8_t bit_lengths[256],
    uint32_t codes[256]
) {
    // 1. 统计每种码长的符号数
    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. 按符号顺序分配码字
    for (int i = 0; i < 256; i++) {
        int len = bit_lengths[i];
        if (len > 0) {
            codes[i] = next_code[len]++;
            // 例如码长 3，码字 011 → 反转后存入 → 110 作为输出
        }
    }
}

关键点：规范 Huffman 码字的 bit 序在存储时需要反转——编码时将最低有效位先写入，解码时按此序还原。这与 DEFLATE 和 JPEG 规范一致。

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

4.1 JPEG 中的 Huffman 编码

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

DC 系数的差分编码

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

差分值的编码分为两步：

查表确定 $\Delta$ 值的 magnitude category（如 category=3 表示 -7～-4 或 4～7）
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 码字，表示块中剩余所有系数全为零。

4.2 DEFLATE 中的 Huffman 编码

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

LZ77 产生两种输出：(a) literal 字节 (b) (length, distance) 匹配对
literal 值和 length 值合并为一个 alphabet，用一棵 Huffman 树编码
distance 值用另一棵 Huffman 树编码

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

DEFLATE 对 Huffman 码长表本身再进行一层 run-length 编码（使用重复码），进一步压缩描述 Huffman 码长的开销。这也是规范 Huffman 编码的优势所在——只需传输码长而非完整树结构。

4.3 PNG IDAT 中的 Huffman

PNG 的 IDAT chunk 数据使用 DEFLATE 格式压缩（RFC 1951）。在 filter byte 之后的所有像素数据都经过 DEFLATE 压缩。因此 PNG 的 Huffman 编码实际上就是 DEFLATE 的 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 查找表

void buildLookupTable(const HuffNode* root) {
    buildTable(root, 0, 0, 8);
}

void buildTable(HuffNode* node, uint32_t code, int depth, int maxBits) {
    if (depth == maxBits || node->isLeaf()) {
        // 将该 code 的所有前缀填充到表中
        uint32_t mask = (1 << (maxBits - depth)) - 1;
        for (uint32_t suffix = 0; suffix <= mask; suffix++) {
            uint32_t idx = (code << (maxBits - depth)) | suffix;
            table[idx] = {node->ch, (uint8_t)depth};
        }
    } else {
        buildTable(node->left,  code << 1,     depth + 1, maxBits);
        buildTable(node->right, (code << 1) | 1, depth + 1, maxBits);
    }
}

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

六、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 编码对于单符号编码（逐符号编码），期望码长 $H(X) \leq \bar{L} < H(X) + 1$，其中 $H(X)$ 是信息熵。这个 +1 bit 的上界在符号独立的情况下是无法突破的。

但实际数据中的符号不是独立的——字符之间存在上下文相关性。这解释了为何 Huffman 编码单独使用压缩率不及上下文自适应编码。

7.2 算术编码 vs Huffman

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

现代压缩格式（H.264/H.265 的 CABAC、JPEG 2000、JPEG XL、Brotli、Zstandard）均采用算术编码或其自适应变体。Huffman 编码的持续存在主要是因为：

专利历史：算术编码长期受 IBM 专利限制，促使 DEFLATE 选用 Huffman
解码速度：Huffman 的查表法解码非常快，适合资源受限设备
格式兼容性：JPEG、PNG、DEFLATE 的海量存量文件使得 Huffman 仍然广泛使用

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 被认为是当前最优秀的通用熵编码方法。

面试常考问题

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 · ⌈-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* 直接操作字节数组，避免 Java 层的 JNI 调用开销。实测在 1MB 文本压缩中，native 版本通常快 3-5 倍。另外 native 端的 BitWriter/BitReader 可以利用 ARM NEON 的 vector bit-shift 指令进一步优化。

参考

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