哈夫曼树
Post on:
Words: 726
Lab 6.10
又称最优树,使用贪婪算法,经常用于数据压缩 (Huffman codes)

编码理论

A character-coding problem
在数据通信和压缩算法中,每个字符都被映射到一个特定的二进制码(codeword),以便在传输或存储过程中进行表示,码字的长度取决于所使用的编码方案。

定长编码

Fixed-length code
每个字符被赋予相同长度的编码
  • 一个常见的例子是 ASCII 编码,其中每个字符都用 8 位二进制数(1字节)表示。
  • 由于每个字符的编码长度相等,定长编码的主要优点是简单和快速解码。
  • 它不具备压缩效果,对于频率较低的字符,会造成编码空间的浪费。

变长编码

Variable-length code
为频率较高的字符分配较短的编码,为频率较低的字符分配较长的编码,从而提高编码效率

前缀码

Prefix code
若要设计不定长的编码,则必须保证一个字符的编码不是另一个字符的前缀,从而确保数据的唯一解码性,而无需引入任何分隔符或标记来区分不同的字符编码。

构造步骤


  1. 统计每个字符出现的频率
    1. notion image
  1. 构建 Huffman 树(从下往上建)
      • 在森林中选出两个最小的节点,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和
      • 把这两个节点移出集合,把它们之和放入集合再进行下一轮对比
  1. 创建 Huffman 编码表:从根节点开始,左子树分配编码 0,通过右子树分配编码 1
    1. notion image
      a
      0
      b
      101
      c
      100
      d
      111
      e
      1101
      f
      1100

伪代码

O(nlgn)O(n\lg n)
HUFFMAN(C) n = |C| // 获取字符集 C的大小,即字符的数量 /* 将 C 初始化为一个优先队列 Q, 即每个字符都被看作是一个单独的节点,并且根据其频率(权重)排序。*/ Q = C for i = 1 to n - 1 new node z // 创建新的节点z,将其作为两个最小频率节点的父节点 x = EXTRACT-MIN(Q) // 从 Q 中会移除并返回具有最小频率的元素 y = EXTRACT-MIN(Q) z.left = x z.right = y z.freq = x.freg + y.freq // freq 表示某个字符的出现频率 INSERT(Q,z) /* 实际生成的编码树是由节点 z 组成的,与 Q 无关 在循环结束后,队列中只剩下一个节点,即根节点,它具有最大频率。 根节点即代表完整的编码树,包含了所有字符的编码信息。*/ return EXTRACT-MIN(Q)