算法设计与分析课件 6.5.2-贪心法应用-哈夫曼编码-算法正确性证明

上传人：y*** IP属地：山东上传时间：2024-11-10 格式：PPTX 页数：6 大小：252.64KB 积分：7.2 举报 版权申诉

已阅读5页，还剩1页未读，继续免费阅读

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

信息工程大学算法设计与分析贪心法--哈夫曼算法的正确性证明国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版定理：Huffman算法对任意规模为n（n2）的字符集C都能得到关于C的最优前缀码的二叉树。

该定理的证明需要两个引理。则T与T’的WPL之差为其中dT(i)为i在T中的层数（i到根的距离）,引理1成立。引理1：设C是字符集，

C,f(c)为频率，x,y

C,f(x),f(y)频率最小，那么存在最优二元前缀码使得x,y的编码长度相等，且仅在最后一位不同。f(x)

f(a)f(y)

f(b)a与x交换b与y交换

TT’yabxTbxyaT’证明:设T是C的最优前缀树，且a和b是具有最大深度的两个兄弟字符:引理2：设T是最优二元前缀码所对应的二叉树，

x,y

T,x,y是树叶兄弟，z是x,y的父亲，令T’=T

{x,y},且令z的频率f(z)=f(x)+f(y)，T’是对应于二元前缀码C’=(C

{x,y})

{z}的二叉树，那么WPL(T)=WPL

(T’)+f(x)+f(y)。bczT’0011f(c)f(b)f(x)+f(y)bcxyT000111f(x)f(c)f(y)f(b)z定理：Huffman算法对任意规模为n（n2）的字符集C都能得到关于C的最优前缀码的二叉树。

归纳基础

n=2，字符集C={x1,x2}，Huffman算法得到的编码是0和1，是最优前缀码。归纳步骤

假设Huffman算法对于规模为k的字符集能得到最优前缀码。考虑规模为k+1的字符集C={x1,x2,...,xk+1},其中x1,x2

C是频率最小的两个字符。

令

C’=(C－{x1,x2})

{z}，

f(z)=f(x1)+f(x2)根据归纳假设，Huffman算法得到一棵关于字符集C’、频率f(z)和f(xi)（i=3,4,...,k+1）的最优前缀码的二叉树T’。把x1和x2作为z的儿子附加到T’上，得到树T，那么T是关于字符集C=(C’－{z})

{x1,x2}的最优前缀码的二叉树。

zT’x2x1T

zx1T*x2T*‘

z如若不然，存在更优的树T*。根据引理1，其最深层树叶是x1,

x2，且WPL(T*)<WPL(T)。去掉T*中的x1和x2，根据引理2，所得二叉树T*’满足WPL(T*’)＝WPL(T*)－(f(x1)+f(x2))<WPL(T)－

人人文库> 全部分类> 教育资料 > 课件下载

1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

算法设计与分析 课件 6.5.2-贪心法应用-哈夫曼编码-算法正确性证明