使用Java实现哈夫曼编码

前言

哈夫曼编码是一种经典的无损数据压缩算法，它通过赋予出现频率较高的字符较短的编码，出现频率较低的字符较长的编码，从而实现压缩效果。这篇博客将详细讲解如何使用Java实现哈夫曼编码，包括哈夫曼编码的原理、具体实现步骤以及完整的代码示例。

哈夫曼编码原理

哈夫曼编码的基本原理可以概括为以下几个步骤：

1. 统计字符频率：遍历输入数据，统计每个字符出现的频率。
2. 构建哈夫曼树：根据字符的频率构建一棵哈夫曼树。树的每个节点代表一个字符及其频率，树的叶子节点代表具体的字符。
3. 生成哈夫曼编码：通过遍历哈夫曼树生成每个字符的哈夫曼编码。左子树表示’0’，右子树表示’1’。
4. 编码数据：将原始数据根据哈夫曼编码表转换为二进制数据。
5. 解码数据：根据哈夫曼树将二进制数据还原为原始字符。

实现步骤

1. 定义哈夫曼树的节点类

首先定义一个内部类Node，用于表示哈夫曼树的节点。每个节点包含字符、频率、左子节点和右子节点。实现Comparable<Node>接口用于在优先队列中排序。

private static class Node implements Comparable<Node> {private final char ch;     // 字符private final int freq;    // 频率private final Node left, right;  // 左右子节点Node(char ch, int freq, Node left, Node right) {this.ch = ch;this.freq = freq;this.left = left;this.right = right;}// 判断是否为叶子节点private boolean isLeaf() {assert ((left == null) && (right == null)) || ((left != null) && (right != null));return (left == null) && (right == null);}// 根据频率比较节点，用于优先队列public int compareTo(Node that) {return this.freq - that.freq;}
}

2. 构建哈夫曼树

根据字符频率构建哈夫曼树。我们使用优先队列来实现该步骤。

private static Node buildTrie(int[] freq) {// 初始化优先队列，并将每个字符及其频率作为单节点树插入队列MinPQ<Node> pq = new MinPQ<Node>();for (char c = 0; c < R; c++)if (freq[c] > 0)pq.insert(new Node(c, freq[c], null, null));// 不断合并频率最小的两棵树，直到剩下一棵树while (pq.size() > 1) {Node left = pq.delMin();Node right = pq.delMin();Node parent = new Node('\0', left.freq + right.freq, left, right);pq.insert(parent);}return pq.delMin();
}

3. 生成哈夫曼编码表

通过遍历哈夫曼树生成每个字符的哈夫曼编码。

private static void buildCode(String[] st, Node x, String s) {if (!x.isLeaf()) {// 递归遍历左子树，路径加'0'buildCode(st, x.left, s + '0');// 递归遍历右子树，路径加'1'buildCode(st, x.right, s + '1');} else {// 叶子节点，记录字符的编码st[x.ch] = s;}
}

4. 压缩数据

读取输入数据，生成哈夫曼编码表，输出编码后的二进制数据。

public static void compress() {// 读取输入字符串并转换为字符数组String s = BinaryStdIn.readString();char[] input = s.toCharArray();// 计算每个字符的频率int[] freq = new int[R];for (int i = 0; i < input.length; i++)freq[input[i]]++;// 构建哈夫曼树Node root = buildTrie(freq);// 建立字符编码表String[] st = new String[R];buildCode(st, root, "");// 输出哈夫曼树以便解码使用writeTrie(root);// 输出原始未压缩的字节数BinaryStdOut.write(input.length);// 使用哈夫曼编码压缩输入for (int i = 0; i < input.length; i++) {String code = st[input[i]];for (int j = 0; j < code.length(); j++) {if (code.charAt(j) == '0') {BinaryStdOut.write(false);} else if (code.charAt(j) == '1') {BinaryStdOut.write(true);} else throw new IllegalStateException("Illegal state");}}// 关闭输出流BinaryStdOut.close();
}

5. 解码数据

读取哈夫曼树和编码后的二进制数据，解码还原原始数据。

public static void expand() {// 从输入流中读取哈夫曼树Node root = readTrie();// 读取原始字节数int length = BinaryStdIn.readInt();// 使用哈夫曼树解码输入的二进制数据并输出字符for (int i = 0; i < length; i++) {Node x = root;while (!x.isLeaf()) {boolean bit = BinaryStdIn.readBoolean();if (bit) x = x.right;else x = x.left;}BinaryStdOut.write(x.ch, 8);}BinaryStdOut.close();
}

完整代码

以下是完整的哈夫曼编码实现代码：

public class Huffman {// 定义扩展ASCII字符集的大小private static final int R = 256;// 防止实例化private Huffman() { }// 哈夫曼树的节点类，实现了Comparable接口以便于优先队列排序private static class Node implements Comparable<Node> {private final char ch;     // 字符private final int freq;    // 频率private final Node left, right;  // 左右子节点Node(char ch, int freq, Node left, Node right) {this.ch = ch;this.freq = freq;this.left = left;this.right = right;}// 判断是否为叶子节点private boolean isLeaf() {assert ((left == null) && (right == null)) || ((left != null) && (right != null));return (left == null) && (right == null);}// 根据频率比较节点，用于优先队列public int compareTo(Node that) {return this.freq - that.freq;}}// 压缩方法public static void compress() {// 读取输入字符串并转换为字符数组String s = BinaryStdIn.readString();char[] input = s.toCharArray();// 计算每个字符的频率int[] freq = new int[R];for (int i = 0; i < input.length; i++)freq[input[i]]++;// 构建哈夫曼树Node root = buildTrie(freq);// 建立字符编码表String[] st = new String[R];buildCode(st, root, "");// 输出哈夫曼树以便解码使用writeTrie(root);// 输出原始未压缩的字节数BinaryStdOut.write(input.length);// 使用哈夫曼编码压缩输入for (int i = 0; i < input.length; i++) {String code = st[input[i]];for (int j = 0; j < code.length(); j++) {if (code.charAt(j) == '0') {BinaryStdOut.write(false);} else if (code.charAt(j) == '1') {BinaryStdOut.write(true);} else throw new IllegalStateException("Illegal state");}}// 关闭输出流BinaryStdOut.close();}// 构建哈夫曼树private static Node buildTrie(int[] freq) {// 初始化优先队列，并将每个字符及其频率作为单节点树插入队列MinPQ<Node> pq = new MinPQ<Node>();for (char c = 0; c < R; c++)if (freq[c] > 0)pq.insert(new Node(c, freq[c], null, null));// 不断合并频率最小的两棵树，直到剩下一棵树while (pq.size() > 1) {Node left = pq.delMin();Node right = pq.delMin();Node parent = new Node('\0', left.freq + right.freq, left, right);pq.insert(parent);}return pq.delMin();}// 输出哈夫曼树，用于解码private static void writeTrie(Node x) {if (x.isLeaf()) {BinaryStdOut.write(true);BinaryStdOut.write(x.ch, 8);return;}BinaryStdOut.write(false);writeTrie(x.left);writeTrie(x.right);}// 生成哈夫曼编码表private static void buildCode(String[] st, Node x, String s) {if (!x.isLeaf()) {// 递归遍历左子树，路径加'0'buildCode(st, x.left, s + '0');// 递归遍历右子树，路径加'1'buildCode(st, x.right, s + '1');} else {// 叶子节点，记录字符的编码st[x.ch] = s;}}// 解码方法public static void expand() {// 从输入流中读取哈夫曼树Node root = readTrie();// 读取原始字节数int length = BinaryStdIn.readInt();// 使用哈夫曼树解码输入的二进制数据并输出字符for (int i = 0; i < length; i++) {Node x = root;while (!x.isLeaf()) {boolean bit = BinaryStdIn.readBoolean();if (bit) x = x.right;else x = x.left;}BinaryStdOut.write(x.ch, 8);}BinaryStdOut.close();}// 从输入流中读取哈夫曼树private static Node readTrie() {boolean isLeaf = BinaryStdIn.readBoolean();if (isLeaf) {return new Node(BinaryStdIn.readChar(), -1, null, null);} else {return new Node('\0', -1, readTrie(), readTrie());}}// 主方法，根据参数决定执行压缩或解码public static void main(String[] args) {if (args[0].equals("-")) compress();else if (args[0].equals("+")) expand();else throw new IllegalArgumentException("Illegal command line argument");}
}

总结

哈夫曼编码是一种高效的无损数据压缩算法。本文通过详细的代码示例展示了如何使用Java实现哈夫曼编码的压缩和解压功能。从统计字符频率、构建哈夫曼树、生成哈夫曼编码表到最终的编码和解码，涵盖了哈夫曼编码的全部核心步骤。希望这篇博客能够帮助你更好地理解哈夫曼编码的实现原理和具体的编码实践。