Java实现哈夫曼压缩与解压缩的方法

哈夫曼编码是一种有效的无损压缩算法，常用于压缩文本文件等数据。本文将详细介绍如何使用Java实现哈夫曼压缩与解压缩的方法。

哈夫曼压缩

1. 构建哈夫曼树

首先需要构建一个哈夫曼树，该树的每个叶子节点都代表一个字符，并且每个叶子节点的编码都是唯一的。构建哈夫曼树的过程如下：

• 统计给定文本中每个字符出现的频率。
• 将字符频率作为权值构建一棵小根堆（优先队列）。
• 从堆中取出两个权值最小的节点，并将它们合并为一棵树，并将根节点的权值设置为两个子节点的权值之和。
• 将新生成的树作为一个节点重新加入堆中。
• 重复以上步骤，直到堆里只剩下一个节点，即树的根节点。

2. 获取字符编码

在构建哈夫曼树之后，需要根据该树计算出每个叶子节点的编码。对于树中的每个节点，左子节点的编码是当前节点的编码加上字符0，右子节点的编码是当前节点的编码加上字符1。可以使用深度优先遍历的方式，递归地计算出所有叶子节点的编码。

3. 压缩数据

获取字符编码之后，可以根据编码将数据进行压缩。将每个字符替换成它的编码，最终得到一个由0和1组成的二进制字符串。由于Java中没有二进制字符串类型，可以使用StringBuilder类来实现。

以下是具体的Java代码示例：

import java.util.*;

public class HuffmanCompressor {
    private static class Node implements Comparable<Node> {
        public int value;
        public char ch;
        public Node left;
        public Node right;

        public Node(int value, char ch) {
            this.value = value;
            this.ch = ch;
        }

        public Node(int value) {
            this.value = value;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(value, other.value);
        }
    }

    public static String compress(String data) {
        int[] freqTable = new int[256];
        for (int i = 0; i < data.length(); i++) {
            freqTable[data.charAt(i)]++;
        }

        PriorityQueue<Node> pqueue = new PriorityQueue<>();
        for (int i = 0; i < freqTable.length; i++) {
            if (freqTable[i] > 0) {
                pqueue.offer(new Node(freqTable[i], (char) i));
            }
        }

        while(pqueue.size() > 1) {
            Node left = pqueue.poll();
            Node right = pqueue.poll();

            Node parent = new Node(left.value + right.value);
            parent.left = left;
            parent.right = right;

            pqueue.offer(parent);
        }

        Node root = pqueue.poll();

        Map<Character, String> codeTable = new HashMap<>();
        getCodeTable(root, "", codeTable);

        StringBuilder encodedData = new StringBuilder();
        for (int i = 0; i < data.length(); i++) {
            encodedData.append(codeTable.get(data.charAt(i)));
        }

        return encodedData.toString();
    }

    private static void getCodeTable(Node node, String code, Map<Character, String> codeTable) {
        if (node == null) {
            return;
        }

        if (node.isLeaf()) {
            codeTable.put(node.ch, code);
        }

        getCodeTable(node.left, code + "0", codeTable);
        getCodeTable(node.right, code + "1", codeTable);
    }
}

哈夫曼解压缩

1. 构建哈夫曼树

哈夫曼解压缩需要用到与压缩相同的哈夫曼树，因此需要先构建哈夫曼树。步骤与压缩时相同，将编码和字符对应关系调换即可。

2. 解码数据

将二进制编码的数据根据哈夫曼编码进行解码。从树的根节点开始，依次读取每一个二进制位，如果是0，则移动到当前节点的左子节点，如果是1，则移动到当前节点的右子节点，直到遇到叶子节点。当遇到叶子节点时，将该节点的字符存储下来，并从根节点重新开始处理下一个编码。

以下是具体的Java代码示例：

public class HuffmanDecompressor {
    private static class Node {
        public char ch;
        public Node left;
        public Node right;

        public Node(char ch) {
            this.ch = ch;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }
    }

    public static String decompress(String data, Node root) {
        StringBuilder decodedData = new StringBuilder();

        Node curr = root;
        for (int i = 0; i < data.length(); i++) {
            if (data.charAt(i) == '0') {
                curr = curr.left;
            } else if (data.charAt(i) == '1') {
                curr = curr.right;
            }

            if (curr.isLeaf()) {
                decodedData.append(curr.ch);
                curr = root;
            }
        }

        return decodedData.toString();
    }
}

示例

示例1：压缩文件

下面的代码示例演示如何使用上面的HuffmanCompressor类将文件（已存在的test.txt文件）压缩并写入到新文件test.gz中，并解压缩到解压缩文件test_decoded.txt。

import java.io.*;
import java.nio.file.Files;

public class Main {
    public static void main(String[] args) throws IOException {
        String filePath = "test.txt";
        String compressedFilePath = "test.gz";
        String decompressedFilePath = "test_decoded.txt";

        // 读取源文件
        byte[] dataBytes = Files.readAllBytes(new File(filePath).toPath());
        String data = new String(dataBytes);

        // 压缩
        String compressedData = HuffmanCompressor.compress(data);

        // 将压缩后的数据写入到文件
        FileOutputStream fos = new FileOutputStream(compressedFilePath);
        byte[] compressedBytes = compressedData.getBytes("UTF-8");
        fos.write(compressedBytes);
        fos.close();

        // 从压缩文件中读取数据
        String compressedDataFromFile = new String(Files.readAllBytes(new File(compressedFilePath).toPath()), "UTF-8");

        // 解压缩
        String decompressedData = HuffmanDecompressor.decompress(compressedDataFromFile, getHuffmanTree(data));

        // 将解压缩后的数据写入到文件
        FileOutputStream fos2 = new FileOutputStream(decompressedFilePath);
        byte[] decompressedBytes = decompressedData.getBytes("UTF-8");
        fos2.write(decompressedBytes);
        fos2.close();
    }

    private static HuffmanDecompressor.Node getHuffmanTree(String data) {
        int[] freqTable = new int[256];
        for (int i = 0; i < data.length(); i++) {
            freqTable[data.charAt(i)]++;
        }

        PriorityQueue<HuffmanCompressor.Node> pqueue = new PriorityQueue<>();
        for (int i = 0; i < freqTable.length; i++) {
            if (freqTable[i] > 0) {
                pqueue.offer(new HuffmanCompressor.Node(freqTable[i], (char) i));
            }
        }

        while(pqueue.size() > 1) {
            HuffmanCompressor.Node left = pqueue.poll();
            HuffmanCompressor.Node right = pqueue.poll();

            HuffmanCompressor.Node parent = new HuffmanCompressor.Node(left.value + right.value);
            parent.left = left;
            parent.right = right;

            pqueue.offer(parent);
        }

        return pqueue.poll();
    }
}

示例2：压缩字符串

以下代码演示如何使用上面的HuffmanCompressor类将字符串压缩并解压缩。

public class Main {
    public static void main(String[] args) {
        String data = "Hello, World!";
        String compressedData = HuffmanCompressor.compress(data);
        String decompressedData = HuffmanDecompressor.decompress(compressedData, getHuffmanTree(data));

        System.out.println("原始数据：" + data);
        System.out.println("压缩后的数据：" + compressedData);
        System.out.println("解压缩后的数据：" + decompressedData);
    }

    private static HuffmanDecompressor.Node getHuffmanTree(String data) {
        int[] freqTable = new int[256];
        for (int i = 0; i < data.length(); i++) {
            freqTable[data.charAt(i)]++;
        }

        PriorityQueue<HuffmanCompressor.Node> pqueue = new PriorityQueue<>();
        for (int i = 0; i < freqTable.length; i++) {
            if (freqTable[i] > 0) {
                pqueue.offer(new HuffmanCompressor.Node(freqTable[i], (char) i));
            }
        }

        while(pqueue.size() > 1) {
            HuffmanCompressor.Node left = pqueue.poll();
            HuffmanCompressor.Node right = pqueue.poll();

            HuffmanCompressor.Node parent = new HuffmanCompressor.Node(left.value + right.value);
            parent.left = left;
            parent.right = right;

            pqueue.offer(parent);
        }

        return pqueue.poll();
    }
}

希望这些示例能够帮助您更好地了解如何使用Java实现哈夫曼压缩和解压缩。