2.2.1 认识哈夫曼编码

什么是编码？编码就是将信息从一种形式或格式转换为另一种形式的过程，我们常说的汉语是一种编码形式，而英语也是一种编码形式，我们可以将汉语编码成英语，比如，猫编码成Cat，狗编码成Dog。现在我们想将英文字符串“i want to learn algorithm”通过计算机编码发送，编码条件要求如下。

（1）因为计算机只能识别二进制0和1，所以编码要由0和1组成，这样才能用于计算机的数据传输。

（2）保证编码的唯一性，即任一编码不是另一编码的前面部分，这样可以连在一起传送，例如，ABCD编码如下，

A:0;B:1;C:01;D:10

如果我们想要传输CD的字符串0110，那么计算机要怎样解码呢？是解码成ABBA，还是CD？因此，我们要保证任一编码不是另一编码的前缀，这也叫作“异前置码字”，这样可以使各码字连在一起传送，中间不需另加隔离符号，只要传送时不出错，接收端就可分离各个码字，不致混淆。

（3）编码是不定长的，即编码可以是任意长度，这种编码方式叫作可变字长编码（VLC）。有不定长的编码方式，就有定长的编码方式，计算机中常用的ASCII编码就属于定长编码。

（4）满足以上条件以后需要保证编码的长度是最短的。

哈夫曼于1952年提出了一种编码方式，该方法完全依据字符出现的概率来构造异前置的平均长度最短的码字，因为是哈夫曼提出的，所以称为哈夫曼编码，该方法完美解决了上述编码要求。哈夫曼编码已经被广泛用于计算机的通信压缩等领域。