哈夫曼树详解

哈夫曼树（Huffman Tree）是一种用于数据压缩的贪心算法数据结构，通过构建带权路径最短的二叉树实现高效编码。以下是核心要点：

‌1. 基本概念‌

• ‌目标‌：最小化带权路径长度（WPL = Σ 叶子权值 × 路径长度）。
• ‌特点‌：高频字符靠近根节点，编码更短；低频字符远离根节点，编码更长。

‌2. 构建步骤‌

1. ‌初始化‌：将每个字符及其频率作为独立节点。
2. ‌合并节点‌：重复选择频率最小的两个节点合并，生成新节点（权值为两者之和）。
3. ‌生成树‌：最终合并为单一根节点，形成哈夫曼树。

‌示例‌：字符集 {'A':5, 'B':9, 'C':12, 'D':13, 'E':16, 'F':45} 的构建过程：

• 合并 A+B → 新节点 (14)
• 合并 C+D → 新节点 (25)
• 合并 14+E → 新节点 (30)
• 合并 25+30 → 新节点 (55)
• 最后合并 55+F → 根节点 (100)。

‌3. 哈夫曼编码‌

• ‌规则‌：左分支标 0，右分支标 1，从根到叶子的路径即为字符编码。
• ‌示例‌：上述字符集的编码结果：
  • F:0（频率最高，路径最短）
  • A:1100（频率最低，路径最长）

‌4. 应用场景‌

• ‌数据压缩‌：ZIP、GZIP等格式的基础算法。
• ‌图像编码‌：JPEG中的熵编码阶段。
• ‌实时通信‌：减少传输数据量。
• 5. 复杂度与优化‌
• ‌时间复杂度‌：O(n log n)（使用优先队列）。
• ‌空间优化‌：动态统计频率时可结合滑动窗口。