5,2哈夫曼树与哈夫曼编码

2020-03-16 68浏览

  • 1.5.2 哈夫曼树与哈夫曼编码
  • 2.什么是哈夫曼树（Huffman Tree） [例] 将百分制的考试成绩转换成五分制的成绩 if( score < 60 ) grade =1; else if( score < 70 ) grade =2; else if( score < 80 ) grade =3; else if( score < 90 ) grade =4; else grade =5;  判定树: yes grade=1 score<60 yes grade=2 no score<70 yes grade=3 no score<80 yes grade=4 no score<90 no grade=5
  • 3. 如果考虑学生成绩的分布的概率： 分数段 0-59 60-69 70-79 80-89 90-100 比例 0.05 0.15 0.40 0.30 0.10  查找效率：0.05× 1+0.15 ×2+0.4× 3+0.3 ×4+0.1× 4 yes grade=1 score<60 yes grade=2 no score<70 yes grade=3 no score<80 yes grade=4 no score<90 no grade=5 = 3.15
  • 4. 如果考虑学生成绩的分布的概率： 分数段 0-59 60-69 70-79 80-89 90-100 比例 0.05 0.15 0.40 0.30 0.10  修改判定树： yes score<80 no yes score<70 no yes score<60 no grade=1 grade=3 yes score<90 no grade=4 grade=2 效率: 0.05× 3+0.15 ×3+0.4× 2+0.3 ×2+0.1× 2 = 2.2 grade=5 if( score < 80 ) { if( score < 70 ) if( score < 60 ) grade =1; else grade = 2; }else if( score < 90 ) grade =4; else grade =5; 如何根据结点不同的查找频率构造更有效的搜索树？
  • 5. 哈夫曼树的定义 带权路径长度(WPL)：设二叉树有n个叶子结点，每个叶子结点带 有权值 wk，从根结点到每个叶子结点的长度为 lk，则每个叶子结 n 点的带权路径长度之和就是： WPL  w l  k 1 k k 最优二叉树或哈夫曼树: WPL最小的二叉树
  • 6.〖例〗有五个叶子结点，它们的权值为{1,2,3,4,5}，用此权值序列 可以构造出形状不同的多个二叉树。 5 1 4 2 3 1 3 2 5 WPL ＝ 34 4 WPL ＝ 50 3 1 4 2 WPL ＝ 33 WPL ＝ 5×1＋4×2＋3×3＋2×4＋1×4＝ 34 WPL WPL＝1×1＋2×2＋3×3＋4×4＋5×4＝ ＝1×3＋2×3＋3×2＋4×2＋5×2＝50 33 5
  • 7.哈夫曼树的构造  每次把权值最小的两棵二叉树合并 15 1 3 26 3 3 1 49 5 6 3 2 3 1 3 2
  • 8.typedef struct TreeNode *HuffmanTree; struct TreeNode{ int Weight; HuffmanTree Left, Right; } HuffmanTree Huffman( MinHeap H ) { /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */ int i; HuffmanTree T; BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/ for (i = 1; i < H->Size; i++) { /*做H->Size-1次合并*/ T = malloc( sizeof( struct TreeNode) ); /*建立新结点*/ T->Left = DeleteMin(H); /*从最小堆中删除一个结点，作为新T的左子结点*/ T->Right = DeleteMin(H); /*从最小堆中删除一个结点，作为新T的右子结点*/ T->Weight = T->Left->Weight+T->Right->Weight; /*计算新权值*/ Insert( H, T ); /*将新T插入最小堆*/ } T = DeleteMin(H); 整体复杂度为O(N logN) return T; }
  • 9. 哈夫曼树的特点:     没有度为1的结点； n个叶子结点的哈夫曼树共有2n-1个结点； 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树； 对同一组权值{w1 ,w2 , …… , wn}，是否存在不同构的两 棵哈夫曼树呢？ 对一组权值{ 1, 2 , 3, 3 }，不同构的两棵哈夫曼树： 3 3 1 1 2 3 3 2 WPL ＝ 18 WPL ＝ 18
  • 10.哈夫曼编码  给定一段字符串，如何对字符进行编码，可以使得该字符串的编码 存储空间最少？ [例] 假设有一段文本，包含58个字符，并由以下7个字符构：a，e，i， s，t，空格（sp），换行（nl）；这7个字符出现的次数不同。如何对 这7个字符进行编码，使得总编码空间最少？ 【分析】 （1）用等长ASCII编码：58 ×8 = 464位； （2）用等长3位编码：58 ×3 = 174位； （3）不等长编码：出现频率高的字符用的编码短些，出现频率低 的字符则可以编码长些？
  • 11.怎么进行不等长编码？ 如何避免二义性？ 前缀码prefix code：任何字符的编码都不是另一字符编码的前缀  可以无二义地解码
  • 12.二叉树用于编码 用二叉树进行编码： （1）左右分支：0、1 （2）字符只在叶结点上 1 1 0 0 四个字符的频率:a:4,u:1,x:2,z:1a 0 0 a 1 u x 0 u 1 z 1 0 x 1 z Cost ( aaaxuaxz  00010110010111) = 14 + 31 + 22 + 31 = 14 Cost ( aaaxuaxz  0000001001001011) = 24 + 21 + 22 + 21 = 16 怎么构造一颗编码代价最小的二叉树？
  • 13.〖例〗哈夫曼编码 t nl a 4 10 1 0 t 25 4 0 i 12 Ci fi a 10 e 15 i 12 s 3 t 4 sp 13 nl 1 e e sp ai : 111 a a sp 4 a i e e s sp t sp nl i 8 18 25 15 3315 18 13 e 10 : 10 25 15 10 13 12 15 312 1215 10 15 3 13 4 13 12 1 1 i : 00 nl sa sa : 11011 i sp sp e 4i 8 1 33 3 10 8 18 12 13 12 13 15 10 t : 1100 1 0 1 sp : 01 nl t s sp e t 8 418 nl : 11010 4 a 1 4 3 13 15 4 10 0 1 nl sat nl 4 s 8 1 310 4 1 3 = 310 + 215 Cost 0 1 + 212 + 53 t nl s + 44 + 213 4 4 1 3 + 51 1 0 = 146 nl s i e e12 s i 58 1 3