证明 ·设丁是任意一个最优编码对应的树,a,b是 深度最深的一对兄弟【为什么存在?】 然后交换x、a;y、b;【见下图】 ·T'是最优编码对应的树 Q“ 清华大学們学院宋恒 清华大学软件学院宋 上图不同树的成本之差 Huffman的贪心选择律 B(T)-B(T)=∑fc4(c)-∑f(c)dr(c) ·设C是给定的字符集,f是C中元素c的频 =fx}(x)+flka)-f[x41(x)-fl}1(a) 率。设x,y是C中频率最小的两个元素。令 C=C-{xy}+{z},其中z是一个新的元素 fd,(x)+falr(a-x], (a)-fad,(x) 即z不属于C。我们在C上更新f,使得 Ga-fd,(a)-d,(x) f2]=fx]y]其它值不变。则如果T是C上 的任意一个最优前缀编码对应的树,则把z > 用一棵由x和y为叶子点的树代替而生成的 新树T是C上的一个最优编码对应的树 清华大学学院未恒 清华大学软件学院宋 证明提示 Huffman编码小结 1.树T和T编码成本关系B(TB(T)=f×]+y] ·前缀码 2.反证法,假设T不是最优编码树→ Exists 最优码的特征 T such that BT)<B), which has x and 最小频率的优化码可最长化 y are the deepest siblings, Construct T" to represents a prefix code for ·贪婪选择律 C+T"is a better coding than t,a 贪婪算法 contradiction 清华大学轼字院宋恒 消华大学软件学院宋4 清华大学软件学院宋斌恒 19 证明 •设T是任意一个最优编码对应的树，a，b是 深度最深的一对兄弟【为什么存在？】， 然后交换x、a；y、b；【见下图】 •T’’是最优编码对应的树 清华大学软件学院宋斌恒 20 y a b x y x b a a b x y 清华大学软件学院宋斌恒 21 上图不同树的成本之差 å å Î Î - = - c C T c C T B(T) B(T') f (c)d (c) f (c)d (c) ' f[x]d (x) f [a]d (a ) f [x]d (x) f[a]d (a ) = T + T - T ' - T ' ( f[a] f[x])(d (a ) d (x)) = - T - T f[x]d (x) f [a ]d (a ) f[x]d (a) f [a]d (x) = T + T - T - T ³ 0, 清华大学软件学院宋斌恒 22 Huffman的贪心选择律 •设C是给定的字符集，f[c]是C中元素c的频 率。设x，y是C中频率最小的两个元素。令 C’＝C－{x,y}+{z}，其中z是一个新的元素， 即z不属于C。我们在C’上更新f，使得 f[z]=f[x]+f[y]，其它值不变。则如果T’是C’上 的任意一个最优前缀编码对应的树，则把z 用一棵由x和y为叶子点的树代替而生成的 新树T是C上的一个最优编码对应的树。 清华大学软件学院宋斌恒 23 证明提示 1. 树T和T’编码成本关系B(T)-B(T’)=f[x]+f[y] 2. 反证法，假设T不是最优编码树Ë Exists T’’such that B(T’’)<B(T), which has x and y are the deepest siblings, Ë Construct T’’’to represents a prefix code for C’ËT’’’is a better coding than T’, a contradiction 清华大学软件学院宋斌恒 24 Huffman编码小结 •前缀码 •最优码的特征 •最小频率的优化码可最长化 •贪婪选择律 •贪婪算法