哈夫曼树
一句话总结
霍夫曼树是二叉树结构的经典应用，它是一种最优前缀编码树，常用于数据压缩。
核心内容
数据压缩基础
无损压缩 vs 有损压缩
| 类型 | 特点 | 示例 |
|---|---|---|
| 无损压缩 | 压缩后数据可完全还原，不丢失任何信息 | zip 压缩包 |
| 有损压缩 | 压缩后数据会丢失一些信息，但压缩率更高 | 图片压缩（降低色度精度） |
无损压缩的本质：编码和解码过程。压缩效果取决于算法能否充分挖掘原始数据中的冗余信息。
权衡三角：通用性 ↔ 压缩率 ↔ 性能
定长编码 vs 变长编码
| 编码方式 | 特点 | 优势 | 劣势 |
|---|---|---|---|
| 定长编码（如 ASCII） | 每个字符编码长度固定（如 8 位） | 可随机访问（按索引计算位置） | 存储效率低 |
| 变长编码（如 UTF-8） | 每个字符编码长度可变（1-4 字节） | 存储效率高 | 无法随机访问 |
示例：aaabacc 字符串
- 定长编码（2 比特/字符）：
00 00 00 01 00 10 11= 14 比特 - 变长编码（a=0, b=10, c=11）：
0 0 0 10 0 11 11= 10 比特
变长编码的三大难点
-
解码唯一性：如何设计编码保证无歧义？
- 核心原则：任意一个编码都不能是另一个编码的前缀（前缀码）
- 违反示例：a=1, b=10, c=11 →
11可解码为c或aa
-
压缩率：如何让编码数据尽可能短？
- 高频字符用短编码，低频字符用长编码
-
解码效率：如何保证解码速度？
- 保证前缀无歧义性后，解码复杂度从 O(NK) 降到 O(N)
- 其中 N 为编码数据长度，K 为最长编码长度
哈夫曼编码
定义：哈夫曼编码是一种通用无损压缩算法，通过构建最优前缀编码树（哈夫曼树）来实现数据压缩。
工作原理：
- 输入原始数据，统计字符频率
- 构建哈夫曼树（最优前缀编码树）
- 生成编码表（码表）
- 根据码表编码数据
- 解码时根据码表还原原始数据
优化目标：使所有字符的（频率 × 编码长度）之和最小。
关键要点
- 哈夫曼树是二叉树结构的经典应用
- 前缀码（任意编码不是其他编码的前缀）是保证解码唯一性的关键
- 变长编码通过给高频字符分配短编码来优化压缩率
- 哈夫曼编码是通用无损压缩算法，需要码表进行解码
待补充内容
⚠️ 本文内容不完整（原文使用 JavaScript 动态加载，仅获取到 141 行静态内容）：
- 哈夫曼树的构建算法（贪心策略）
- 哈夫曼编码的具体实现（Java 代码）
- 基于哈夫曼编码的压缩程序实现
- 与其他压缩算法的详细对比
相关概念
以下概念首次在此文提及，暂未创建独立页面（需 ≥2 篇来源）：
- 数据压缩（Data Compression）
- 无损压缩（Lossless Compression）
- 有损压缩（Lossy Compression）
- 定长编码（Fixed-Length Encoding）
- 变长编码（Variable-Length Encoding）
- 前缀码（Prefix Code）
- 哈夫曼树（Huffman Tree）
- 哈夫曼编码（Huffman Coding）
相关概念
- 二叉树：哈夫曼树的基础数据结构
相关实体
- labuladong：算法学习平台作者