《树的路径长学习教案.pptx》由会员分享，可在线阅读，更多相关《树的路径长学习教案.pptx（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1树的路径树的路径(ljng)长长第一页，共45页。学习学习(xux)目标目标n n什么是信息论中的信息？n n如何使用二进制编码进行(jnxng)表达信息？n n如何计算编码的信息量？n n为什么哈夫曼编码是最优编码？n n如何使用二叉树进行(jnxng)编码设计？n n常见的树结构的算法有哪些？第1页/共45页第二页，共45页。信息信息(xnx)与信息与信息(xnx)论论n n信息的应用非常广泛，定义在不同的领域，也有不同，例如，在管理信息系统中：n nBy information we mean data that have been shaped into a form that
2、 is meaningful and useful to human beingsn n但是在计算机和通信领域：n n1948年，美国数学家、信息论的创始人仙农在题为“通讯的数学理论”的论文(lnwn)中指出：“信息是用来消除随机不定性的东西”第2页/共45页第三页，共45页。案例案例(n l)1：灯笼报信：灯笼报信第3页/共45页第四页，共45页。一个灯笼一个灯笼(dng long)的故事的故事第4页/共45页第五页，共45页。改进改进(gijn)的报警方案的报警方案第5页/共45页第六页，共45页。2的幂次和可表达的信息的幂次和可表达的信息(xnx)单单元元第6页/共45页第七页，共45页
3、。灯笼的个数和信息单元灯笼的个数和信息单元(dnyun)的表达的表达第7页/共45页第八页，共45页。反向反向(fn xin)思维思维n n如果知道如果知道(zh do)要传送的消息个数，怎要传送的消息个数，怎样知道样知道(zh do)需要的最少比特数需要的最少比特数?n n如果需要报信的内容是一年内可能发生进攻如果需要报信的内容是一年内可能发生进攻的月份，需要多少灯笼？的月份，需要多少灯笼？第8页/共45页第九页，共45页。数字数字(shz)表达表达n n如果民兵如果民兵(mnbng)希望发送英军中先头部希望发送英军中先头部队数量的消息时怎么办队数量的消息时怎么办?n n假设教堂中的报信人知
4、道英军先头部队有假设教堂中的报信人知道英军先头部队有50个连，我们知道可以用不到个连，我们知道可以用不到50个灯笼来表达个灯笼来表达这种消息这种消息n n信息论告诉我们，民兵信息论告诉我们，民兵(mnbng)只要使用只要使用六个灯笼就可以表达英军六个灯笼就可以表达英军50个连进攻的消息个连进攻的消息n n但要传送这个消息，哪些灯笼要打开，哪些但要传送这个消息，哪些灯笼要打开，哪些要关闭呢要关闭呢?第9页/共45页第十页，共45页。用灯笼用灯笼(dng long)来表示来表示50第10页/共45页第十一页，共45页。字符字符(z f)表达表达n n假设要表达字母表中的26个字母，需要多少灯笼或比
5、特呢?n n尽管看起来用5个比特已足够(zgu)表达这26个字符，但是，英语中每个字母都有大小写，还有大量的标点符号、缩略语(如$、&、+)n n如果把这些计算在内，包括从0到9的数字，则总共有95个不同的字符需要表达第11页/共45页第十二页，共45页。ASCII码表码表第12页/共45页第十三页，共45页。熵与信息量熵与信息量n n著名的美国数学家Claude Shannon在1948年定义“熵”来表达消息(xio xi)的信息量n n消息(xio xi)的信息量是一个非常有意思的概念，取决于我们对此消息(xio xi)已知的内容n n有时，我们只要问一个问题，就消除了再问的必要性，这种情
6、况下，消息(xio xi)所含的信息量就很低第13页/共45页第十四页，共45页。猜、猜、猜猜、猜、猜n n如果你的朋友问你：“猜猜我今天是怎么到学校的?”，n n你一定可以很容易的一下猜到,骑车n n而如果他是坐直升飞机(zh shn fi j)来的?n n而如果他是坐宇宙飞船来的?n n猜测次数的多少，意味着“信息不确定性”的程度，越是难猜的信息，包含的信息值越大第14页/共45页第十五页，共45页。07之间数字之间数字(shz)的猜测过程的猜测过程第15页/共45页第十六页，共45页。哪支球队哪支球队(qi du)是冠军是冠军n n可以(ky)把球队编上号，从1到32,猜/答一次,付钱一
7、元n n然后提问：“冠军的球队在1-16号中吗?”假如他告诉我猜对了n n我会接着问：“冠军在1-8号中吗?”假如他告诉我猜错了，我自然知道冠军队在9-16中n n这样只需要五次，我就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信息量只值五块钱第16页/共45页第十七页，共45页。如何如何(rh)少猜几次少猜几次n n信息量使用比特数计量并和所有可能情况的对数函数信息量使用比特数计量并和所有可能情况的对数函数loglog有关有关n nlog2 32=5log2 32=5n nlog2 64=6log2 64=6（6464支参赛队）支参赛队）n n实际上象巴西、德国、意大利这样的球队得冠
8、军的可能性比日本、实际上象巴西、德国、意大利这样的球队得冠军的可能性比日本、美国美国(mi(mi u)u)、韩国等队大的多、韩国等队大的多n n因此，当每个球队夺冠的可能性（概率）不等时，因此，当每个球队夺冠的可能性（概率）不等时，“谁世界杯冠谁世界杯冠军军”的信息量实际比五比特少的信息量实际比五比特少第17页/共45页第十八页，共45页。实际上的信息量实际上的信息量n n香农指出，它的准确(zhnqu)信息量应该是：n n-（p1log p1+p2 log p2+p32log p32)n n其中，p1，p2，p32 分别是这32个球队夺冠的概率n n香农把它称为“信息熵”(Entropy)，
9、一般用符号H表示，单位是比特第18页/共45页第十九页，共45页。硬币的抛掷硬币的抛掷(pozh)测试测试n n假设一条消息(xio xi)出现的概率为p,那么其信息量就是 log2 p比特n n如果出现的正面的概率为1/2，那么其信息量就是-log2 1/2=1比特n n如果因为重心等原因，出现的正面的概率为1，那么信息量就成了-log2 1=0比特第19页/共45页第二十页，共45页。熵的定义熵的定义(dngy)n n设随机变量X，取值空间，为有限集合；X的分布密度为p(x)，p(x)=P(X=x)，xX，则该随机变量的取值不确定程度，即其熵为：n n当使用log2时，熵的单位为比特n n
10、反映一个信源发出不同(b tn)信号，具有的平均信息量第20页/共45页第二十一页，共45页。利用信息论进行编码利用信息论进行编码(bin m)分析（分析（1）n n计算英文字符（26字母加空格(kn)）为信息源的熵：n n设所有字符等概率出现：H(X)=-p(x)log2p(x)xX =27*-1/27log21/27 =log227 =4.75(bits/Letter)第21页/共45页第二十二页，共45页。利用信息论进行利用信息论进行(jnxng)编码编码分析分析(2)假设假设(ji(ji sh)sh)英文字符的概率分布如下表：英文字符的概率分布如下表：解：解：H(X)=-p(xi)lo
11、g2p(xi)i=127 H(X)=-p(xi)log2p(xi)i=127 4.02(bits/Letter)4.02(bits/Letter)说明：考虑英文字符和空格实际出现的概率后，英文信说明：考虑英文字符和空格实际出现的概率后，英文信源的平均不确定性，比把字符和空格看作等概率的情况源的平均不确定性，比把字符和空格看作等概率的情况要小要小第22页/共45页第二十三页，共45页。利用利用(lyng)熵求最优编码的问熵求最优编码的问题题n n有一个池塘里，有时非常平静，有时有青蛙叫，有时有蛤蟆叫，有时青蛙和蛤蟆一起叫，池塘的声响状态服从以下分布：n n请定时记录池塘的声响状态，并编码(bin
12、 m)发送。如何编码(bin m)，可以使编码(bin m)最短？池塘状态池塘状态平静平静青蛙叫青蛙叫蛤蟆叫蛤蟆叫青蛙和蛤蟆叫青蛙和蛤蟆叫概率0.50.1250.1250.25第23页/共45页第二十四页，共45页。利用利用(lyng)熵求最优编码熵求最优编码n n定长编码，需要两个二进制位；n n变长编码：给小概率消息较长的编码，给大小概率消息较短的编码；n n因为，随机变量 X服从概率分布P时，如果消息x的分布密度为p（x）,则给其分配一个长度为-log2p(x)个二进制位的编码n n则发送一个消息平均需要-p(x)log2p(x)个二进制位n n所以，有变长的编码规则(guz)如下：第2
13、4页/共45页第二十五页，共45页。利用利用(lyng)熵求最优熵求最优编码编码(3)消息消息编码编码平静平静0青蛙叫青蛙叫110蛤蟆叫蛤蟆叫111青蛙和蛤蟆一起叫青蛙和蛤蟆一起叫10编码的平均长度(chngd)为：-p(x)log2p(x)=0.5*1+0.125*3+0.125*3+0.25*2 =1.75比特第25页/共45页第二十六页，共45页。基于基于(jy)有序频率二叉树编码有序频率二叉树编码 n n1951年哈夫曼和他在MIT信息论课程的同学(tng xu)需要选择是完成学期报告还是期末考试；n n导师Robert M.Fano给他们的学期报告的题目是，寻找最有效的二进制编码 n
14、 n最终发现了基于有序频率二叉树（也称为最优二叉树）编码的想法 第26页/共45页第二十七页，共45页。最优二叉树概念最优二叉树概念(ginin)n n1树的路径长度树的路径长度n n从树根到树中每一节点的路径长度之和从树根到树中每一节点的路径长度之和n n2树的带权路径长度树的带权路径长度(Weighted Path Length of Tree，WPL)n n节点的权：在一些应用节点的权：在一些应用(yngyng)中，赋予中，赋予树中节点的一个有某种意义的实数树中节点的一个有某种意义的实数(例如编例如编码值码值)n n节点的带权路径长度：节点到树根之间的路节点的带权路径长度：节点到树根之间
15、的路径长度与该节点上权的乘积径长度与该节点上权的乘积第27页/共45页第二十八页，共45页。最优二叉树概念最优二叉树概念(ginin)n n树的带权路径长度：定义为树中所有叶节点(ji din)的带权路径长度之和，通常记为：其中：n表示叶子节点(ji din)的数目 wi和li分别表示叶节点(ji din)ki的权值和根到节点(ji din)ki之间的路径长度 树的带权路径长度亦称为树的代价 第28页/共45页第二十九页，共45页。最优二叉树或哈夫曼树最优二叉树或哈夫曼树n n在权为wl，w2，wn的n个叶子所构成(guchng)的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二
16、叉树(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=46(c)WPL=7*1+5*2+2*3+4*3=35第29页/共45页第三十页，共45页。构造构造(guzo)Huffman(guzo)Huffman树树n nl l）将信号源的符号按照出现概率递减）将信号源的符号按照出现概率递减）将信号源的符号按照出现概率递减）将信号源的符号按照出现概率递减(dji(dji n)n)的顺序排列的顺序排列的顺序排列的顺序排列2 2）将最下面的两个）将最下面的两个）将最下面的两个）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率最小出现概率
17、进行合并相加，得到的结果作为新符号的出现概率最小出现概率进行合并相加，得到的结果作为新符号的出现概率最小出现概率进行合并相加，得到的结果作为新符号的出现概率n n3 3）重复进行步骤）重复进行步骤）重复进行步骤）重复进行步骤1 1和和和和2 2直到概率相加的结果等于直到概率相加的结果等于直到概率相加的结果等于直到概率相加的结果等于1 1为止为止为止为止n n4 4）在合并运算时，概率大的符号用编码）在合并运算时，概率大的符号用编码）在合并运算时，概率大的符号用编码）在合并运算时，概率大的符号用编码0 0表示，概率小的符号用编码表示，概率小的符号用编码表示，概率小的符号用编码表示，概率小的符号用
18、编码1 1表示表示表示表示n n5 5）记录下概率为）记录下概率为）记录下概率为）记录下概率为1 1处到当前信号源符号之间的处到当前信号源符号之间的处到当前信号源符号之间的处到当前信号源符号之间的0 0，l l序列，从而得到每个符号的序列，从而得到每个符号的序列，从而得到每个符号的序列，从而得到每个符号的编码编码编码编码第30页/共45页第三十一页，共45页。例例6-5：请编制：请编制(binzh)哈夫曼哈夫曼编码编码 n n一串信号源SZ，K，F，C，U，D，L，E对应(duyng)频率为p2，7，24，32，37，42，42，120第31页/共45页第三十二页，共45页。例例6-5：请编制
19、：请编制(binzh)哈夫曼哈夫曼编码编码n nE=0n nU=100n nD=101n nL=110n nC=1110n nZ=111100n nK=111101n nF=11111 每一码不会是另一码的前缀每一码不会是另一码的前缀每一码不会是另一码的前缀每一码不会是另一码的前缀(qinzhu)(qinzhu)，译码时可惟一译码时可惟一译码时可惟一译码时可惟一复原复原复原复原 第32页/共45页第三十三页，共45页。使用使用RAPTOR产生产生(chnshng)哈夫曼编码哈夫曼编码 n n1、编码的数据的准备：基本数据，通过文、编码的数据的准备：基本数据，通过文件件(code_frequen
20、ce.csv)输入给算法，并按输入给算法，并按以下字母以下字母(zm)、频率对的形式排列：、频率对的形式排列：n n“Z，2，K，7，F，24，C，32，U，37，D，42，L，42，E，120”第33页/共45页第三十四页，共45页。使用使用(shyng)RAPTOR产生哈夫产生哈夫曼编码曼编码n n2 2、主要数据结构：、主要数据结构：、主要数据结构：、主要数据结构：n n使用使用使用使用(sh(sh yng)binlistyng)binlist数组保存带权二叉树数组保存带权二叉树数组保存带权二叉树数组保存带权二叉树元素序号123456作用节点名左子右子代码频率父节点作为叶子的作为叶子的8
21、个节点在代码字段，具有原始代码的值，其他个节点在代码字段，具有原始代码的值，其他(qt)节点则没有；节点则没有；所有叶子节点的左子，右子字段为空，用所有叶子节点的左子，右子字段为空，用“0”表示表示第34页/共45页第三十五页，共45页。哈夫曼编码哈夫曼编码(bin m)main子图子图第35页/共45页第三十六页，共45页。主要主要(zhyo)子图和子程序子图和子程序n nInitInit子图：子图：binlistbinlist、asslistasslist数组初始化，从文件读入编码需要的基本数据；数组初始化，从文件读入编码需要的基本数据；n nBuild_huffman_treeBuild
22、_huffman_tree子图：子图：使用哈夫曼编码的原理，进行建立带权二叉树；使用哈夫曼编码的原理，进行建立带权二叉树；n nTwochildTwochild子图：找出当前新建节点的两个子节点子图：找出当前新建节点的两个子节点n nFindminFindmin子图：用于寻找当前子图：用于寻找当前asslistasslist中保存的最小权重的节点；中保存的最小权重的节点；n nIncodeIncode子程序：用于带权二叉树建立完成后，进行各个原始码的二进制编码子程序：用于带权二叉树建立完成后，进行各个原始码的二进制编码的编制的编制(binzh)(binzh)；n nOutputOutput子图
23、：用于最终的编码输出。子图：用于最终的编码输出。第36页/共45页第三十七页，共45页。Init子图子图第37页/共45页第三十八页，共45页。Build_huffman_treeBuild_huffman_tree子图子图子图子图第38页/共45页第三十九页，共45页。Twochild子图子图第39页/共45页第四十页，共45页。Findmin子图子图寻找当前寻找当前(dngqin)asslist中保存的最中保存的最小权重的节点小权重的节点第40页/共45页第四十一页，共45页。Incode子程序子程序完成各个完成各个(gg)原始码的二进制编码的编制原始码的二进制编码的编制第41页/共45页第四十二页，共45页。Output子图子图第42页/共45页第四十三页，共45页。编码编码(bin m)结果结果第43页/共45页第四十四页，共45页。End of ch6-1第44页/共45页第四十五页，共45页。