Java实现Huffman编码时压缩解压PNG文件的异常问题

核心问题分析 #

• 叶子节点判断逻辑错误：原代码通过node.character != 0判定叶子节点，但二进制文件（如PNG）中存在值为0的有效字节，导致这类字节的编码无法被正确生成，解压时丢失关键数据。
• 文本格式存储编码数据：使用BufferedWriter/BufferedReader以文本形式读写编码位串，会因为文本编码规则丢失二进制信息；且readLine()会截断换行符相关的编码位，导致解压时位串不完整。
• 缺少补位处理：Huffman编码的总位数不一定是8的整数倍，直接存储位串会导致最后一个字节不完整，解压时解析错误。

修复后的完整代码 #

import java.io.*;
import java.util.*;

public class HuffmanCoding {

    public static void main(String[] args) throws IOException {
        String inputFilePath = "C:\\Users\\MAJ\\eclipse-workspace\\ProjectTwo\\src\\inputFile.png";
        String encodedOutputFilePath = "C:\\Users\\MAJ\\eclipse-workspace\\ProjectTwo\\src\\encodedOutputFile.huff";
        byte[] data = fileToByteArray(inputFilePath);
        Map<Byte, Integer> frequencyTable = getByteFrequencies(data);
        Node root = createHuffmanTree(frequencyTable);
        Map<Byte, String> encodings = createEncodings(root);
        
        // 编码时记录补位数量，写入压缩文件
        int paddingCount = encodeFile(data, encodings, encodedOutputFilePath);
        // 解压时传入补位数量
        decodeFile(encodedOutputFilePath, "C:\\Users\\MAJ\\eclipse-workspace\\ProjectTwo\\src\\decompressedOutputFile.png", root, paddingCount);
    }

    public static byte[] fileToByteArray(String filePath) throws IOException {
        try (BufferedInputStream inputStream = new BufferedInputStream(new FileInputStream(filePath))) {
            return inputStream.readAllBytes();
        }
    }

    public static Map<Byte, Integer> getByteFrequencies(byte[] data) {
        Map<Byte, Integer> frequencyTable = new HashMap<>();
        for (byte b : data) {
            frequencyTable.put(b, frequencyTable.getOrDefault(b, 0) + 1);
        }
        return frequencyTable;
    }

    public static Node createHuffmanTree(Map<Byte, Integer> frequencyTable) {
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.frequency));
        for (Map.Entry<Byte, Integer> entry : frequencyTable.entrySet()) {
            queue.add(new Node(entry.getKey(), entry.getValue()));
        }
        while (queue.size() > 1) {
            Node left = queue.poll();
            Node right = queue.poll();
            assert right != null;
            Node parent = new Node(left.frequency + right.frequency, left, right);
            queue.add(parent);
        }
        return queue.poll();
    }

    static class Node {
        int frequency;
        byte character;
        Node left;
        Node right;

        Node(int frequency, Node left, Node right) {
            this.frequency = frequency;
            this.left = left;
            this.right = right;
        }

        Node(byte character, int frequency) {
            this.character = character;
            this.frequency = frequency;
        }
    }

    public static Map<Byte, String> createEncodings(Node root) {
        Map<Byte, String> encodings = new HashMap<>();
        createEncodings(root, "", encodings);
        return encodings;
    }

    private static void createEncodings(Node node, String encoding, Map<Byte, String> encodings) {
        if (node == null) {
            return;
        }
        // 用左右子节点是否为空判断叶子节点，而非character值
        if (node.left == null && node.right == null) {
            encodings.put(node.character, encoding);
        } else {
            createEncodings(node.left, encoding + "0", encodings);
            createEncodings(node.right, encoding + "1", encodings);
        }
    }

    public static int encodeFile(byte[] data, Map<Byte, String> encodings, String outputFilePath) throws IOException {
        StringBuilder sb = new StringBuilder();
        for (byte b : data) {
            sb.append(encodings.get(b));
        }

        // 计算需要补的位数，使总长度为8的倍数
        int paddingCount = 8 - (sb.length() % 8);
        if (paddingCount != 8) {
            for (int i = 0; i < paddingCount; i++) {
                sb.append('0');
            }
        } else {
            paddingCount = 0;
        }

        // 将位串转换为字节数组
        byte[] encodedBytes = new byte[sb.length() / 8];
        for (int i = 0; i < encodedBytes.length; i++) {
            String byteStr = sb.substring(i * 8, (i + 1) * 8);
            encodedBytes[i] = (byte) Integer.parseInt(byteStr, 2);
        }

        // 写入压缩文件：先写补位数量，再写编码后的字节数组
        try (DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(outputFilePath)))) {
            dos.writeInt(paddingCount);
            dos.write(encodedBytes);
        }
        return paddingCount;
    }

    public static void decodeFile(String inputFilePath, String outputFilePath, Node root, int paddingCount) throws IOException {
        // 读取补位数量和编码字节数组
        byte[] encodedBytes;
        try (DataInputStream dis = new DataInputStream(new BufferedInputStream(new FileInputStream(inputFilePath)))) {
            paddingCount = dis.readInt();
            encodedBytes = dis.readAllBytes();
        }

        // 将字节数组转换为位串，确保每个字节是8位（补前导0）
        StringBuilder sb = new StringBuilder();
        for (byte b : encodedBytes) {
            String byteStr = String.format("%8s", Integer.toBinaryString(b & 0xFF)).replace(' ', '0');
            sb.append(byteStr);
        }

        // 去掉补的位
        if (paddingCount > 0) {
            sb.setLength(sb.length() - paddingCount);
        }

        // 解码过程
        try (BufferedOutputStream outputStream = new BufferedOutputStream(new FileOutputStream(outputFilePath))) {
            Node current = root;
            for (int i = 0; i < sb.length(); i++) {
                current = sb.charAt(i) == '0' ? current.left : current.right;
                assert current != null;
                if (current.left == null && current.right == null) {
                    outputStream.write(current.character);
                    current = root;
                }
            }
        }
    }
}

关键修复点说明 #

1. 叶子节点判断逻辑修正：生成编码时，通过node.left == null && node.right == null判断叶子节点，避免遗漏值为0的有效字节。
2. 二进制格式存储编码数据：使用DataOutputStream/DataInputStream读写二进制数据，确保编码位串完整保留；替换原文本文件存储为专用压缩格式（如.huff）。
3. 补位处理：编码时计算补位数量，将位串补全为8的整数倍后转换为字节数组；解压时先读取补位数量，再去掉多余的补位，保证原始数据完整。

内容的提问来源于stack exchange，提问作者ojcoding