七、熵编码算法（1）：基础知识

一、熵编码的概念

• 熵
  • 化学和热力学，用于度量能量退化的指标
  • 熵越高，物体或系统的做功能力越低
• 信息学中的熵
  • 表示信源所发出信息的不确定性
  • 越是随机的、前后不相关的信息，其熵越高
• 信源编码定理
  • 说明了香农熵与信源符号概率之间的关系
  • 信息的熵为信源无损编码后的平均码字长度的下限
  • 任何的无损编码方法都不可能使编码后的平均码长小于香农熵，只能使其尽量接近

　　前面的表述球之间的关系相对于后面这个是比较繁琐的，而且由于前面的排列之间没有任何的规律，进行改进和压缩的空间也就比较小了；因此：混乱程度高的信源，所表达的信息更难被压缩，熵也更高

• 基本思想
  • 使其前后的码字之间尽量更加随机，尽量减小前后的相关性，更加接近其信源的香农熵
• 常用熵编码算法
  • 变长编码：运算复杂度和编码效率都比较低，常用方法：哈夫曼编码、香农-费诺编码等；
  • 算术编码：运算较复杂，但编码效率更高

二、熵编码的简单实现——哈夫曼编码

• 哈夫曼编码
  • 变长编码方法的一种，依赖于码字出现的概率来构造整体平均长度最短的编码方法
  • 关键步骤：建立符合哈夫曼编码规则的二叉树，该树又称作哈夫曼树
• 哈夫曼树：
  • 一种特殊的二叉树，其终端节点的个数与待编码的码元的个数等同，而且每个终端节点上都带有各自的权值
  • 每个终端节点的路径长度乘以该节点的权值的总和称为整个二叉树的加权路径长度。在满足条件的各种二叉树中，该路径长度最短的二叉树即为哈夫曼树。

在使用哈夫曼编码执行对码元的实际编码过程时，码元的权值可设置为其概率值，那么可以根据其权值来构建哈夫曼树。我们假设使用哈夫曼编码对以下概率的码字进行编码：

码字 概率
A 0.1
B 0.1
C 0.15
D 0.2
E 0.2
F 0.25

根据概率表构建哈夫曼树的过程如下图所示：

最终我们可以得到如下图所示的哈夫曼树：

　　在哈夫曼树构建完成后，便可以得到每一个码元的哈夫曼编码的码字。具体方法是：从哈夫曼树的根节点开始遍历，直至每一个终端节点，当访问某个节点的左子树时赋予码字0，访问右子树时赋予一个码字1（反之亦可），直到遍历到终端节点时这一路径所代表的0和1的串便是该码元的哈夫曼编码码字。
　　例如上图的哈夫曼树，根节点访问左子树ABCF，赋予码字0；然后再访问左子树ABC，赋予码字0，此时整个码字为00，然后访问右子树得到终端节点C，赋予码字1，此时便可以得到C的哈夫曼编码码字001。以此规律，整个六个元素的码元集合的编码码表为：

A: 0000
B: 0001
C: 001
D: 10
E: 11
F: 01
　　从这个码表中还可以看出另外一个规律：哈夫曼编码的任意一个码字，都不可能是其他码字的前缀。因此通过哈夫曼编码的信息可以紧密排列连续传输，而不用担心解码时的歧义性。