在了解熵编码的基本原理后，接下来我们来看一个比较简单的算法，哈夫曼编码。哈夫曼编码是美国科学家戴维·哈夫曼在1952年在麻省理工学院攻读博士学位时，在著名科学家罗伯特·费诺的指导下发明的一种基于有序频率二叉数的编码方法。这种方法的编码效率超过了他的导师费诺和信息论之父香浓的研究成果，也就是香浓-费诺编码。因此，哈夫曼编码又被人称作最优编码方法。从本质上来讲，哈夫曼编码是变长编码方法的一种。该方法完全依赖于码字出现的概率来构造整体平均长度最短的编码方法。进行哈夫曼编码最关键的步骤是建立符合哈夫曼编码规则的二叉树，这个二叉树又被称作哈夫曼树。哈夫曼树是一种比较特殊的二叉树，这个二叉树的叶子节点个数与需要编码的码源的个数相同。每个叶子节点上都带有各自的全值，而每个叶子节点的路径长度乘以该节点的全值，这些加全路径的总和称为整个二叉树的加全路径长度，在满足条件的所有二叉树中，该路径长度最短的二叉树就是我们想要的哈夫曼树。 在使用哈夫曼编码执行对码源的实际编码的过程中，可以把每个码源的全值设置为概率的值，那么就可以根据它们的全值来构建哈夫曼树。举例来说，如果我们希望对四个码源进行哈夫曼编码，这四个码源的概率分别为0.5、0.25、0.15和0.1，我们的编码过程就是：首先取出概率最小的两个码源进行合并生成一个新的码源CD，它的概率是这两个码源的概率之和0.5和0.1，然后将这个合并后的节点作为一个新的码源放到与其他节点进行比较。接着，再次从这些码源中找出概率最小的两个节点B和CD合并成BCD，然后将其全值0.5作为新的节点与之前的节点进行比较。最后，只剩下两个节点，它们再次合并就可以得到哈夫曼树的根节点，也是全值为1的节点。这个二叉树就是我们对这四个码源进行哈夫曼编码的过程中所生成的哈夫曼树。 在哈夫曼树构建完成之后，便可以得到每个码源的哈夫曼编码的码字。具体的方法是从哈夫曼树的根节点开始前进，每次访问该节点的左子树时赋值为0，访问右子树时赋值为1，从而得到该码源的哈夫曼编码的码字。例如，如果我们想获得C这个码源的哈夫曼编码码字，我们可以从根节点前进到右子树，分别以1、1访问BCD节点，然后再访问CD的左子树C，给它赋值0，因此C的哈夫曼编码码字就是110。同样地，我们还可以得到其他三个元素（即A、B、D）的哈夫曼编码码字，分别为0、1、010和111。从这个码表可以看出，哈夫曼编码的任意一个码字都不可能是其他码字的前缀，因此通过哈夫曼编码的信息，这些码字可以进行紧密的排列传输，而不用担心解码的时候会造成歧义。