如何用Java将霍夫曼编码写入二进制文件并优化压缩效率？

关于压缩体积的疑问 #

霍夫曼编码能缩小体积的核心是变长编码机制：

• 给出现频率高的字符分配更短的二进制编码（比如2-3位），低频字符分配较长编码（比如10位），整体平均每个字符的编码长度会小于8位（1字节）。
• 写入文件时，不是把每个编码单独存成一个字节，而是将多个编码的二进制位打包到同一个字节中（比如4个2位编码刚好凑成1字节），最终总字节数会远少于原文件（原文件每个字符占1字节），从而实现压缩。

高效Java实现方案 #

你之前的问题出在两个关键低效点：一是将编码先转为超长01字符串（大文件会占用巨量内存，直接导致崩溃）；二是用BitSet逐位处理，IO操作频繁且效率极低。以下是更高效的实现思路和代码：

核心实现步骤 #

1. 统计字符频率：遍历原文件，统计每个字符的出现次数，这是构建霍夫曼树的基础。
2. 构建霍夫曼树：用最小优先队列（堆）实现，每次合并频率最低的两个节点，直到只剩一个根节点。
3. 生成编码表：遍历霍夫曼树，为每个字符生成对应的二进制编码。
4. 打包编码写入文件：读取原文件字符，将对应编码的位填充到字节缓冲区，凑满8位就写入输出流；最后处理剩余不足8位的位，记录补位数量（供解压使用）。
5. 保存霍夫曼树：将霍夫曼树结构写入压缩文件头部，确保解压时能重建编码表。

关键代码示例 #

1. 霍夫曼树节点定义（需实现Serializable）

class HuffmanNode implements Comparable<HuffmanNode>, Serializable {
    char data;
    int frequency;
    HuffmanNode left, right;

    public HuffmanNode(char data, int frequency) {
        this.data = data;
        this.frequency = frequency;
        left = right = null;
    }

    @Override
    public int compareTo(HuffmanNode node) {
        return this.frequency - node.frequency;
    }
}

2. 统计字符频率

private static Map<Character, Integer> countCharFrequency(File inputFile) throws IOException {
    Map<Character, Integer> freqMap = new HashMap<>();
    try (FileInputStream fis = new FileInputStream(inputFile)) {
        int byteVal;
        while ((byteVal = fis.read()) != -1) {
            char c = (char) byteVal;
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }
    }
    return freqMap;
}

3. 构建霍夫曼树与编码表

private static Map<Character, String> buildHuffmanCodeMap(Map<Character, Integer> freqMap) {
    PriorityQueue<HuffmanNode> minHeap = new PriorityQueue<>();
    freqMap.forEach((c, freq) -> minHeap.add(new HuffmanNode(c, freq)));

    // 合并节点生成霍夫曼树
    while (minHeap.size() > 1) {
        HuffmanNode left = minHeap.poll();
        HuffmanNode right = minHeap.poll();
        HuffmanNode mergedNode = new HuffmanNode('\0', left.frequency + right.frequency);
        mergedNode.left = left;
        mergedNode.right = right;
        minHeap.add(mergedNode);
    }

    // 遍历树生成编码表
    Map<Character, String> codeMap = new HashMap<>();
    generateCodeFromTree(minHeap.peek(), "", codeMap);
    return codeMap;
}

private static void generateCodeFromTree(HuffmanNode root, String currentCode, Map<Character, String> codeMap) {
    if (root == null) return;
    // 叶子节点对应字符
    if (root.left == null && root.right == null) {
        codeMap.put(root.data, currentCode.isEmpty() ? "0" : currentCode);
        return;
    }
    generateCodeFromTree(root.left, currentCode + "0", codeMap);
    generateCodeFromTree(root.right, currentCode + "1", codeMap);
}

4. 打包编码并写入压缩文件

private static void writeCompressedData(File inputFile, File outputFile, Map<Character, String> codeMap, HuffmanNode root) throws IOException {
    try (FileOutputStream fos = new FileOutputStream(outputFile);
         ObjectOutputStream oos = new ObjectOutputStream(fos);
         FileInputStream fis = new FileInputStream(inputFile)) {

        // 写入霍夫曼树（供解压重建）
        oos.writeObject(root);

        int currentByte = 0;
        int bitPosition = 0;
        int byteVal;

        while ((byteVal = fis.read()) != -1) {
            char c = (char) byteVal;
            String code = codeMap.get(c);
            for (char bit : code.toCharArray()) {
                // 将当前位左移后填充新bit
                currentByte = (currentByte << 1) | (bit == '1' ? 1 : 0);
                bitPosition++;
                // 凑满8位则写入字节
                if (bitPosition == 8) {
                    fos.write(currentByte);
                    currentByte = 0;
                    bitPosition = 0;
                }
            }
        }

        // 处理剩余未凑满8位的bit，补0后写入
        if (bitPosition > 0) {
            currentByte <<= (8 - bitPosition);
            fos.write(currentByte);
        }
        // 记录补位数量，解压时需去除这些补位
        oos.writeInt(8 - bitPosition);
    }
}

优化说明 #

• 避免超大字符串：直接处理每个编码的二进制位，不存储完整的01编码字符串，彻底解决大文件内存溢出问题。
• 减少IO操作：凑满8位才写入一次字节，大幅降低IO调用次数，提升写入速度。
• 高效流处理：使用字节流直接读写，避免字符流的额外转换开销，适合大文件处理。

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