哈夫曼編碼 是一種前綴編碼，利用字符出現頻率構建最優二叉樹（哈夫曼樹），高頻字符編碼短、低頻字符編碼長，實現無損壓縮。核心步驟：
import java.util.*;
public class HuffmanCoding {
// 節點類：包含字符、權重、左右孩子、父節點索引
private static class Node {
char ch; // 字符（葉子節點有效）
int weight; // 權重
int left, right, parent; // 孩子、父節點索引
Node(char ch, int weight) {
this.ch = ch; this.weight = weight;
left = right = parent = -1;
}
Node(int weight, int left, int right) {
this.ch = 0; this.weight = weight;
this.left = left; this.right = right; parent = -1;
}
boolean isLeaf() { return left == -1 && right == -1; }
}
private final Node[] tree; // 哈夫曼樹數組
private final String[] codes; // 編碼表
private final Map encodeMap = new HashMap<>();
private final Map decodeMap = new HashMap<>();
/** 構造器：傳入字符與權重數組 [[ch, weight], ...] */
public HuffmanCoding(int[][] charWeights) {
int n = charWeights.length;
if (n == 0) throw new IllegalArgumentException("字符集不能為空");
// 1. 初始化葉子節點
tree = new Node[2 * n - 1];
for (int i = 0; i < n; i++) {
tree[i] = new Node((char) charWeights[i][0], charWeights[i][1]);
}
// 2. 構建內部節點
for (int i = n; i < 2 * n - 1; i++) {
// 選擇兩個權重最小且無父節點的節點
int[] minTwo = selectMinTwo(i);
int l = minTwo[0], r = minTwo[1];
tree[l].parent = tree[r].parent = i;
tree[i] = new Node(tree[l].weight + tree[r].weight, l, r);
}
// 3. 生成編碼表
codes = new String[n];
buildCodes(n);
}
/** 選擇權重最小的兩個無父節點 */
private int[] selectMinTwo(int limit) {
int min1 = -1, min2 = -1;
for (int i = 0; i < limit; i++) {
if (tree[i].parent == -1) { // 無父節點
if (min1 == -1 || tree[i].weight < tree[min1].weight) {
min2 = min1;
min1 = i;
} else if (min2 == -1 || tree[i].weight < tree[min2].weight) {
min2 = i;
}
}
}
return new int[]{min1, min2};
}
/** 從葉子向根構建編碼 */
private void buildCodes(int n) {
for (int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
int cur = i, par = tree[i].parent;
while (par != -1) {
if (tree[par].left == cur) sb.append('0');
else sb.append('1');
cur = par;
par = tree[cur].parent;
}
codes[i] = sb.reverse().toString();
encodeMap.put(tree[i].ch, codes[i]);
decodeMap.put(codes[i], tree[i].ch);
}
}
/** 編碼：字符串 -> 壓縮二進制字符串 */
public String encode(String text) {
StringBuilder sb = new StringBuilder();
for (char c : text.toCharArray()) {
String code = encodeMap.get(c);
if (code == null) throw new IllegalArgumentException("字符不在編碼表中: " + c);
sb.append(code);
}
return sb.toString();
}
/** 解碼：壓縮二進制字符串 -> 原文 */
public String decode(String encoded) {
StringBuilder sb = new StringBuilder();
int root = tree.length - 1; // 根節點索引
int cur = root;
for (char bit : encoded.toCharArray()) {
cur = (bit == '0') ? tree[cur].left : tree[cur].right;
if (tree[cur].isLeaf()) {
sb.append(tree[cur].ch);
cur = root; // 重置到根
}
}
return sb.toString();
}
/** 獲取編碼表（調試用） */
public void printCodes() {
for (int i = 0; i < codes.length; i++) {
System.out.printf("'%c' (w=%d): %s%n", tree[i].ch, tree[i].weight, codes[i]);
}
}
// ========== 測試主方法 ==========
public static void main(String[] args) {
// 示例：字符及頻率
int[][] data = {
{'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5}
};
HuffmanCoding hc = new HuffmanCoding(data);
hc.printCodes();
// 輸出示例：
// 'f' (w=5): 1100
// 'e' (w=9): 1101
// 'c' (w=12): 100
// 'b' (w=13): 101
// 'd' (w=16): 00
// 'a' (w=45): 01
String text = "abcdef";
String encoded = hc.encode(text);
String decoded = hc.decode(encoded);
System.out.println("原文: " + text);
System.out.println("編碼: " + encoded);
System.out.println("解碼: " + decoded);
System.out.println("驗證: " + text.equals(decoded)); // true
}
} | 模塊 | 核心邏輯 | 複雜度 |
|---|---|---|
| 樹構建 | 數組模擬樹，selectMinTwo 線性掃描選最小兩個 | O(n²) 可優化為 O(n log n) 用優先隊列 |
| 編碼生成 | 從葉子向根回溯，左 0 右 1，反轉得編碼 | O(n * h) h=樹高 |
| 編碼壓縮 | 查表拼接字符串 | O(m) m=文本長度 |
| 解碼還原 | 從根按位遍歷樹，遇葉子輸出字符並重置 | O(k) k=編碼位長 |
PriorityQueue 將構建樹降為 O(n log n)。BitOutputStream，解碼用 BitInputStream，避免字符串開銷。本文提供了結構清晰、邏輯完整、可直接運行的哈夫曼編碼解碼 Java 實現。通過數組模擬樹、雙向 Map 加速查找、迴溯生成編碼，展示了經典算法的工程化落地要點。理解此實現，可輕鬆擴展至文件壓縮、網絡傳輸優化等實際場景。
