使用Java实现哈夫曼编码

前言

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

哈夫曼编码原理

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

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

实现步骤

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");}
}