Huffmancode.docVIP

哈夫曼编码问题 哈天曼编码(Huffman Code)问题是一个有着广泛用途的知名问题。哈夫曼编码是一个最佳前缀码的编码方法。我们先介绍前缀码。 前缀码 大家知道，任何信息都是以二进制編码形式存放在计算机里和传输于网络之中。例如，ASCII码把大、小写英文字母，标点符号及其他控制符号一共128个字符中每一个对应到一个7个比特的二进制数上去。这种编码使用的是定长的编码。这种编码使用方便但通信量较大，即传输的比特数较多。这是因为，不同的符号在报文中出现的频率不一样。比如字母e在报文中出现频率很高而字母z则很少出现。如果我们用较少比特数为字母e编码而用较多的比特数为z编码，则可大大减少传输的比特数。可是，如果我们使用变长的编码，接收方解码时怎么把一连串二进制序列正确地断开为一个个字符呢？例如，我们把字母A编为0，B编为1，C编为01，那么序列0101应解码为ABAB呢，还是ABC呢，还是CAB呢？为了避免二义性，我们要求任一字符的编码都必须不是任一其他字符编码的前缀。这样，接收方解出的码是唯一的。这样编出的码字称为前缀码。 假设我们须要设计n个字符的前缀码，我们可以用一个有n个树叶的完全二叉树来实现，其中每个叶子对应一个字符。具体做法是，从根开始，在联结任一内结点与其左右儿子的两条边上分别标上0和1。然后，从根到某一叶子的路径上边的标号序列作为这个叶子对应字符的编码。因为任一条这样的路径不可能是另外一条路径的前缀，所得的编码必定是前缀码。在这个二叉树中，一个内结点代表着以它为根的子树中所有前缀码的集合。图7-5给出了一个有7个叶子的二叉树及对应的7个字符的前缀码。我们把这样一个二叉树称为前缀码树。 图1 一个有七个叶结点的前缀码树 反之，给定一个n个字符的前缀码，我们也可以找到对应的有n个叶子的二叉树，这个二叉树可以构造如下。我们把这n个前缀码分为二组，第一个比特为0的前缀码组成第一组，第一个比特为1的前缀码组成第二组。相应地，我们从根画出二条连结其左右子树的边。它的左儿子代表第一组前缀码，而右儿子代表第二组前缀码。然后递归地画出左子树和右子树。在这个过程中，如果在k层一个内结点含有二个或二个以上前缀码时，我们用第(k+1)个比特把它们分为二组，分别对应它的左右儿子。第(k+1)个比特为0的前缀码组成第一组，对应左儿子，第(k+1)个比特为1的前缀码组成第二组，对应右儿子。我们举一例子说明。 例：假设我们有如下6个字符的前缀码：A = 01，B = 001，C = 000，D = 110，E = 10，F = 111。试构造对应的二叉树。 解： 下面图7-6 说明了这个二叉树的构造步骤。 图7-6 对应于6个字符前缀码的二叉树 如果在构造中，从某个内结点分出的两个组中有一个为空集，那么对应的子树为空子树，即这个内结点只有一个儿子。这时，这个二叉树不是完全二叉树。这说明这个结点的前缀码中对应的比特是多余的，不起作用。这样的前缀码不会是最优的。 最佳前缀码(哈夫曼編码(Huffman code) 我们在这里考虑的问题是，如何对一组字符编码以使得用它来对一个文件编码时所需要的总的比特数最少。这样在我们存储和传输这个文件时即省空间又省时间。比如，一个文件有n个字符要编码，如果用7位的定长码的话，我们需要7n个比特。如果用变长的编码，是否可以用少一些比特数呢？这要看情况，有些情况下，变长码优于定长码，而有些情况则不一定。比如在变长码中，我们用01表示A，用10表示B，那么如果一个文件含有n个A和B，我们只须要用2n个比特，当然很好。但是，在变长码中，我们也许用10个比特表示X和Y，而这时，传输n个X和Y，那就需要10n个比特了。所以，我们要考虑的是平均效果。那么，如何来评价一个编码的好坏呢？ 从图7-5可见，在前缀码中，一个字符需要的比特数就等于它在前缀码树中代表该字符的叶子的深度。所以，如果一个字符c在一个文件中平均出现f(c)次，而它对应的叶子在前缀码树的深度为d(c)的话，那么，这个字符在一个文件中平均需要f(c)d(c)比特。因此，一个文件平均需要的比特数就是所有字符所需平均比特数的总和。 假设T是对子符集S定义的前缀码树，那么该前缀码可以用下面公式来评价： B(T) = (7.1) 在这个公式，如果我们把f(c)改为出现的频率，那么(7.1)式仍可以用来评价T的优劣，因为频率乘以文件长度n就是平均出现次数。现在我们定义最佳前缀码如下。 定义 假设S是一个字符集。其中任一字符c ( S 在文件中出现的频率为f(c)。S的一个前缀码称为最佳前缀码，如果其前缀码树对应的(7.1)式的值是所有前缀码树中最小的。 下面讨论如何构造最佳前缀码或前缀码