哈夫曼编码入门指南（用Java轻松实现数据压缩）

二、哈夫曼树的构建步骤

构建哈夫曼树的核心思想是：每次选择频率最小的两个节点合并，直到只剩一棵树。具体步骤如下：

1. 统计每个字符的出现频率。
2. 将每个字符视为一个叶子节点，放入优先队列（最小堆）。
3. 从队列中取出两个频率最小的节点，创建一个新父节点，其频率为两者之和，并将这两个节点作为左右子节点。
4. 将新节点放回队列。
5. 重复步骤 3-4，直到队列中只剩一个节点——这就是哈夫曼树的根节点。

三、Java 实现哈夫曼编码

下面我们用 Java 编写一个完整的哈夫曼编码程序。

1. 定义哈夫曼树节点类

class Node implements Comparable<Node> {    char ch;    int freq;    Node left, right;    Node(char ch, int freq) {        this.ch = ch;        this.freq = freq;    }    Node(Node left, Node right) {        this.left = left;        this.right = right;        this.freq = left.freq + right.freq;    }    @Override    public int compareTo(Node other) {        return Integer.compare(this.freq, other.freq);    }}  

2. 构建哈夫曼树并生成编码表

import java.util.*;public class HuffmanCoding {    public static Map<Character, String> buildHuffmanCodes(String text) {        // 1. 统计字符频率        Map<Character, Integer> freqMap = new HashMap<>();        for (char c : text.toCharArray()) {            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);        }        // 2. 创建优先队列（最小堆）        PriorityQueue<Node> pq = new PriorityQueue<>();        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {            pq.offer(new Node(entry.getKey(), entry.getValue()));        }        // 3. 构建哈夫曼树        while (pq.size() > 1) {            Node left = pq.poll();            Node right = pq.poll();            Node parent = new Node(left, right);            pq.offer(parent);        }        // 4. 生成编码表        Map<Character, String> huffmanCodes = new HashMap<>();        if (!pq.isEmpty()) {            generateCodes(pq.peek(), "", huffmanCodes);        }        return huffmanCodes;    }    private static void generateCodes(Node node, String code, Map<Character, String> codes) {        if (node == null) return;        if (node.left == null && node.right == null) {            codes.put(node.ch, code.isEmpty() ? "0" : code); // 处理只有一个字符的情况        } else {            generateCodes(node.left, code + "0", codes);            generateCodes(node.right, code + "1", codes);        }    }    public static void main(String[] args) {        String text = "aabbc";        Map<Character, String> codes = buildHuffmanCodes(text);        System.out.println("哈夫曼编码表:");        for (Map.Entry<Character, String> entry : codes.entrySet()) {            System.out.println(entry.getKey() + ": " + entry.getValue());        }        // 输出编码结果        StringBuilder encoded = new StringBuilder();        for (char c : text.toCharArray()) {            encoded.append(codes.get(c));        }        System.out.println("\n原始文本: " + text);        System.out.println("编码结果: " + encoded.toString());    }}  

四、运行结果示例

以输入字符串 aabbc 为例，程序可能输出：

哈夫曼编码表:a: 00b: 01c: 1原始文本: aabbc编码结果: 000001011  

可以看到，原本需要 40 位（ASCII）的数据，现在仅用 9 位就完成了表示，压缩率非常高！

五、总结

通过本哈夫曼编码教程，你已经掌握了：

• 哈夫曼编码的基本原理
• 如何用 Java 构建哈夫曼树
• 如何生成变长前缀编码
• 实际压缩效果的验证

哈夫曼编码不仅是面试常考题，更是许多压缩工具（如 ZIP、GZIP）的核心技术之一。掌握它，你就迈入了数据压缩算法的大门！

快动手试试吧！修改输入字符串，观察不同频率下的编码变化，加深理解。祝你编程愉快！