树的路径长度课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,章,信息论、哈夫曼编码与二叉树,PART A,可视化计算,学习目标,什么是信息论中的信息？,如何使用二进制编码进行表达信息？,如何计算编码的信息量？,为什么哈夫曼编码是最优编码？,如何使用二叉树进行编码设计？,常见的树结构的算法有哪些？,信息与信息论,信息的应用非常广泛，定义在不同的领域，也有不同，例如，在管理信息系统中：,By information,we mean data that have been shaped into a form that is meaningful and useful to human beings,但是在计算机和通信领域：,1948年，美国数学家、信息论的创始人仙农在题为“通讯的数学理论”的论文中指出：“,信息是用来消除随机不定性的东西,”,案例,1,：灯笼报信,一个灯笼的故事,改进的报警方案,2,的幂次,和可表达的信息单元,灯笼的个数和信息单元的表达,反向思维,如果知道要传送的消息个数，怎样知道需要的最少比特数,?,如果需要报信的内容是一年内可能发生进攻的月份，需要多少灯笼？,数字表达,如果民兵希望发送英军中先头部队数量的消息时怎么办,?,假设教堂中的报信人知道英军先头部队有,50,个连，我们知道可以用不到,50,个灯笼来表达这种消息,信息论告诉我们，民兵只要使用六个灯笼就可以表达英军,50,个连进攻的消息,但要传送这个消息，哪些灯笼要打开，哪些要关闭呢,?,用灯笼来表示,50,字符表达,假设要表达字母表中的,26,个字母，需要多少灯笼或比特呢,?,尽管看起来用,5,个比特已足够表达这,26,个字符，但是，英语中每个字母都有大小写，还有大量的标点符号、缩略语,(,如,$,、,、,、,&,、,+),如果把这些计算在内，包括从,0,到,9,的数字，则总共有,95,个不同的字符需要表达,ASCII,码表,熵与信息量,著名的美国数学家,Claude Shannon,在,1948,年定义“熵”来表达消息的信息量,消息的信息量是一个非常有意思的概念，取决于我们对此消息已知的内容,有时，我们只要问一个问题，就消除了再问的必要性，这种情况下，消息所含的信息量就很低,猜、猜、猜,如果你的朋友问你：“猜猜我今天是怎么到学校的,?,”，,你一定可以很容易的一下猜到,骑车,而如果他是坐直升飞机来的,?,而如果他是坐宇宙飞船来的,?,猜测次数的多少，意味着“信息不确定性”的程度，越是难猜的信息，包含的信息值越大,07,之间数字的猜测过程,哪支球队是冠军,可以把球队编上号，从,1,到,32,猜,/,答一次,付钱一元,然后提问：“冠军的球队在,1-16,号中吗,?”,假如他告诉我猜对了,我会接着问：“冠军在,1-8,号中吗,?”,假如他告诉我猜错了，我自然知道冠军队在,9-16,中,这样只需要五次，我就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信息量只值五块钱,如何少猜几次,信息量,使用,比特数,计量,并,和所有可能情况的对数函数,log,有关,log,2,32=5,log,2,64=6,（,64,支参赛队）,实际上象巴西、德国、意大利这样的球队得冠军的可能性比日本、美国、韩国等队大的多,因此，当每个球队夺冠的可能性（概率）不等时，“谁世界杯冠军”的信息量实际比五比特少,实际上的信息量,香农指出，它的准确信息量应该是：,-,（,p1,log p1+p2,log p2+,p32,log p32),其中，,p1,，,p2,，,p32,分别是这,32,个球队夺冠的概率,香农把它称为“信息熵”,(,Entropy,),，一般用符号,H,表示，单位是比特,硬币的抛掷测试,假设一条消息出现的概率为,p,那么其信息量就是,log,2,p,比特,如果出现的正面的概率为,1/2,，那么其信息量就是,-log,2,1/2=1,比特,如果因为重心等原因，出现的正面的概率为,1,，那么信息量就成了,-log,2,1=0,比特,熵的定义,设随机变量,X,，取值空间，为有限集合,；,X,的分布密度为,p(x),，,p(x)=P(X=x),，,x,X,，则该随机变量的取值不确定程度，即其熵为：,当使用,log,2,时，熵的单位为比特,反映一个信源发出不同信号，具有的平均信息量,利用信息论进行编码分析,（,1,）,计算英文字符（,26,字母加空格）,为,信息源的熵,：,设所有字符,等概率出现：,H(X)=-,p(x)log,2,p(x)x,X =27*-1/27log,2,1/27 =log,2,27 =,4.75(bits/Letter),利用信息论进行编码分析,(2),假设,英文字符,的概率分布如下表：,解：,H(X)=-,p(x,i,)log,2,p(x,i,)i=127,4.02(bits/Letter),说明：考虑英文字符和空格实际出现的概率后，英文信源的平均不确定性，比把字符和空格看作等概率的情况要小,利用熵求最优编码,的问题,有一个池塘里，有时非常平静，有时有青蛙叫，有时有蛤蟆叫，有时青蛙和蛤蟆一起叫，池塘的声响状态服从以下分布：,请定时记录池塘的声响状态，并编码发送。如何编码，可以使编码最短？,池塘状态,平静,青蛙叫,蛤蟆叫,青蛙和蛤蟆叫,概率,0.5,0.125,0.125,0.25,利用熵求最优编码,定长编码，需要,两个二进制位,；,变长编码：给小概率消息较长的编码，给大小概率消息较短的编码；,因为，随机变量,X,服从概率分布,P,时，如果消息,x,的分布密度为,p,（,x,）,则给其分配一个长度为,-log,2,p(x),个二进制位的编码,则发送一个消息平均需要,-,p(x)log,2,p(x),个二进制位,所以，有变长的编码规则如下：,利用熵求最优编码,(3),消息,编码,平静,0,青蛙叫,110,蛤蟆叫,111,青蛙和蛤蟆一起叫,10,编码的平均长度为：,-,p(x)log,2,p(x)=0.5*1+0.125*3+0.125*3+0.25*2,=,1.75,比特,基于有序频率二叉树编码,1951年哈夫曼和他在MIT信息论课程的同学需要选择是完成学期报告还是期末考试；,导师Robert M.Fano给他们的学期报告的题目是，寻找最有效的二进制编码,最终发现了基于有序频率二叉树（也称为最优二叉树）编码的想法,最优二叉树概念,1,树的路径长度,从树根到树中每一节点的路径长度之和,2,树的带权路径长度,(Weighted Path Length of Tree,，,WPL),节点的权：在一些应用中，赋予树中节点的一个有某种意义的实数,(,例如编码值,),节点的带权路径长度：节点到树根之间的路径长度与该节点上权的乘积,最优二叉树概念,树的带权路径长度：定义为树中所有叶节点的带权路径长度之和，通常记为：,其中：,n,表示叶子节点的数目,wi,和,li,分别表示叶节点,ki,的权值和根到节点,ki,之间的路径长度,树的带权路径长度亦称为树的代价,最优二叉树或哈夫曼树,在权为,wl,，,w2,，,，,wn,的,n,个叶子所构成的所有二叉树中，带权路径长度最小,(,即代价最小,),的二叉树称为,最优二叉树,(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,构造,Huffman,树,l,）将信号源的符号按照出现概率递减的顺序排列,2,）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率,3,）重复进行步骤,1,和,2,直到概率相加的结果等于,1,为止,4,）在合并运算时，概率大的符号用编码,0,表示，概率小的符号用编码,1,表示,5,）记录下概率为,1,处到当前信号源符号之间的,0,，,l,序列，从而得到每个符号的编码,例6-5：请编制哈夫曼编码,一串信号源SZ，K，F，C，U，D，L，E对应频率为p2，7，24，32，37，42，42，120,例6-5：请编制哈夫曼编码,E=0,U=100,D=101,L=110,C=1110,Z=111100,K=111101,F=11111,每一码不会是另一码的前缀，译码时可惟一复原,使用RAPTOR产生哈夫曼编码,1,、编码的数据的准备：,基本数据，通过文件,(code_frequence.csv),输入给算法，并按以下字母、频率对的形式排列：,“,Z,，,2,，,K,，,7,，,F,，,24,，,C,，,32,，,U,，,37,，,D,，,42,，,L,，,42,，,E,，,120”,使用RAPTOR产生哈夫曼编码,2,、主要数据结构：,使用,binlist,数组保存带权二叉树,元素序号,1,2,3,4,5,6,作用,节点名,左子,右子,代码,频率,父节点,作为叶子的,8,个节点在代码字段，具有原始代码的值，其他节点则没有；,所有叶子节点的左子，右子字段为空，用“,0”,表示,哈夫曼编码main子图,主要子图和子程序,Init,子图：,binlist,、,asslist,数组初始化，从文件读入编码需要的基本数据；,Build_huffman_tree,子图：使用哈夫曼编码的原理，进行建立带权二叉树；,Twochild,子图：找出当前新建节点的两个子节点,Findmin,子图：用于寻找当前,asslist,中保存的最小权重的节点；,Incode,子程序：用于带权二叉树建立完成后，进行各个原始码的二进制编码的编制；,Output,子图：用于最终的编码输出。,Init,子图,Build_huffman_tree,子图,Twochild,子图,Findmin,子图,寻找当前,asslist,中保存的最小权重的节点,Incode,子程序,完成各个原始码的二进制编码的编制,Output,子图,编码结果,End of ch6-1,