Java 實現哈夫曼編碼壓縮：從原理到完整代碼實戰

為什麼要自研壓縮？

標準工具（GZIP 等）針對通用數據優化，對於短文本、字符分布極不均勻、特定業務字符集場景，哈夫曼編碼往往能產出更小體積，且無第三方依賴。

核心原理三步走

1. 統計頻率：掃描文本，得出每字符權重
2. 構建哈夫曼樹：反復合併最小權重兩節點，構建最優前綴碼二叉樹
3. 生成編碼表：左邊 0、右邊 1，從根到葉子路徑即編碼，無編碼是其他編碼前綴

完整工程代碼 (三類)

1. 節點類

public class Node implements Comparable<Node> {
    int weight;
    Node left, right;
    String huffCode;
    boolean isLeaf;
    Character value;

    public Node(Character value, int weight) { // 葉子
        this.value = value; this.weight = weight; this.isLeaf = true;
    }
    public Node(int weight, Node left, Node right) { // 內部節點
        this.weight = weight; this.left = left; this.right = right; this.isLeaf = false;
    }
    public void incWeight(int i) { weight += i; }
    @Override public int compareTo(Node o) { return this.weight - o.weight; }
}

2. 哈夫曼樹構建與編碼/解碼引擎

public class HuffmanTree {
    private Map<Character, Node> leafMap = new HashMap<>();
    private List<Node> nodes = new ArrayList<>();

    // 編碼入口
    public String encode(String text) {
        if (text == null) return null;
        buildWeights(text);
        Node root = buildTree();
        genCodes(root, "");
        StringBuilder sb = new StringBuilder();
        for (char ch : text.toCharArray()) sb.append(leafMap.get(ch).huffCode);
        return sb.toString(); // 如 "010011..."
    }

    // 解碼入口
    public String decode(Map<String, Character> codeTable, String bits) {
        StringBuilder sb = new StringBuilder();
        int start = 0, end = 1;
        while (end <= bits.length()) {
            String key = bits.substring(start, end);
            if (codeTable.containsKey(key)) {
                sb.append(codeTable.get(key));
                start = end;
            }
            end++;
        }
        return sb.toString();
    }

    // 獲取編碼表 (傳輸給解碼端)
    public Map<String, Character> getCodeTable() {
        Map<String, Character> map = new HashMap<>();
        leafMap.forEach((ch, node) -> map.put(node.huffCode, ch));
        return map;
    }

    // --- 內部實現 ---
    private void buildWeights(String text) {
        for (char ch : text.toCharArray()) {
            leafMap.computeIfAbsent(ch, c -> {
                Node n = new Node(c, 1);
                nodes.add(n);
                return n;
            }).incWeight(1);
        }
    }

    private Node buildTree() {
        Collections.sort(nodes);
        while (nodes.size() > 1) {
            Node l = nodes.remove(0);
            Node r = nodes.remove(0);
            insertSorted(nodes, new Node(l.weight + r.weight, l, r));
        }
        return nodes.remove(0);
    }

    private void insertSorted(List<Node> list, Node node) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (node.weight < list.get(mid).weight) hi = mid;
            else lo = mid + 1;
        }
        list.add(lo, node);
    }

    private void genCodes(Node node, String prefix) {
        if (node.isLeaf) { node.huffCode = prefix; return; }
        genCodes(node.left, prefix + "0");
        genCodes(node.right, prefix + "1");
    }
}

3. 二進制位串與 byte[] 互轉工具 (關鍵落地)

public class HuffUtils {
    // "010011" → byte[]
    public static byte[] toBytes(String bits) {
        int len = bits.length();
        byte[] bytes = new byte[(len + 7) / 8];
        for (int i = 0; i < len; i++) {
            if (bits.charAt(i) == '1') bytes[i / 8] |= 1 << (7 - i % 8); // 大端序
        }
        return bytes;
    }

    // byte[] → "010011..." (需知最後一字節有效位數)
    public static String toBits(byte[] bytes, int lastValidBits) {
        StringBuilder sb = new StringBuilder(bytes.length * 8);
        for (int i = 0; i < bytes.length; i++) {
            int b = bytes[i];
            int valid = (i == bytes.length - 1) ? lastValidBits : 8;
            for (int bit = 7; bit >= 8 - valid; bit--) {
                sb.append((b >> bit) & 1);
            }
        }
        return sb.toString();
    }
}

端到端測試

public class HuffmanTest {
    public static void main(String[] args) {
        String original = "abcdacaha"; // 測試文本
        HuffmanTree tree = new HuffmanTree();
        
        // 壓縮端
        String bits = tree.encode(original);
        byte[] bytes = HuffUtils.toBytes(bits);
        Map<String, Character> codeTable = tree.getCodeTable();
        int lastBits = bits.length() % 8 == 0 ? 8 : bits.length() % 8;
        
        System.out.println("原文: " + original);
        System.out.println("編碼: " + bits);
        System.out.println("字節數: " + bytes.length + " (原始 " + original.getBytes().length + " 字節)");
        System.out.println("編碼表: " + codeTable);
        
        // 模擬傳輸...
        
        // 解壓端
        String decodedBits = HuffUtils.toBits(bytes, lastBits);
        String restored = tree.decode(codeTable, decodedBits);
        System.out.println("還原: " + restored);
        System.out.println("驗證: " + original.equals(restored));
    }
}

輸出示例

原文: abcdacaha
編碼: 0100110111001011
字節數: 2 (原始 9 字節)
編碼表: {0=a, 100=b, 101=c, 110=d, 111=h}
還原: abcdacaha
驗證: true

工程化注意事項

• 編碼表必須隨數據傳輸：解碼端無法反推樹結構
• 最後一字節填充位處理：傳輸 lastValidBits 避免解碼多出垃圾字符
• 大文件分塊處理：避免一次性構建巨大樹、生成超長位串導致 OOM
• 性能優化：用 int[] 代替 Map 統計 ASCII/GBK 字符；位操作用 BitSet 或手寫位流
• 不適用場景：已壓縮數據、高熵隨機數據、極大文件（優先用 LZ77/LZ4/Zstd）