《数据结构（C语言描述）（第2版）》教学课件4-14哈夫曼编码的构造

1、2016数据结构Data structure讲授：刘斌哈夫曼编码的构造常州信息职业技术学院02教学目标12编码和解码相关概念03最优二叉树构造哈夫曼编码三、链表的插入04哈夫曼编码的构造1.4哈夫曼树及哈夫曼编码4、哈夫曼编码编码和解码数据压缩过程称为编码。即将文件中的每个字符均转换为一个唯一的二进制位串。数据解压过程称为解码。即将二进制位串转换为对应的字符。等长、变长编码方案给定的字符集C，可能存在 多种编码方案。例如：ASCII编码中 A 的二进制编码为 01000001例如：ASCII编码、8421编码、数字的原码，反码，补码等三、链表的插入05哈夫曼编码的构造1.4哈夫曼树及哈夫曼编码

2、（1）等长编码方案等长编码方案将给定字符集C中每个字符的码长定为|C|表示字符集的大小。【示例】设待压缩的数据文件共有100000个字符，这些字符均取自字符集C=a，b，c，d，e，f，等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为300000位。06哈夫曼编码的构造1.4变长编码方案将频度高的字符编码设置较短，将频度低的字符编码设置较长。【示例4-30】设待压缩的数据文件共有100000个字符，这些字符均取自字符集C=a，b，c，d，e，f，其中每个字符在文件中出现的次数（简称频度）见表4-1。（2）变长编码方案字符abcdef频度（千次）4513121695定长编码0

3、00001010011100101变长编码010010111011101111表4-1 字符编码根据计算公式：(45*1+13*3+12*3+16*3+9*4+5*4)*1000=224000整个文件被编码为224000位，比定长编码方式节约了约25的存储空间。 注意：变长编码可能使解码产生二义性。原因是某些字符的编码可能与其他字符的编码开始部分（称为前缀）相同。07哈夫曼编码的构造1.4哈夫曼树及哈夫曼编码3前缀码方案对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀（编）码。 4最优前缀码平均码长或文件总长最小的前缀编码称为最优前缀码。最优前缀码对文

4、件的压缩效果亦最佳。 其中：pi为第i个字符的概率，li为码长。08哈夫曼编码的构造1.412利用哈夫曼树很容易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20至90，其压缩效率取决于被压缩文件的特征。5根据最优二叉树构造哈夫曼编码（1）编码构造方法用字符ci作为叶子，概率pi或频度fi作为叶子ci的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1；将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码（也称哈夫曼编码）。09哈夫曼编码的构造1.4设字符集C=a，b，

5、c，d，e，f，其中每个字符在文件中出现的频度分别为：45，13，12，16，9，5（千次）。求一个哈夫曼编码。 先构造哈夫曼树并将树中左分支和右分支分别标记为0和1，如图4-27； 再将从根到叶子的路径上的标号依次相连，得到如下哈夫曼编码。【例4-4】哈夫曼编码的构造。cb100554525301312defa1614950110010101a：0b：100c：101d：110e：1110f：1111 10哈夫曼编码的构造1.4（2）哈夫曼编码为最优前缀码由哈夫曼树求得的编码为最优前缀码，原因是：每个叶子字符ci的码长恰为从根到该叶子的路径长度li，平均码长（或文件总长）又是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小的二叉树，因此编码的平均码长（或文件总长）亦最小。树中没有一片叶子是另一叶子的祖先，每片叶子对应的编