Huffman编码

算法

Huffman编码是一种变长编码,对于出现频率较高的字符使用较短的编码,出现频率较低的字符使用较长的编码,从而达到压缩数据的目的。

时间复杂度:最佳 O(n log n) | 平均 O(n log n) | 最差 O(n log n)
空间复杂度:O(n)

应用场景/前提条件

  • 适用于任何类型的数据
  • 无损压缩
  • 贪心策略

算法讲解

Huffman编码

介绍

Huffman编码是一种重要的无损数据压缩算法,由David A. Huffman于1952年提出。核心思想是利用字符出现频率的不同,为每个字符设计长度可变的编码,保证出现频率高的字符使用较短的编码,频率低的字符使用较长的编码,实现数据压缩。

Huffman编码基于贪心策略构建最优前缀码,时间复杂度为O(n log n),n是不同字符的数量。在信息论、数据压缩和通信系统中有广泛应用,也是理解前缀编码和贪心算法的经典例子。

问题定义

给定一组字符及其出现频率,为每个字符设计一种二进制编码,实现:

  1. 任何字符的编码都不是其他字符编码的前缀(前缀性质)
  2. 所有字符编码长度的加权和最小(最优性质)

例如,给定字符集及频率:{'a':5, 'b':9, 'c':12, 'd':13, 'e':16, 'f':45},Huffman编码会生成一种编码方案,让总编码长度最小。

算法步骤

  1. 为每个字符创建一个叶节点,节点的权重为字符的频率
  2. 将所有节点放入优先队列(最小堆)中
  3. 重复以下操作,直到队列中只剩一个节点:
    • 取出两个权重最小的节点
    • 创建一个新的内部节点,其权重为两个节点的权重之和

...