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