树的路径长学习.pptx

《树的路径长学习.pptx》由会员分享，可在线阅读，更多相关《树的路径长学习.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习目标什么是信息论中的信息？如何使用二进制编码进行表达信息？如何计算编码的信息量？为什么哈夫曼编码是最优编码？如何使用二叉树进行编码设计？常见的树结构的算法有哪些？第1页/共45页信息与信息论信息的应用非常广泛，定义在不同的领域，也有不同，例如，在管理信息系统中：Byinformationwemeandatathathavebeenshapedintoaformthatismeaningfulandusefultohumanbeings但是在计算机和通信领域：1948年，美国数学家、信息论的创始人仙农在题为“通讯的数学理论”的论文中指出：“信息是用来消除随机不定性的东西”第2页/共45页案例

2、1：灯笼报信第3页/共45页一个灯笼的故事第4页/共45页改进的报警方案第5页/共45页2的幂次和可表达的信息单元第6页/共45页灯笼的个数和信息单元的表达第7页/共45页反向思维如果知道要传送的消息个数，怎样知道需要的最少比特数?如果需要报信的内容是一年内可能发生进攻的月份，需要多少灯笼？第8页/共45页数字表达如果民兵希望发送英军中先头部队数量的消息时怎么办?假设教堂中的报信人知道英军先头部队有50个连，我们知道可以用不到50个灯笼来表达这种消息信息论告诉我们，民兵只要使用六个灯笼就可以表达英军50个连进攻的消息但要传送这个消息，哪些灯笼要打开，哪些要关闭呢?第9页/共45页用灯笼来表示5

3、0第10页/共45页字符表达假设要表达字母表中的26个字母，需要多少灯笼或比特呢?尽管看起来用5个比特已足够表达这26个字符，但是，英语中每个字母都有大小写，还有大量的标点符号、缩略语(如$、&、+)如果把这些计算在内，包括从0到9的数字，则总共有95个不同的字符需要表达第11页/共45页ASCII码表第12页/共45页熵与信息量著名的美国数学家ClaudeShannon在1948年定义“熵”来表达消息的信息量消息的信息量是一个非常有意思的概念，取决于我们对此消息已知的内容有时，我们只要问一个问题，就消除了再问的必要性，这种情况下，消息所含的信息量就很低第13页/共45页猜、猜、猜如果你的朋友

4、问你：“猜猜我今天是怎么到学校的?”，你一定可以很容易的一下猜到,骑车而如果他是坐直升飞机来的?而如果他是坐宇宙飞船来的?猜测次数的多少，意味着“信息不确定性”的程度，越是难猜的信息，包含的信息值越大第14页/共45页07之间数字的猜测过程第15页/共45页哪支球队是冠军可以把球队编上号，从1到32,猜/答一次,付钱一元然后提问：“冠军的球队在1-16号中吗?”假如他告诉我猜对了我会接着问：“冠军在1-8号中吗?”假如他告诉我猜错了，我自然知道冠军队在9-16中这样只需要五次，我就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信息量只值五块钱第16页/共45页如何少猜几次信息量使用比特数

5、计量并和所有可能情况的对数函数log有关log232=5log264=6（64支参赛队）实际上象巴西、德国、意大利这样的球队得冠军的可能性比日本、美国、韩国等队大的多因此，当每个球队夺冠的可能性（概率）不等时，“谁世界杯冠军”的信息量实际比五比特少第17页/共45页实际上的信息量香农指出，它的准确信息量应该是：-（p1logp1+p2logp2+p32logp32)其中，p1，p2，p32分别是这32个球队夺冠的概率香农把它称为“信息熵”(Entropy)，一般用符号H表示，单位是比特第18页/共45页硬币的抛掷测试假设一条消息出现的概率为p,那么其信息量就是log2p比特如果出现的正面的概率

6、为1/2，那么其信息量就是-log21/2=1比特如果因为重心等原因，出现的正面的概率为1，那么信息量就成了-log21=0比特第19页/共45页熵的定义设随机变量X，取值空间，为有限集合；X的分布密度为p(x)，p(x)=P(X=x)，xX，则该随机变量的取值不确定程度，即其熵为：当使用log2时，熵的单位为比特反映一个信源发出不同信号，具有的平均信息量第20页/共45页利用信息论进行编码分析（1）计算英文字符（26字母加空格）为信息源的熵：设所有字符等概率出现：H(X)=-p(x)log2p(x)xX=27*-1/27log21/27=log227=4.75(bits/Letter)第21

7、页/共45页利用信息论进行编码分析(2)假设英文字符的概率分布如下表：解：H(X)=-p(xi)log2p(xi)i=1274.02(bits/Letter)说明：考虑英文字符和空格实际出现的概率后，英文信源的平均不确定性，比把字符和空格看作等概率的情况要小第22页/共45页利用熵求最优编码的问题有一个池塘里，有时非常平静，有时有青蛙叫，有时有蛤蟆叫，有时青蛙和蛤蟆一起叫，池塘的声响状态服从以下分布：请定时记录池塘的声响状态，并编码发送。如何编码，可以使编码最短？池塘状态池塘状态平静平静青蛙叫青蛙叫蛤蟆叫蛤蟆叫青蛙和蛤蟆叫青蛙和蛤蟆叫概率0.50.1250.1250.25第23页/共45页利用

8、熵求最优编码定长编码，需要两个二进制位；变长编码：给小概率消息较长的编码，给大小概率消息较短的编码；因为，随机变量X服从概率分布P时，如果消息x的分布密度为p（x）,则给其分配一个长度为-log2p(x)个二进制位的编码则发送一个消息平均需要-p(x)log2p(x)个二进制位所以，有变长的编码规则如下：第24页/共45页利用熵求最优编码(3)消息消息编码编码平静平静0青蛙叫青蛙叫110蛤蟆叫蛤蟆叫111青蛙和蛤蟆一起叫青蛙和蛤蟆一起叫10编码的平均长度为：-p(x)log2p(x)=0.5*1+0.125*3+0.125*3+0.25*2 =1.75比特第25页/共45页基于有序频率二叉树编

9、码 1951年哈夫曼和他在MIT信息论课程的同学需要选择是完成学期报告还是期末考试；导师RobertM.Fano给他们的学期报告的题目是，寻找最有效的二进制编码最终发现了基于有序频率二叉树（也称为最优二叉树）编码的想法第26页/共45页最优二叉树概念1树的路径长度从树根到树中每一节点的路径长度之和2树的带权路径长度(Weighted Path Length of Tree，WPL)节点的权：在一些应用中，赋予树中节点的一个有某种意义的实数(例如编码值)节点的带权路径长度：节点到树根之间的路径长度与该节点上权的乘积第27页/共45页最优二叉树概念树的带权路径长度：定义为树中所有叶节点的带权路径长

10、度之和，通常记为：其中：n表示叶子节点的数目 wi和li分别表示叶节点ki的权值和根到节点ki之间的路径长度 树的带权路径长度亦称为树的代价 第28页/共45页最优二叉树或哈夫曼树在权为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第29页/共45页构造构造Huffman树树l）将信号源的符号按照出现概率递减的顺序排列2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率3

11、）重复进行步骤1和2直到概率相加的结果等于1为止4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码第30页/共45页例6-5：请编制哈夫曼编码 一串信号源SZ，K，F，C，U，D，L，E对应频率为p2，7，24，32，37，42，42，120第31页/共45页例6-5：请编制哈夫曼编码E=0U=100D=101L=110C=1110Z=111100K=111101F=11111 每一码不会是另一码的前缀，每一码不会是另一码的前缀，每一码不会是另一码的前缀，每一码不会是另一码的前缀，译码时可惟一复原译码

12、时可惟一复原译码时可惟一复原译码时可惟一复原 第32页/共45页使用RAPTOR产生哈夫曼编码 1、编码的数据的准备：基本数据，通过文件(code_frequence.csv)输入给算法，并按以下字母、频率对的形式排列：“Z，2，K，7，F，24，C，32，U，37，D，42，L，42，E，120”第33页/共45页使用RAPTOR产生哈夫曼编码2、主要数据结构：使用binlist数组保存带权二叉树元素序号123456作用节点名左子右子代码频率父节点作为叶子的8个节点在代码字段，具有原始代码的值，其他节点则没有；所有叶子节点的左子，右子字段为空，用“0”表示第34页/共45页哈夫曼编码main

13、子图第35页/共45页主要子图和子程序Init子图：binlist、asslist数组初始化，从文件读入编码需要的基本数据；Build_huffman_tree子图：使用哈夫曼编码的原理，进行建立带权二叉树；Twochild子图：找出当前新建节点的两个子节点Findmin子图：用于寻找当前asslist中保存的最小权重的节点；Incode子程序：用于带权二叉树建立完成后，进行各个原始码的二进制编码的编制；Output子图：用于最终的编码输出。第36页/共45页Init子图第37页/共45页Build_huffman_tree子图第38页/共45页Twochild子图第39页/共45页Findmin子图寻找当前asslist中保存的最小权重的节点第40页/共45页Incode子程序完成各个原始码的二进制编码的编制第41页/共45页Output子图第42页/共45页编码结果第43页/共45页End of ch6-1第44页/共45页感谢您的观看！第45页/共45页