哈夫曼編碼原理與 Java 實現無損壓縮工具完整指南

核心概念

哈夫曼樹

帶權路徑長度 (WPL) 最小的二叉樹。WPL = Σ(葉子節點權值 × 到根路徑長度)。

哈夫曼編碼

從根到葉：左分支編 0，右分支編 1。高頻字符編碼短，低頻字符編碼長，實現無損壓縮。

哈夫曼壓縮特點

• 無損壓縮，信息熵不損失。
• 理論證明：在無損壓縮中最優（針對字符級編碼）。
• 廣泛應用於 ZIP、JPEG、MP3 等格式的熵編碼階段。

壓縮流程與 Java 關鍵代碼

1. 統計字節頻率（0-255）

int[] byteCount = new int[256];
InputStream bis = new BufferedInputStream(new FileInputStream(inputPath));
int b;
while ((b = bis.read()) != -1) {
    byteCount[b]++;
}
bis.close();

2. 構建哈夫曼樹（優先隊列/最小堆）

PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(HfmNode::getWeight));
for (int i = 0; i < 256; i++) {
    if (byteCount[i] > 0) pq.add(new HfmNode(byteCount[i], i));
}
while (pq.size() > 1) {
    HfmNode n1 = pq.poll();
    HfmNode n2 = pq.poll();
    HfmNode parent = new HfmNode(n1.weight + n2.weight, -1); // -1 表示內部節點
    parent.left = n1;
    parent.right = n2;
    pq.add(parent);
}
HfmNode root = pq.poll();

3. 遞歸生成編碼表 String[256]

void buildCodes(HfmNode node, String prefix) {
    if (node.isLeaf()) {
        codes[node.data] = prefix;
        return;
    }
    if (node.left != null) buildCodes(node.left, prefix + '0');
    if (node.right != null) buildCodes(node.right, prefix + '1');
}

4. 寫入文件頭：每字節編碼長度（1 字節）

for (int i = 0; i < 256; i++) {
    bos.write(codes[i] == null ? 0 : codes[i].length());
}

5. 寫入編碼表內容（位流打包成字節）

將所有字節的編碼拼成長位串，每 8 位切一字節寫入；最後不足 8 位補 0，並記錄補位數（1 字節）。

6. 壓縮文件數據：按編碼表轉碼並打包

讀取原文件每字節，查表輸出對應位串，同樣 8 位打包寫入；結尾補 0 並記錄補位數。

解壓縮：逆向流程

1. 讀取 256 字節編碼長度，重建編碼長度表。
2. 讀取編碼表位流，按長度截取還原每字節編碼字符串。
3. 用編碼表構建解碼字典（編碼→字節）。
4. 讀取壓縮數據位流，逐位匹配字典輸出原字節。
5. 處理末尾補位。

關鍵技術點

• 位流操作：用 int 累積位，滿 8 位輸出字節；解碼時逐位遍歷哈夫曼樹（0 左 1 右）至葉子輸出。
• 文件頭設計：固定 256 字節長度表 + 變長編碼表 + 補位標記，無需額外分隔符。
• 邊界情況：單一字符文件、空文件、補位處理。

完整源碼包含 HfmNode、HfmTree、Compressor、Decompressor 四大類，可作為教學級壓縮工具參考實現。