数据结构精品课件-哈夫曼编码.pptVIP

* 哈夫曼编码 在数据通信中，经常需要将传送的文字转换为二进 制字符0和1组成的二进制串，我们称这个过程为编码。 例如，假设要传送的电文为ABACCADAA，电文中只有A,B,C,D四种字符。如果在编码时考虑 字符在要传送的电文中出现的次数，让出现次 数越高的字符采用越短的编码，构造一种不等 长编码，则可使要传送的电文的代码长度最短。 等长编码：A:00 B:01 C:10 D:11 不等长编码：A:0 B:10 C:110 D:111 6.5 哈夫曼树及其应用 第 6 章 树和二叉树 * 设计不等长编码，必须保证一个字符 的编码都不是另一个字符的编码的前缀。 6.5 哈夫曼树及其应用 第 6 章 树和二叉树 哈夫曼编码 前缀编码： 任何一个字符的编码都不是同一字 符集中另一个字符的编码的前缀。 利用哈夫曼树可以构造一种不等长的二进制编码， 并且构造所得的哈夫曼编码是一种最优前缀编码， 即使所传电文的总长度最短。 哈夫曼编码: 对哈夫曼树中每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的值构成该叶子的哈夫曼编码。 例：若要传输如下单词 state, seat, act, tea, cat, set, a, eat 如何使所传送的信息编码长度最短？ 为保证信息编码长度最短，先统计各字符出现的次数，然后以此作为权值, 构造哈夫曼树。 6.5 哈夫曼树及其应用 第 6 章 树和二叉树 7 2 3 5 15 8 5 10 25 0 0 0 0 1 1 1 1 00 10 010 011 编码: 左分支:0;右分支:1； 根到叶子路径上的 值构成叶子的编码。 11 需传输信息：state, seat, act, tea, cat, set, a, eat 2 5 7 8 3 c e a t s 各字符权值： 010 00 10 11 011 c e a t s 各字符编码： 构造哈夫曼树： 结论一：哈夫曼编码是前缀码。 结论二: 哈夫曼编码是最优前缀码。 若di≠dj(字符不同)，则对应的树叶不同，因为从根到每个叶子的路径是不同的，所以一条路径不可能是另一条路径的前部（前缀），因此哈夫曼编码是前缀码。 用字符出现的频率(Pi)为权值构造哈夫曼树,并以此来构造字符的哈夫曼编码，由于哈夫曼树的WPL最小： 所以传输的报文长度： 必定最小。 WPL=?wi×li i=1 n 报文长=?Pi×li i=1 n 6.5 哈夫曼树及其应用 第 6 章 树和二叉树 * 假设某系统通信联络中只可能出现8种字符 ,其 出现概率为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11, 试设计哈夫曼编码。 例如： 设w={5,29,7,8,14,23,3,11} 5 3 8 ,8} 7 8 15 ,15} 11 19 ,19} 14 29 ,29} 23 42 ,42} 29 58 ,58} 100 ,100} 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 010 0110 0111 10 110 1110 1111 6.5 哈夫曼树及其应用 第 6 章 树和二叉树 哈夫曼编码应用举例 例：设有一台模型机，共有7种不同的指令，各指令的使用频率Pi为： 指 令 I1 I2 I3 I4 I5 I6 I7 使用频率pi 0.40 0.30 0.15 0.05 0.04 0.03 0.03 哈夫曼树最典型、最广泛的应用是在编码技术上，而操作码的优化也是其应用之一。 以指令的使用频率为权值构造哈夫曼树，并求各指令的哈夫曼编码。 6.5 哈夫曼树及其应用 第 6 章 树和二叉树 则指令的平均码长为： pi×li =0.4*7+0.3*2+0.15*3+0.05*5+0.04*5 +0.03*5+0.03*5 = 2.20 n i=1 若用等长编码，其平均码长为3。 指令 I1 I2 I3 I4 I5 I6 I7 编码 1 01 001 00011 00010 00001 00000 各指令的哈夫曼编码为： 6.5 哈夫曼树及其应用 第 6 章 树和二叉树 哈夫曼编码算法 利用哈夫曼树求编码时，编码是由后向前生成的，需要走一条从叶子到根的路径 当前结点若是其双亲的左子树时，则置当前编码位为0，否则置为1。 当由叶子走到根结点时，完成一个叶子结点编码的求取。 6.5 哈夫曼树及其应用