ch8--成绩统哈夫曼树.pptVIP

8.6 哈夫曼树（Huffman Tree） 哈夫曼树 – Huffman Tree 又叫最优二叉树 Huffman 1952 年提出。 8.6.1 哈夫曼树基本概念 1. 引言 【例】考试成绩转换 90~100：—— A 　 80~89 ：—— B 　 70~79 ：—— C 　 60~69 ：—— D 　 0~59 ：—— E 　 假设个分数段的分布如下， A：5% 500份 B：15% 1500份 C：30% 3000份 D: 35% 3500份 E: 15% 1500份 求3个判断流程的次数。 【解】 流程一的判断次数： 500×1＋1500×2＋3000×3＋3500×4＋1500×4 ＝32500次 流程二的判断次数： 500×4＋1500×4＋3000×3＋3500×2＋1500×1＝25500次 流程三的判断次数： 500×3＋1500×3＋3000×2＋3500×2＋1500×2＝22000次 结论：选择不同的求解次序造成比较/判断次数的差异。 2. 几个概念 (1) 路径 从一个结点到另一个结点所经过的结点和边。 (2) 路径长度 路径上的边数。 (3) 节点的带权路径长度 结点到树根的路径长度和结点权值的乘积。 (4) 树的带权路径长度 树中所有叶子结点的带权路径长度之和。 设有 n 个叶子结点，wi 为第 i 个叶子结点的权值，Li 为第 i 个叶子结点的路径长度，树的带权路径长度记作： 3.哈夫曼树的定义 给定一组数值{w1，w2,…,wn}作为叶子结点的权值，构造一棵二叉树。 若二叉树满足：WPL 为最小（其中Li为wi对应的叶子结点到根结点的路径长度），则称此二叉树为最优二叉树，也称哈夫曼树，并称WPL为带权路径长度。 8.6.2 哈夫曼树的构造 对给定的 w={w1，w2,…,wn}，以此作为叶子结点的权值,如何构造哈夫曼树？ 构造方法： 根据给定的n个权值 w={w1，w2,…,wn}，构成 n 棵二叉树的集合 T={T1,T2,…,Tn}，其中每个 Ti 只有一个权值为 wi 的根结点，其左右子 树均空。 从T中选两棵根结点权值最小的二叉树（不妨设为 T1、T2 ），作为左右子树构成一棵新二叉树 T1’，并置新二叉树 T1’的根的权值为其左右子树（即T1、T2 ）的根结点的权值之和。 将新二叉树 T1’并入到 T 中，同时从 T中删除T1、T2 。 重复①、②，直到 T 中只有一棵树为止。这棵树便是哈夫曼树。 【例】以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造哈夫曼树，并计算其带权路径长度。 【解】 按构造算法，首先将这些数变成单结点的二叉树集合： 8.6.3 哈夫曼编码 压缩编码（节省存储空间） 报文的编码、译码 将报文的字符进行二进制编码、译码 等长编码 对每个字符作长度相等的编码。 例：报文 “ABAACCBADCA”，有四个不同字符，可用 2 位(bit)二进制编码，如： A-00、B-01、C-10、D-11，则编码后的电文为： “0001000010100100111000”，总长为 22 位； 译码时，从左往右，每 2位(bit)为进行翻译，只要有编码字典，即可译出原文。 不等长编码 对字符采用不等长的编码 比如上例中可以分别采用 1 位和 2 位编码，0、1、00、01； 为减少总码长度，容易想到，出现频率高的字符采用短的编码，频度低的字符采用长的编码，如上例中 A、C 出现的频度高，进行下列编码： A--0、B--00、C--1、D--01，则编码后电文为： “00000110000110”，码长为 14 位，比等长编码短。 但是，不等长编码在译码时，存在歧义解释问题： 上例中，接收方在收到 “00000” 时，既可以译为 “AAAAA”，也可译为 “ABB”、或 “BAB”、或 “BAAA” 等等。 怎么解决这个问题呢 – 前缀编码 前缀编码 不等长编码，任一个编码不是另一个编码的前缀。即：短编码不能是任何长编码的前缀。 前缀编码可以保证译码的唯一性。 哈夫曼编码（一种前缀压缩编码） 设电文使用了 n 个不同字符； 统计电文中各种字符 ( n 种 ) 出现的次数（频率）； 用这 n 个字符作为根结点，出现的次数（频率）作为权值，构成 n 棵二叉树（只有根结点）； 用这 n 棵二叉树，构造一棵哈夫曼树； 哈夫曼树中，所有左分支对应的边（结点到其左孩子的边）上标记‘0’，右分支对应的边（结点到其右孩子的边）上标记 ‘1’；（反之亦可） 从根结点到每个叶子结点，经过边的