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%权 可能的判定算法:<70a80 中等 8a90 60 良好<60×a≤70 不及格 a<80 <a<60及格 及格<a<80 中等<a90>不及格优良 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 不及格 及格 中等 良好 优良