September 12, 2005
霍夫曼编码
刚刚上了两次多媒体技术课，黄老师讲的很好，只是我以前没有这方面的基础，听起来比较困难，所以下课的时候又看了会儿讲义，才明白黄老师讲的是什么意思，不知道以后如果加的是教材里面没有的东西该怎么办呢。下面的是上次说的霍夫曼编码的内容，这种编码方式编出的代码压缩比最接近于信息熵，而且还是无损压缩编码，所以得到了广泛的应用，比如图片、声音、视频等的压缩就会用到霍夫曼编码，而实际中往往是无损和有损的编码方式混用。霍夫曼编码也不是没有缺点：首先，这种编码方式么有错误保护功能，若其中任何一位码出现错误，就会出现误码传播；其次，霍夫曼编码的码长不固定，这样在译码是必须有编码表，否则无法译码，而编码表传送是不经济的，这样等于没有压缩；不过还好，人们已经制定了相应的标准，这样双方遵守同样的标准，就不需要再传送编码表了，而目前也确实是这样做的。
霍夫曼(Huffman)在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以一个具体的例子说明它的编码步骤：
1。初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表4-03和图4-02所示。
2。把概率最小的两个符号组成一个节点，如图4-02中的D和E组成节点P1。
3。重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。
4。从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。
5。从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表4-03所示。
按照香农理论，这幅图像的熵为（对数是2为底数，不太好输入，理解就可以了）
H(S) = (15/39)Xlog2(39/15) + (7/39) Xlog2(39/7) + ... ...+ (5/39) Xlog2(39/5) = 2.1859
压缩比1.37:1。
霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。
采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。
与香农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外添加标记符号，即在译码时分割符号的特殊代码。此外，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。