哈夫曼编码 带权路径长度 假设二叉树中每个叶结点有一个权值w;到根的路 径长度为1,其他结点权值为0,则有n个叶子结点 的树的带权路径长度为wPL=∑甲* i=0 2氵g9 WPL=2(2+4+5+7)=36WPL=2+24+3*(5+7)=46WPL=7+25+3+4+2)=35 带权路径长度达到最小的二叉树即为 Huffman树。 在 Huffman树中,权值越大的结点离根越近。 11
哈夫曼编码 ◼ 带权路径长度 假设二叉树中每个叶结点有一个权值wi，到根的路 径长度为l i，其他结点权值为0，则有n个叶子结点 的树的带权路径长度为 11 = = -1 0 n i i i WPL w l 2 4 5 7 2 5 7 4 7 4 2 5 WPL=2*(2+4+5+7)=36 WPL=2+2*4+3*(5+7)=46 WPL=7+2*5+3*(4+2)=35 带权路径长度达到最小的二叉树即为Huffman树。 在Huffman树中，权值越大的结点离根越近
哈夫曼编码 ■构造权值为Ww1W2…,wWn}的 Huffman树 口构造n棵二叉树的森林F={T1T2…,T},每棵二叉 树T只有一个带权值为W的根结点 口重复以下步骤,直到只剩一棵树为止 >1.在F中选两棵根结点权值最小的二叉树,作为左、 右子树构造一棵新的二叉树,新树的根结点权值等于 其左、右子树根结点权值之和 >2在F中删除这两棵二叉树 >3.把新构造的二叉树加入F 12
哈夫曼编码 ◼ 构造权值为{w1 ,w2 , …, wn }的Huffman树 构造n棵二叉树的森林F={T1 ,T2 , …, Tn }，每棵二叉 树Ti只有一个带权值为wi的根结点 重复以下步骤，直到只剩一棵树为止： ➢ 1. 在F中选两棵根结点权值最小的二叉树，作为左、 右子树构造一棵新的二叉树，新树的根结点权值等于 其左、右子树根结点权值之和 ➢ 2. 在F中删除这两棵二叉树 ➢ 3. 把新构造的二叉树加入F 12
哈夫曼编码 F:{7}{5}{2}{4} F:{75}{6} F:{7}11 F:{18} 团图回(回⑩ 四四 214 (a)初始 (b)合并{24 (b)合并{2{4} (b)合并11 13
哈夫曼编码 13 F: {7} {5} {2} {4} 7 5 2 4 (a) 初始 F: {7} {5} {6} (b) 合并{2}{4} F: {7} {11} (b) 合并{2}{4} F: {18} (b) 合并{7}{11} 7 5 6 2 4 6 7 5 2 4 11 6 7 5 2 4 11 18
哈夫曼编码 Huffman编码,进行数据压缩 口计算机领域数据用二进制表示 若已统计出某文本中各字符出现的概率,可以用 Huffman编码进行数据压缩 概率=某字符出现次数 总字符数 14
哈夫曼编码 ◼ Huffman编码，进行数据压缩 计算机领域数据用二进制表示 若已统计出某文本中各字符出现的概率，可以用 Huffman编码进行数据压缩 14 总字符数 概率 = 某字符出现次数
哈夫曼编码 Huffman编码,进行数据压缩 假设某文本共有1000个字符,且只由a,b,c,d,e 5种字符组成 固定长度编码可将每个字符用3比特表示,整个文本 要3*1000=3000比特表示,平均编码长度3比特 符号 定长编码 a 001 100 cde 101 110 15
哈夫曼编码 ◼ Huffman编码，进行数据压缩 假设某文本共有1000个字符，且只由 a, b, c, d, e 5种字符组成 ➢ 固定长度编码可将每个字符用3比特表示，整个文本 要3*1000=3000比特表示，平均编码长度3比特 15 符号 定长编码 a 000 b 001 c 100 d 101 e 110