数据结构 赫夫曼编码.ppt

* SWPU-SCS Data Structure 电报编码 原文 电文（二进制字符串） 原文 发送方 接收方 假设要传输的原文为：WINNIE WILL WIN 方案1： 等长编码 发送方：将WINNIE WILL WIN 转换成 000|001|010|010|001|011|000|001|100|100|000|001|010 接收方：将 电文还原为 WINNIE WILL WIN 编码 译码 编码、译码较容易，但电文总长度较大 W I N E L 000 001 010 011 100 总长度39 电报编码 方案2： 不等长编码 　发送方：将WINNIE WILL WIN转换成 00|0|01|01|0|011|00|0|100|100|00|0|01 　接收方： 0000101001100010010000001转换成 IIINNIEIIILLWIN WINNINLNWLIIIN …… 任一字符的编码不是其他字符编码的前缀，称为前缀编码 W I N E L 00 0 01 011 100 总长度25 出现歧义 电报编码 W I N E L 011 010 11 00 10 W I N E L 00 11 10 010 011 发送方：011|010|11|11|010|00|011|010|10|10|011|010|11 总长度33 接收方： WINNIE WILL WIN 发送方： 00|11|10|10|11|010|00|11|011|011|00|11|10 接收方： WINNIE WILL WIN 总长度29 目标 * 最优二叉树 如何能让编码总长度最短且译码唯一？ 解决方案 * (1)利用二叉树来设计二进制的前缀码； 如右图：a----0 b---10 c----110 d---111 c d b a 7 5 2 4 即求以n种字符的频率为权，设计一棵Huffman树的问题，对应的编码称为Huffman编码。 (2)设计总电文最短的前缀码： 假定以每种字符的出现次数或出现频率为wi，编码长度为li，电文中共有n种字符，则电文编码总长度为： 利用最优二叉树设计一种前缀编码 1）构造以 W(3)、I(4)、N(3)、E(1)、L(2) 为叶子结点的最优二叉树； 2）将该二叉树所有左分枝标记0，所有右分枝标记1； 原文为：WINNIE WILL WIN W I N E L 3 4 3 1 2 W L E I N 0 0 0 0 1 1 1 1 W:00 E:010 L:011 N:10 I: 11 3）根结点到叶子结点所经过的二进制序列为该叶子结点字符的编码。 哈夫曼编码的平均码长为： ? pi×li n i=1 哈夫曼编码 W I N E L 00 11 10 010 011 发送方：00|11|10|10|11|010|00|11|011|011|00|11|10 接收方： WINNIE WILL WIN 译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束 译码唯一 练习 某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.06, 0.28, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，利用赫夫曼树设计一种前缀编码： a: 0110 b: 10 c: 1110 d: 1111 e: 110 f: 00 g: 0111 h: 010 构造赫夫曼树—— 以字符使用频率作为权 0 1 0 1 0 1 0 1 0 1 0 1 0 1 c g a d h f e b 100 43 20 57 23 11 6 3 14 7 28 15 9 29 8 作标记——左0右1 求编码——从根到叶 具体算法如下：?? 一棵有n片叶子的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。 typedef struct { // 结点结构 unsigned int weight; unsigned int parent, lchild, rchild ; }