跳到主要内容

Huffman Tree

定义​

哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，又称最优二叉树，常用于数据压缩编码。

带权路径长度 WPL​

WPL=∑i=1nwiliWPL = \sum_{i=1}^{n} w_i l_i

其中 wiw_i 为第 ii 个叶子结点的权值，lil_i 为该叶子结点到根的路径长度。

构造方法​

  1. 将 n 个权值作为 n 棵只有根结点的二叉树，构成森林
  2. 每次选取两棵根结点权值最小的树合并，新根权值为两者之和
  3. 重复步骤 2，直到只剩一棵树

哈夫曼编码​

  • 固定长度编码：每个字符编码长度相同
  • 可变长度编码：高频字符用短编码，低频字符用长编码
  • 前缀编码：任一编码都不是其他编码的前缀，保证解码唯一性

哈夫曼编码是一种最优前缀编码。