算法引入
数据压缩是现代信息技术的基石。一个800MB的高清电影之所以能通过网络快速传输，正是因为压缩算法大幅减少了数据量。在众多压缩技术中，哈夫曼编码（Huffman Coding） 是最经典的无损压缩算法之一，它由大卫·哈夫曼于1952年在MIT攻读博士学位时提出。哈夫曼编码利用贪心策略，根据字符出现频率构建最优前缀码，使高频字符用短码表示、低频字符用长码表示，从而达到最优的压缩效率。
核心思想
哈夫曼编码的核心是最优前缀码的构造。前缀码要求任何字符的编码都不是其他字符编码的前缀，这保证了解码时无需分隔符即可唯一确定每个字符。
构造过程采用贪心策略：
- 统计频率：计算每个字符在数据中出现的次数
- 构建森林：每个字符作为一个带权节点（权重=频率），形成一片森林
- 反复合并：每次选择权值最小的两棵树合并为一棵新树，新树的权值为两者之和。新树的左分支标记为0，右分支标记为1
- 形成编码树：重复合并直到只剩一棵树，从根到每个叶子节点的路径就是该字符的哈夫曼编码
贪心策略的正确性由最优子结构和贪心选择性质保证：频率最低的两个字符在最优编码树中必然是最深的兄弟节点，将其合并不会破坏全局最优性。
完整Java实现
import java.util.*;
/**
* 哈夫曼编码（Huffman Coding）实现
* 贪心策略构建最优前缀码，实现数据无损压缩
* 压缩率取决于字符频率分布，通常为20%-90%
*/
public class HuffmanCoding {
/**
* 哈夫曼树节点
*/
private static class HuffmanNode implements Comparable<HuffmanNode> {
char ch; // 字符（叶子节点有效）
int frequency; // 频率/权重
HuffmanNode left; // 左子树
HuffmanNode right; // 右子树
HuffmanNode(char ch, int frequency) {
this.ch = ch;
this.frequency = frequency;
}
HuffmanNode(int frequency, HuffmanNode left, HuffmanNode right) {
this.frequency = frequency;
this.left = left;
this.right = right;
}
boolean isLeaf() {
return left == null && right == null;
}
@Override
public int compareTo(HuffmanNode other) {
return Integer.compare(this.frequency, other.frequency);
}
}
/** 字符到编码的映射表 */
private Map<Character, String> charToCode;
/** 编码到字符的映射表（用于解码） */
private Map<String, Character> codeToChar;
/** 哈夫曼树根节点 */
private HuffmanNode root;
/**
* 根据输入文本构建哈夫曼编码
*
* @param text 原始文本
*/
public void build(String text) {
if (text == null || text.isEmpty()) {
throw new IllegalArgumentException("输入文本不能为空");
}
// 第一步：统计字符频率
Map<Character, Integer> frequencyMap = new HashMap<>();
for (char ch : text.toCharArray()) {
frequencyMap.merge(ch, 1, Integer::sum);
}
// 第二步：构建哈夫曼树
this.root = buildTree(frequencyMap);
// 第三步：生成编码表
this.charToCode = new HashMap<>();
this.codeToChar = new HashMap<>();
generateCodes(root, new StringBuilder());
}
/**
* 使用贪心策略构建哈夫曼树
* 每次选择权值最小的两棵树合并
*
* @param frequencyMap 字符频率映射
* @return 哈夫曼树根节点
*/
private HuffmanNode buildTree(Map<Character, Integer> frequencyMap) {
// 使用优先队列（小根堆）管理节点
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
// 将所有字符节点加入优先队列
for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
}
// 贪心合并：每次取两个最小权值节点合并
while (pq.size() > 1) {
HuffmanNode left = pq.poll(); // 权值最小的节点
HuffmanNode right = pq.poll(); // 权值次小的节点
// 合并为新节点，权值为两者之和
int sumFreq = left.frequency + right.frequency;
HuffmanNode parent = new HuffmanNode(sumFreq, left, right);
pq.offer(parent);
}
return pq.poll();
}
/**
* 递归生成每个字符的哈夫曼编码
* 左分支标记0，右分支标记1
*
* @param node 当前节点
* @param prefix 当前路径前缀
*/
private void generateCodes(HuffmanNode node, StringBuilder prefix) {
if (node == null) return;
if (node.isLeaf()) {
// 叶子节点，记录编码
String code = prefix.length() > 0 ? prefix.toString() : "0";
charToCode.put(node.ch, code);
codeToChar.put(code, node.ch);
return;
}
// 遍历左子树，追加0
prefix.append('0');
generateCodes(node.left, prefix);
prefix.deleteCharAt(prefix.length() - 1);
// 遍历右子树，追加1
prefix.append('1');
generateCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length() - 1);
}
/**
* 将原始文本编码为哈夫曼二进制串
*
* @param text 原始文本
* @return 编码后的二进制字符串
*/
public String encode(String text) {
StringBuilder encoded = new StringBuilder();
for (char ch : text.toCharArray()) {
encoded.append(charToCode.get(ch));
}
return encoded.toString();
}
/**
* 将哈夫曼二进制串解码为原始文本
*
* @param encodedText 编码后的二进制字符串
* @return 原始文本
*/
public String decode(String encodedText) {
StringBuilder decoded = new StringBuilder();
StringBuilder current = new StringBuilder();
for (char bit : encodedText.toCharArray()) {
current.append(bit);
Character ch = codeToChar.get(current.toString());
if (ch != null) {
decoded.append(ch);
current.setLength(0);
}
}
return decoded.toString();
}
/**
* 将二进制字符串转换为字节数组（实际压缩存储）
*
* @param bitString 二进制字符串
* @return 压缩后的字节数组
*/
public byte[] toByteArray(String bitString) {
int length = bitString.length();
int byteLength = (length + 7) / 8;
byte[] bytes = new byte[byteLength];
for (int i = 0; i < length; i++) {
if (bitString.charAt(i) == '1') {
bytes[i / 8] |= (1 << (7 - (i % 8)));
}
}
return bytes;
}
/**
* 将字节数组转换回二进制字符串
*
* @param bytes 字节数组
* @param bitLength 原始二进制字符串长度
* @return 二进制字符串
*/
public String fromByteArray(byte[] bytes, int bitLength) {
StringBuilder bits = new StringBuilder();
for (int i = 0; i < bitLength; i++) {
int byteIndex = i / 8;
int bitIndex = 7 - (i % 8);
bits.append((bytes[byteIndex] >> bitIndex) & 1);
}
return bits.toString();
}
/**
* 打印字符频率统计和编码表
*/
public void printCodeTable() {
System.out.println("=== 哈夫曼编码表 ===");
System.out.printf("%-10s %-10s %-15s %-10s%n", "字符", "频率", "编码", "编码长度");
System.out.println("-".repeat(50));
// 按编码长度排序显示
List<Map.Entry<Character, String>> entries = new ArrayList<>(charToCode.entrySet());
entries.sort(Comparator.comparingInt(e -> e.getValue().length()));
int totalBits = 0;
int totalChars = 0;
for (Map.Entry<Character, String> entry : entries) {
char ch = entry.getKey();
String code = entry.getValue();
// 从root重新计算频率
int freq = getFrequency(root, ch);
totalBits += freq * code.length();
totalChars += freq;
String display = (ch == ' ') ? "[空格]" : (ch == '\n') ? "[换行]" : String.valueOf(ch);
System.out.printf("%-10s %-10d %-15s %-10d%n", display, freq, code, code.length());
}
System.out.println("-".repeat(50));
int originalBits = totalChars * 8; // ASCII编码
System.out.println("原始大小(ASCII): " + originalBits + " bits");
System.out.println("压缩后大小: " + totalBits + " bits");
System.out.printf("压缩率: %.2f%%%n", (1 - (double) totalBits / originalBits) * 100);
}
/**
* 辅助方法：在树中查找字符频率
*/
private int getFrequency(HuffmanNode node, char ch) {
if (node == null) return 0;
if (node.isLeaf() && node.ch == ch) return node.frequency;
return getFrequency(node.left, ch) + getFrequency(node.right, ch);
}
/**
* 序列化哈夫曼树为字符串（用于存储编码表）
*/
public String serializeTree() {
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private void serializeHelper(HuffmanNode node, StringBuilder sb) {
if (node == null) return;
if (node.isLeaf()) {
sb.append('1').append(node.ch);
} else {
sb.append('0');
serializeHelper(node.left, sb);
serializeHelper(node.right, sb);
}
}
/**
* 主方法：演示哈夫曼编码的完整流程
*/
public static void main(String[] args) {
String text = "Huffman coding is a data compression algorithm. " +
"It assigns variable-length codes to characters based on their frequencies. " +
"Frequent characters get shorter codes, while infrequent characters get longer codes. " +
"This greedy approach guarantees optimal prefix codes.";
System.out.println("原始文本:");
System.out.println(text);
System.out.println("原始文本长度: " + text.length() + " 字符, " + (text.length() * 8) + " bits\n");
// 构建哈夫曼编码
HuffmanCoding huffman = new HuffmanCoding();
huffman.build(text);
// 打印编码表
huffman.printCodeTable();
// 编码
String encoded = huffman.encode(text);
System.out.println("\n编码后二进制串长度: " + encoded.length() + " bits");
System.out.println("编码后(前100位): " + encoded.substring(0, Math.min(100, encoded.length())) + "...");
// 转换为字节数组
byte[] compressed = huffman.toByteArray(encoded);
System.out.println("压缩后字节数: " + compressed.length);
// 解码验证
String bitString = huffman.fromByteArray(compressed, encoded.length());
String decoded = huffman.decode(bitString);
System.out.println("\n解码验证: " + (text.equals(decoded) ? "成功 ✓" : "失败 ✗"));
System.out.println("解码后文本(前80字符): " + decoded.substring(0, Math.min(80, decoded.length())) + "...");
// 树序列化
System.out.println("\n哈夫曼树序列化: " + huffman.serializeTree().substring(0, 50) + "...");
}
}
算法正确性证明
哈夫曼编码的最优性可通过贪心算法的两个性质证明：
贪心选择性质：设 $x$ 和 $y$ 是频率最低的两个字符，则存在一个最优前缀码使 $x$ 和 $y$ 具有相同最大长度且互为兄弟节点。若某最优树中 $x$ 和 $y$ 不是最深兄弟，可通过交换将它们调整到最深位置，不会增加树的带权路径长度（WPL）。
最优子结构：将 $x$ 和 $y$ 合并为新节点 $z$（频率为 $f_x + f_y$），对缩减后的字符集 $C’ = C – {x, y} \cup {z}$ 构建最优树 $T’$。将 $T’$ 中的 $z$ 展开为 $x$ 和 $y$ 的父节点，得到的树 $T$ 就是原问题的最优解。
由这两个性质，通过数学归纳法可严格证明哈夫曼算法生成的编码树具有最小的带权路径长度，即实现了最优压缩。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 统计频率 | $O(n)$ | $n$ 为文本长度 |
| 构建编码树 | $O(k \log k)$ | $k$ 为不同字符数，优先队列每次操作 $O(\log k)$ |
| 生成编码表 | $O(k)$ | 遍历树的所有叶子节点 |
| 编码过程 | $O(n)$ | 每个字符查表替换为编码 |
| 解码过程 | $O(m)$ | $m$ 为编码后位数，逐位遍历哈夫曼树 |
| 总空间 | $O(k)$ | 存储哈夫曼树和编码表 |
应用场景
哈夫曼编码及其变体在数据压缩领域有深远影响：
- 文件压缩：ZIP格式中的DEFLATE算法将哈夫曼编码与LZ77字典压缩结合，实现了高效的通用文件压缩
- 图像压缩：JPEG图像的熵编码阶段使用哈夫曼编码对量化后的DCT系数进行压缩
- 音频压缩：MP3格式利用哈夫曼编码对 psychoacoustic 模型处理后的频谱数据进行无损压缩
- 视频编码：H.264/H.265等视频编码标准在CABAC之前使用哈夫曼编码（或算术编码）进行熵编码
- 网络传输：HTTP/2的HPACK头部压缩使用静态哈夫曼表对常见头部字段编码
哈夫曼编码以优雅的贪心设计，证明了”高频短码、低频长码”这一直觉性策略在数学上的最优性。它不仅是数据压缩领域的奠基算法，更是贪心算法”局部最优导向全局最优”的经典范例——将频率统计转化为树形合并，用最简单的优先队列实现了理论最优的编码效率。
