霍夫曼（Huffman）算法的简介

Huffman 编码是 1952 年为压缩文本文件所设计的编码方法，也是目前消除视频信息冗余最常使用的方法之一；其对出现概率最大的符号赋以最短的码字，概率越小表示的码字越长，从而使表示每个符号的平均比特数最小。

霍夫曼（Huffman）编码的步骤

1. 把信源符号按概率大小顺序排列；（概率排序）
2. 在分配码字长度时，首先将两个出现概率最小的两个符号的概率相加，合成一个概率；（合并）
3. 把这个合成概率看作是一个新组合符号的概率，重复上述做法，直到最后只剩下两个符号的概率为止；（置换）
4. 完成上述步骤后，再返回向前进行编码，每层有两个分支，分别赋予 0 和 1（大的赋 0 或小的赋 0 均可，但必须一致）。

霍夫曼（Huffman）编码的特点

• 霍夫曼编码是瞬时惟一的可解块编码；
  • 瞬时：符号串中每个码字无需参考后继符号就可解码；
  • 惟一可解码：任何符号串只能以一种方式解码；
  • 块编码：每个信源符号都映射到一个编码符号的固定序列中；
• 霍夫曼编码是惟一可译码。短的码不会成为更长码的起始部分；
• 霍夫曼编码的平均码长接近于熵；
• 与计算机的数据结构不匹配；
• 需要多次排序，耗费时间。

注意：

• 霍夫曼编码的算法是确定的，但编出的码并非是唯一的。
• 由于霍夫曼编码的依据是信源符号的概率分布，故其编码效率取决于信源的统计特性。

霍夫曼（Huffman）编码的局限性

• 只适用于离散信源，即信源符号个数为有限数；
• 编码时需要知道输入符号集的概率分布；
• 在进行 Huffman 编码压缩时，计算量大而复杂，尤其是译码复杂度较高；
• 由于码长不等，还存在一个输入与输出的速率匹配问题。