每日算法 — 使用java实现霍夫曼编码：贪心构建最优前缀码与数据压缩

在日常开发中，文本文件、图片、音频的存储与传输都离不开压缩技术。如何将 "AAAAABCD" 这类高频字符重复出现的数据高效编码？1952年，David Huffman 提出的 霍夫曼编码（Huffman Coding） 利用 贪心策略 构建最优前缀码，使带权编码长度最小化，至今仍是 ZIP、JPEG、MP3 等格式的底层基础。本文用 Java 完整实现霍夫曼树构建、编码与解码全流程，深入讲解贪心正确性、前缀码特性与工程优化技巧。

从定长编码到变长编码的问题

假设字符集为 {A, B, C, D}，各字符出现频率如下：

定长编码总长度：2 × (45+13+12+10) = 160 位。

变长编码如果随意分配，可能出现 二义性：收到 001 时，无法判断是 A(0) + B(1) 还是 C(00) + ?。因此，编码必须满足 前缀码（Prefix Code） 性质——任意字符的编码都不是其他字符编码的前缀。

前缀码与二叉树的等价关系

前缀码可以用一棵 满二叉树 直观表示：
– 每个叶子节点代表一个字符
– 从根到叶子的路径中，左分支标记 0，右分支标记 1
– 叶子节点的深度即为该字符的编码长度

关键结论：当高频字符靠近根节点（编码短）、低频字符远离根节点（编码长）时，整棵树的带权路径长度最小。这正是霍夫曼编码的核心优化目标。

霍夫曼编码的贪心策略

霍夫曼算法的贪心选择极其简洁：

每次选择频率最低的两个节点，合并为一个新节点，新节点频率为两者之和，重复直至只剩一棵树。

为什么贪心能得到全局最优？

通过交换论证可证明：设 x 和 y 是频率最低的两个字符，则存在某棵最优前缀码树，使得 x 和 y 是深度最大且互为兄弟的叶子节点。将 x、y 合并后，问题规模缩小为 n-1，满足最优子结构。因此贪心选择是安全的。

完整 Java 实现

以下实现包含霍夫曼树节点定义、贪心构建、编码表生成、文本编码与解码的完整流程，可直接运行。

import java.util.*;

/**
 * 霍夫曼编码完整实现
 * 核心：贪心策略 + 优先队列（最小堆）构建最优前缀码
 * 时间复杂度：O(n log n)，n 为不同字符数量
 */
public class HuffmanCoding {

    /**
     * 霍夫曼树节点
     * 叶子节点存储字符与频率，内部节点只存储合并后的频率
     */
    static class HuffmanNode implements Comparable<HuffmanNode> {
        char ch;           // 字符（内部节点可用占位符）
        int freq;          // 出现频率
        HuffmanNode left;  // 左子树（编码0）
        HuffmanNode right; // 右子树（编码1）
        boolean isLeaf;    // 是否为叶子节点

        HuffmanNode(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
            this.isLeaf = true;
        }

        HuffmanNode(int freq, HuffmanNode left, HuffmanNode right) {
            this.freq = freq;
            this.left = left;
            this.right = right;
            this.isLeaf = false;
            this.ch = '\0';
        }

        @Override
        public int compareTo(HuffmanNode other) {
            return Integer.compare(this.freq, other.freq);
        }
    }

    /**
     * 步骤1：统计文本中各字符频率
     * @param text 输入文本
     * @return 字符到频率的映射
     */
    public static Map<Character, Integer> buildFrequencyMap(String text) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : text.toCharArray()) {
            freqMap.merge(c, 1, Integer::sum);
        }
        return freqMap;
    }

    /**
     * 步骤2：使用贪心策略构建霍夫曼树
     * 每次从优先队列中取出频率最小的两个节点合并
     * @param freqMap 字符频率映射
     * @return 霍夫曼树的根节点
     */
    public static HuffmanNode buildHuffmanTree(Map<Character, Integer> freqMap) {
        // 最小堆：按频率升序排列
        PriorityQueue<HuffmanNode> minHeap = new PriorityQueue<>();

        // 将所有字符作为叶子节点入堆
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            minHeap.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        // 贪心合并：每次取两个最小频率节点
        while (minHeap.size() > 1) {
            HuffmanNode left = minHeap.poll();   // 频率最小
            HuffmanNode right = minHeap.poll();  // 频率次小

            // 创建内部节点，频率为两者之和
            HuffmanNode merged = new HuffmanNode(
                left.freq + right.freq, left, right
            );
            minHeap.offer(merged);
        }

        return minHeap.poll(); // 返回树根
    }

    /**
     * 步骤3：从霍夫曼树生成编码表
     * DFS遍历，左分支追加0，右分支追加1
     * @param root 霍夫曼树根节点
     * @return 字符到编码的映射
     */
    public static Map<Character, String> buildCodeTable(HuffmanNode root) {
        Map<Character, String> codeTable = new HashMap<>();
        if (root == null) return codeTable;

        // 特殊情况：只有一个字符
        if (root.isLeaf) {
            codeTable.put(root.ch, "0");
            return codeTable;
        }

        dfsBuildCode(root, new StringBuilder(), codeTable);
        return codeTable;
    }

    private static void dfsBuildCode(HuffmanNode node, StringBuilder prefix,
                                      Map<Character, String> codeTable) {
        if (node == null) return;

        if (node.isLeaf) {
            // 叶子节点：保存当前路径作为该字符的编码
            codeTable.put(node.ch, prefix.toString());
            return;
        }

        // 向左：追加0
        prefix.append('0');
        dfsBuildCode(node.left, prefix, codeTable);
        prefix.deleteCharAt(prefix.length() - 1);

        // 向右：追加1
        prefix.append('1');
        dfsBuildCode(node.right, prefix, codeTable);
        prefix.deleteCharAt(prefix.length() - 1);
    }

    /**
     * 步骤4：将文本编码为二进制字符串
     * @param text 原始文本
     * @param codeTable 编码表
     * @return 编码后的二进制字符串
     */
    public static String encode(String text, Map<Character, String> codeTable) {
        StringBuilder encoded = new StringBuilder();
        for (char c : text.toCharArray()) {
            encoded.append(codeTable.get(c));
        }
        return encoded.toString();
    }

    /**
     * 步骤5：从二进制字符串解码为原文
     * 从根节点出发，0向左、1向右，到达叶子即输出字符并回到根
     * @param encoded 编码后的二进制字符串
     * @param root 霍夫曼树根节点
     * @return 解码后的原文
     */
    public static String decode(String encoded, HuffmanNode root) {
        StringBuilder decoded = new StringBuilder();
        HuffmanNode current = root;

        for (char bit : encoded.toCharArray()) {
            if (bit == '0') {
                current = current.left;
            } else {
                current = current.right;
            }

            if (current.isLeaf) {
                decoded.append(current.ch);
                current = root; // 回到根，开始解码下一个字符
            }
        }

        return decoded.toString();
    }

    /**
     * 可视化打印霍夫曼树结构与编码表
     */
    public static void printTree(HuffmanNode node, String prefix) {
        if (node == null) return;
        if (node.isLeaf) {
            System.out.printf("  叶子: '%c' (频率=%d, 编码=%s)%n",
                node.ch, node.freq, prefix.isEmpty() ? "0" : prefix);
        } else {
            System.out.printf("  内部节点 (合并频率=%d)%n", node.freq);
            printTree(node.left, prefix + "0");
            printTree(node.right, prefix + "1");
        }
    }

    // 主程序：完整演示
    public static void main(String[] args) {
        String text = "this is an example of a huffman tree";
        System.out.println("=== 原始文本 ===");
        System.out.println(text);
        System.out.println("原始长度: " + text.length() * 8 + " 位（ASCII定长）\n");

        // 1. 统计频率
        Map<Character, Integer> freqMap = buildFrequencyMap(text);
        System.out.println("=== 字符频率 ===");
        freqMap.entrySet().stream()
            .sorted(Map.Entry.<Character, Integer>comparingByValue().reversed())
            .forEach(e -> System.out.printf("  '%c': %d%n", e.getKey(), e.getValue()));

        // 2. 构建霍夫曼树
        HuffmanNode root = buildHuffmanTree(freqMap);
        System.out.println("\n=== 霍夫曼树结构 ===");
        printTree(root, "");

        // 3. 生成编码表
        Map<Character, String> codeTable = buildCodeTable(root);
        System.out.println("\n=== 编码表 ===");
        codeTable.entrySet().stream()
            .sorted(Comparator.comparingInt(e -> e.getValue().length()))
            .forEach(e -> System.out.printf("  '%c' -> %s (长度=%d)%n",
                e.getKey(), e.getValue(), e.getValue().length()));

        // 4. 编码
        String encoded = encode(text, codeTable);
        System.out.println("\n=== 编码结果 ===");
        System.out.println("编码长度: " + encoded.length() + " 位");
        System.out.printf("压缩率: %.1f%%%n",
            (1.0 - encoded.length() / (double)(text.length() * 8)) * 100);

        // 5. 解码验证
        String decoded = decode(encoded, root);
        System.out.println("\n=== 解码验证 ===");
        System.out.println("解码结果: " + decoded);
        System.out.println("一致性: " + text.equals(decoded));

        // 6. 边界测试：单字符重复
        System.out.println("\n=== 边界测试：单字符重复 'AAAAA' ===");
        String repeat = "AAAAA";
        Map<Character, Integer> freq2 = buildFrequencyMap(repeat);
        HuffmanNode root2 = buildHuffmanTree(freq2);
        Map<Character, String> table2 = buildCodeTable(root2);
        String enc2 = encode(repeat, table2);
        String dec2 = decode(enc2, root2);
        System.out.println("编码: " + enc2);
        System.out.println("解码: " + dec2);
        System.out.println("一致: " + repeat.equals(dec2));
    }
}

关键代码解读

优先队列的贪心选择

while (minHeap.size() > 1) {
    HuffmanNode left = minHeap.poll();
    HuffmanNode right = minHeap.poll();
    minHeap.offer(new HuffmanNode(left.freq + right.freq, left, right));
}

每次 poll() 取出频率最小的两个节点，保证低频字符被推向树的深处，高频字符靠近根节点。PriorityQueue 的底层是最小堆，使每次插入和取出均为 O(log n)。

前缀码的解码安全性

if (current.isLeaf) {
    decoded.append(current.ch);
    current = root;
}

由于霍夫曼树的叶子节点之间不存在祖先-后代关系，任何编码串都能被 唯一确定地 解析，不会出现 0 既是 A 的编码、又是 AB 前缀的歧义。

复杂度分析

当字符集较小（如 ASCII 的 128 个字符）时，k 为常数，整体接近线性性能。

扩展：从理论到工程实践

1. 字节对齐：上述实现输出二进制字符串，实际存储时需按 8 位对齐为字节流，剩余位用填充标记处理。
2. 序列化编码表：压缩文件必须附带编码表（或频率表），否则接收方无法解码。通常将编码表以头部元数据形式写入。
3. 自适应霍夫曼编码：动态统计流数据频率并实时调整树结构，适用于网络传输等无法预先扫描全文的场景。
4. 与算术编码对比：霍夫曼编码以整数位为单位分配码长，对概率极度倾斜的分布（如 A=99%, B=1%）不如算术编码紧凑，但实现简单、解码高效。

总结

霍夫曼编码是 贪心算法 的经典范例：每一步只关注局部最优（合并频率最低的两个节点），却能证明达到全局最优（最小带权路径长度）。掌握它不仅有助于理解数据压缩原理，更能训练对 最优子结构 与 贪心选择性质 的敏感度——这种思维在设计缓存淘汰策略、任务调度算法时同样适用。