Huffman树及其应用
Huffman树及其应用
Huffman树 基本概念 两个结点间的路径 由一个结点到另一个结点之间的分支构成 路径长度 路径上的分支数目 树的路径长度 ·从树根到每个结点的路径长度之和 结点的带权路径长度 从该结点到树根之间的路径长度与结点上的权的乘积 树的带权路径长度 ·树中所有叶子结点的带权路径长度之和,记作WPL
Huffman树 • 基本概念 – 两个结点间的路径 • 由一个结点到另一个结点之间的分支构成 – 路径长度 • 路径上的分支数目 – 树的路径长度 • 从树根到每个结点的路径长度之和 – 结点的带权路径长度 • 从该结点到树根之间的路径长度与结点上的权的乘积 – 树的带权路径长度 • 树中所有叶子结点的带权路径长度之和，记作WPL
Huffman树 如 a WPL=7*2+5*2+2*2+4*2=36 WPL=4*2+7*3+5*3+2*1=46 bWPL=7*1+5*2+2*3+4*3=35
Huffman树 • 如 a b c d 7 5 2 4 c d 4 5 2 7 a b a b b 7 5 4 c 2 WPL = 7*2 +5*2 + 2*2 +4*2 = 36 WPL = 4*2 +7*3 + 5*3 +2*1 = 46 WPL = 7*1 + 5*2 + 2*3 +4*3 = 35
Huffman树 Huffman树 又称赫夫曼树或最优二叉树 假设有n个权值{w1,w2…,wn},试构造一棵有n各叶子结 点的二叉树,每个叶子结点带权为w,则其中带权路径 长度WPL最小的二叉树即为 Huffman树 权在不同应用中含义不同,如所占比例,出现概率等 Huffman树的应用 用于实现最佳判定算法,让概率最大的事件尽早被判定 用于通信编码,让概率大的字符对应的编码尽可能短 等等
Huffman树 • Huffman树 – 又称赫夫曼树或最优二叉树 – 假设有n个权值{w1 ,w2 ,…wn}，试构造一棵有n各叶子结 点的二叉树，每个叶子结点带权为wi，则其中带权路径 长度WPL最小的二叉树即为Huffman树 – 权在不同应用中含义不同，如所占比例，出现概率等 • Huffman树的应用 – 用于实现最佳判定算法，让概率最大的事件尽早被判定 – 用于通信编码，让概率大的字符对应的编码尽可能短 – 等等
Huffman树 如:将百分制转换为五分制 分数0~5960-6970~7980-8990~100 已知 比例数5%15%40%30%10%权 可能的判定算法:不及格优良 60>中等良刻优良 良好 优良 不及格及 格
Huffman树 如：将百分制转换为五分制 分数 0~59 60~69 70~79 80~89 90~100 比例数 5% 15% 40% 30% 10% 权 已知： 可能的判定算法： a<60 a<70 a<80 a<90 不及格 及格 中等 良好 优良 70 a 80 80 a 90 60 a 70 a<60 不及格 优良 及格 中等 良好 a<80 a<70 a<90 a<60 不及格 及格 中等 良好 优良
Huffman树 构造 Huffman树的一般规律 根据给定的n个权值{w1,w2,…wn},构成n棵二叉 树的集合F={T,T2,Tn},其中每棵二叉树T中只有 个带权为w的根结点,其左右子树均空 2)在F中选取两棵根结点的权值最小的树作为左右 子树构造一棵新的二叉树,且置新的二叉树的根结 点的权值为其左右子树上根结点的权值之和 3)在F中删除这两棵树,同时将新得到的二叉树加 入F中 重复2)和3),直到F中只含一棵树为止。此时得到的 便是 Huffman树
Huffman树 • 构造Huffman树的一般规律 – 1) 根据给定的n个权值{w1 ,w2 ,…wn}，构成n棵二叉 树的集合F={T1 ,T2 ,…Tn}，其中每棵二叉树Ti中只有 一个带权为wi的根结点，其左右子树均空 – 2) 在F中选取两棵根结点的权值最小的树作为左右 子树构造一棵新的二叉树，且置新的二叉树的根结 点的权值为其左右子树上根结点的权值之和 – 3) 在F中删除这两棵树，同时将新得到的二叉树加 入F中 – 重复2)和3)，直到F中只含一棵树为止。此时得到的 便是Huffman树
Huffman树 ·如:已知事件abcd对应的权值集合w={7,5,24},试 设计对应 Huffman树 a(b a stepl 6 c d step2 24 step 2 4 step4 4
Huffman树 • 如：已知事件a,b,c,d对应的权值集合w={7,5,2,4}，试 设计对应Huffman树 a b c d 7 5 2 4 step1 c d 2 4 6 a b 7 5 step2 a 7 c d 2 4 b 6 5 11 step3 a 7 c d 2 4 b 6 5 11 step4 18
Huffman树 ·如:已知事件 a b cdef对应的权值集合w={5,4,71911} 试设计对应 Huffman树 ⑤d(6(2dl8 e a 5 ep step2 step3 20 34 20 34 15 15 a( step4 step5 step
Huffman树 • 如：已知事件a,b,c,d,e,f对应的权值集合w={5,4,7,19,11,8}， 试设计对应Huffman树 a b c d 5 4 7 19 step1 e f 11 8 a b 5 4 9 c d 7 19 e f 11 8 step2 a b 5 4 9 c d 7 19 e f 11 8 step3 15 a b 5 4 9 c d 7 19 e f 11 8 step4 20 15 a b 5 4 9 c d 7 19 e f 11 8 step5 15 20 34 a b 5 4 9 c d 7 19 e f 11 8 step6 15 20 34 54
Huffman n树 ·如:已知某系统在通信联络中只可能出现八种字符,其概 率分别为5%,25%7%8%14%23%,3%,11%,试设计对应 Huffman树 96 或292 830959 058① ①③⑩05 ③③⑦③8 ★在人工构造比m树的过程中如果出现权值相同的情况,可能 ulman
Huffman树 • 如：已知某系统在通信联络中只可能出现八种字符，其概 率分别为5%,25%,7%,8%,14%,23%,3%,11%，试设计对应 Huffman树 3 5 8 7 8 11 15 19 14 23 29 42 25 54 96 或 3 5 7 8 15 8 11 19 14 29 23 42 25 54 96 ★在人工构造Huffman树的过程中，如果出现权值相同的情况，可能 会出现不同的结构。但若通过算法进行构造，则Huffman树唯一
Huffman树 前缀编码(又称 Huffman编码) 任一字符的编码都不是另一字符编码的前缀 如 a的编码为:0 b的编码为:100 k的编码为:101 e的编码为:11
Huffman树 • 前缀编码(又称Huffman编码) – 任一字符的编码都不是另一字符编码的前缀 – 如 a的编码为: 0 b的编码为: 100 k的编码为: 101 e的编码为: 11