课程教学目标 针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程中加以介绍。 课程内容安排 本课程的内容分成两大部分：算法的基础知识、通用算法设计技术与分析方法。 第一部分是算法基础知识，约占20%，主要介绍算法相关的基本概念和数学基础。比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。 第二部分是通用的算法设计技术与分析方法，主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。
057最优前缀码及哈夫曼算法
Loading...
Do curso por Peking University
算法设计与分析 Design and Analysis of Algorithms
34 classificações
Na lição
贪心算法的典型应用
给出了贪心法应用的一些成功案例，如与最优前缀码设计有关的哈夫曼算法、应用广泛的最小生成树Prim算法和Kruskal算法、在网络路由中寻找单源最短路径的Dijkstra算法等。
Conheça os instrutores
Wanling QuProfessor
School of EECS, Peking University
这一讲介绍最优前缀码。首先我们先看看什么叫二元前缀码。
用0-1字符串作为代码来表示字符，
要求任何字符的代码都不能作为其他字符代码的前缀。
这样的设计就叫做二元前缀码。
这里是一个非前缀码的例子，一共有4个字符a,b,c,d，
假定我们用这样的01串来代表这个四个字符的代码，
那么这里边00就是001的前缀， 01就是010的前缀，它不满足前缀码的要求。
那么像这样的代码在解码的时候就会出错，
比如说我们考察一个字符串，是0100001这个字符串，
如果你解码的话，可能会出现歧义，我们可以这样地解码，
把01看作一个字符，00看作一个字符，001看作一个字符，
那这个解码的结果呢就是d,b,a，把它解码成d,b,a了。
那么也有另外的解码方法， 把010看作第一个字符，00第二个字符，01看作第三个字符，
这个解码结果呢就是c,b,d，所以这就出现了歧义。
前缀码在解码的时候不会出现这样的问题， 因此我们在设计代码的时候，要求用前缀码。
下面我们看一下前缀码的表示， 前缀码呢可以表示成一棵二叉树。
这是一个前缀码的例子， 一共有这样多个代码，
那么把这些个代码呢表达在一棵树上， 这棵树向左边走就表示0，向右边走就是1，
所以我们看它的每一步向左都是一个0，向右都是一个1，
那么这个00000就是都是向左，5步向左，
那这个呢就是0000向右1，所以 我们可以把这些个代码都标记在这棵树上，
那么最后的代码在这棵树上就是树叶， 这些个树叶都是代码，这个就是二元前缀码
它的二叉树表示。每一个前缀码都可以对应这样一棵二叉树。
我们看一下它的平均传输位数。这是一棵
二元前缀码的二叉树，那么这些个是它的编码，编码的字符串，
出现的频率都写在这个字符串上面，5,5,10,15,25,10,10,20
大家的频率可能是不一样的。
那么它的传输位数，平均的传输位数怎么算呢？可以这样算， 就是用它的频率乘以它的
码的长度，那这个码的长度在这棵树上正好代表了树的深度，
你比如说我这个码的长度是5，5个0，那么
这棵树的深度是0，这是1,2,3,4,5，正好5条边，从
根到它的路径长度就是深度了。所以这个码的位数就是树的深度，因此
用这个码在树上的深度，乘以它的频率，
对所有的这样的码求和，就是它的平均传输位数。这是这个传输位数的公式。
那么对这个具体的例子，我们可以计算一下，
这两个码它的频率
是5，这个5是指的百分之五了，是吧？两个都是百分之五，乘以它的位数是5，
然后我们看到对于这个码，它是四位， 10%，10X4，然后这三个码
这个码，这个码，这个码，这都是三位的。
这个是15%，10%，10%，就是这一项。
然后这两个是两位的，两位的是 25%，25%，乘以2位，大家
最后把这个整数都除以100%，就是它的频率了。
这个算出来平均的传输位数是2.85， 这是它的这个平均传输位数的定义。
然后我们看看我们的问题是给定一个字符集，
和每个字符的频率，希望你设计一个
最优的前缀码，就是使得这个平均传输位数达到最小的这样的一个前缀码。
这个是它的算法，就是哈弗曼算法。
这棵树对应的最优二元前缀码的树叫哈弗曼树。
这个做法就是每次选择两个频率最小的
作为兄弟，然后把它们合并成一个父结点，
这个父结点的频率恰好等于这两个最小的频率之和。
通过这样合并以后，就在队列中产生一个它的父结点，
它的两个儿子就是两个最小的频率的那个字符。
然我们就在这个队列中 不断地找两个最小的合并，合并以后把它从队列删除，把它的父结点插入到队列中去。
做到最后，这队列只剩下一个结点的时候， 这个整个的数就生成了。因此这是它的
伪码，我们先生成一个空结点作为它的父结点，
生成好了以后，把两个最小的元素，就是频率最低的
两个元素，一个作为这个父结点的左儿子，一个作为右儿子，
然后把父结点的频率表达成这两个儿子的频率之和，
把这个父结点插入到对列中去，所以每次这个队列会减少一个元素。
那它最后剩一个元素的时候，这个树就生成了。
下边看一个具体的例子。这个是输入的字符，
一共是6个字符，那么这些个45， 13,12,16,9和5就是代表它的频率，
用这个数除以100，就是45%， 13%等等，那就是代表它的频率，我们用整数来
来做算法。那这就是开始的这些个字符，
下边标记的就是代表它频率的那些个整数。
按照哈弗曼算法，应该选两个最小的来合并，那就是5和9，
这两个合并以后，生成一个父结点，那这个频率是5和9的和，就是14，
下边再选两个最小的是12和13，这两个是最小的，
然后把它合并，合并生成一个25， 然后再选两个最小的
就是14和16合并，生成30，然后30,25跟45
再选两个小的，就是30和25合并，55 ，
最后这两个再合并，就是 频率就达到100%。这是整棵树的生成。
那么这棵树生成以后，它的代码是什么呢？根据刚才我们的规定，这个f就是4个0，
这个e就是0001，这个d c,b,a都可以把它们对应的代码写出来。
这就是这个算法的结果。那么它的平均 传输位数呢按照我们的公式来计算，
这两个是 频率是5%和9%，然后它是4位长的，
然后这个3位长的就是这几个代码，3位长的，这是它们的频率。
然后乘以它们的位数，然后这边还有一个1位长的，
这个算出来是2.24，这是得到的一个
二元前缀码，也是最优的，就是按照哈弗曼算法算的。
下边我们介绍两个最优前缀码的性质，
这是为了证明算法的正确性来使用的。第一个 引理，有一个字符集C，
每个字符有一个频率，x,y是其中频率是最小的两个字符，
这是它的频率f(x)和f(y)，一定存在着一棵最优的二元前缀码，
这个二元前缀码它x,y是等长，意味着它们在树上正好是兄弟，
它仅在最后一位不同，就是它是在兄弟的位置。
那么这个证明的方法我们可以这样证，假定这是
一个最优前缀码的一棵树T，
那么这里边x,y它并不是兄弟，也没有
处在一个合适的位置，但是它是频率最小的，比如说x
的频率也小于等于a的频率，这个a和b是一对兄弟，
它是处在它的下层，那么y频率小于等于b的频率。
就是它们两个虽然频率最小，但是它们不是兄弟，也没有放在这一层上。
下边我们就把这个x和a替换一下， 把y和b替换一下，把x，y放在最下层，作为兄弟，
就得到这样一棵树。替换完以后得到的树是T‘，
我们就来看一看替换完了以后这棵树的
它所计算的那个权值，就是它的平均的那个位数， 和这棵树相比是降低了还是增高了。
如果它的位数是降低了，那说明我这样做了以后，这棵树的
平均传输位数更好，如果这个是最优解的话，那这个 肯定是最优解。所以我们通过这样的论证就可以说明
这个引理的正确性。下边我们就来看看这两个的平均传输位数，也叫做它们的权值，
就是这棵树的权值和这棵树的权值，到底谁的更大？
我们可以看到这棵树的权值是B(T)，这棵树的权值是B(T')，
那么就把这棵树的每个 字符，就是树叶，树叶的它的深度
乘以它的频率来求和。
那么这是第二棵树，它的深度乘以频率来求和，
除了这四个叶结点以外，这两棵树可能还有其他的叶结点，
其他的叶结点的这两个部分是相同的，在两棵树的权值
是一样的，我们就不管它了。那么只有这四个结点的权值会有变化，
因此我们可以代入这个公式，把这四项的值
代入这个公式，把这四项的值代入这个公式， 利用这个x的深度等于这个a的深度，
这个a的深度在这里边等于x的深度， 这个y的深度在这里边等于b的深度，
这个b的深度在这里边等于y的深度，利用这个深度值相等， 把这四项代进去，化简，
化简以后最终的结果可以发现这个的权值要大于等于这个的权值。
这个化简过程呢大家可以在下面做一下。
所以通过这个化简的过程，我们可以看到 这棵树的权值不比这棵树的权值大，它也是一棵最优的
二元前缀码的树。这是它的证明思想。
这是第1个引理。第2个引理呢， 就是说T是二元前缀码的一棵二叉树，
其中有两个，x,y两个字符它是树叶，
是在这样的一个结构，它有一个父亲，它们是兄弟，
这个就是z，z是它的父亲。下面我在这棵树中把这两个树叶去掉，
去掉后，把这个父亲z作为叶结点， 这是新的这样一棵树，叫T’。那么这棵树和这棵树就是
T‘是由T通过这样的操作导出来的，
那么这两个权值有什么差别呢？这两个权值的差别正好就是
x和y的频率之和，就是这是它的权值的差别。
这是第二个结果，那这个结果怎么做呢？我们可以通过下面的办法来证明。
这是说对于其他的结点，
除了x,y以外其他结点，在第一棵树的
深度乘以它的频率，和它在第二棵树的深度乘以频率，这个值 是相等的，因为它没有变化，在两棵树是完全一样的。
那么在第一棵树的x的深度
和y的深度刚好是第二棵树它的父结点z的深度加1，
这是根据我们导出的结果，z是它的父亲嘛，正好深度
比它小1。下边我们看一看这第一棵树的权值， 每个结点的深度乘以它的频率求和，
把这个权值，我们把它按照结点分成几部分， 这是除了x，y，其他的结点的部分，
就是在这个和式中，除了x，y的其他结点部分， 这是x的结点的部分，这是y结点的部分。
刚好加起来就是所有结点的和，正好这是第一个和。
那么根据第一个公式，第二棵树的 除了x,y的其他的叶结点，跟第一棵树的这个值是一样的，
所以我们直接把这一部分，它没有x,y，就是其他的结点 替换成第二棵树的这个值，因为这两个值是完全一样的。
这是它的这个结果。
然后我们看到剩下的这个部分。
剩下的这个部分呢，它的这个dT(y) dT(x)，就是这两项
它正好可以替换成它的父结点的深度加1， 所以我们把这一项替换成父结点深度加1，这项替换成父结点深度加1，
然后把这个父结点的这个深度部分提出来，把那个加1的部分 就变成它两项的和了。
所以这一部分是加1那一部分提炼出来的，剩下关于 z的那部分都在前面这一项，正好
f(x)加上f(y)就等于f(z)，我们就替换成 f(z)，所以经过这样一整理后就变成这样一个公式了。
那么这是第二棵树，除了z以外的其他的叶结点， 加上这个z这个叶结点，所以这两项合并到一起，就是
第二棵树的整个的权值，因此就差了后边这一项。
这就证明了我们的公式，就是B(T)等于B(T')加上这两个的和。
这是这个引理2的证明。我们把这一讲小结一下， 二元前缀码和它的二叉树表示。
二元前缀码是一个什么定义？
它的二叉树是怎么得到的？它们有着什么样的对应关系？这是第一个点。
第二点呢，就是给定频率下的平均传输位数的计算公式，
这个公式是用每一个字符的位数乘以它的频率求和，
字符的位数正好在树上就是用深度来表示，这是它的计算公式。
第三个什么叫最优的前缀码。就是 平均传输位数最少的那个前缀码是最优的。
那么找到最优前缀码的算法，就是哈弗曼算法。
最后我们介绍前缀码的性质，通过这个性质
来证明哈弗曼算法的正确性，这个证明将放在下一讲来加以介绍。
这一讲内容就介绍到这里。
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
