《可视化计算》第6章信息论、哈夫曼编码与二叉树 (A).ppt

1、第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年，美国数学家

2、、信息论的创始人仙农在题为“通讯的数学理论”的论文中指出：“信息是用来消除随机不定性的东西”,3,案例1：灯笼报信,4,一个灯笼的故事,5,改进的报警方案,6,2的幂次和可表达的信息单元,7,灯笼的个数和信息单元的表达,8,反向思维,如果知道要传送的消息个数，怎样知道需要的最少比特数? 如果需要报信的内容是一年内可能发生进攻的月份，需要多少灯笼？,9,数字表达,如果民兵希望发送英军中先头部队数量的消息时怎么办? 假设教堂中的报信人知道英军先头部队有50个连，我们知道可以用不到50个灯笼来表达这种消息 信息论告诉我们，民兵只要使用六个灯笼就可以表达英军50个连进攻的消息 但要传送这个消息，哪些灯

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

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

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

6、息量就是 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/

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

8、小概率消息较长的编码，给大小概率消息较短的编码； 因为，随机变量 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给他们的学期报告的题目是，寻找最有效的二

9、进制编码 最终发现了基于有序频率二叉树（也称为最优二叉树）编码的想法,27,最优二叉树概念,1树的路径长度 从树根到树中每一节点的路径长度之和 2树的带权路径长度(Weighted Path Length of Tree，WPL) 节点的权：在一些应用中，赋予树中节点的一个有某种意义的实数(例如编码值) 节点的带权路径长度：节点到树根之间的路径长度与该节点上权的乘积,28,最优二叉树概念,树的带权路径长度：定义为树中所有叶节点的带权路径长度之和，通常记为：,其中： n表示叶子节点的数目 wi和li分别表示叶节点ki的权值和根到节点ki之间的路径长度 树的带权路径长度亦称为树的代价,29,最优二

10、叉树或哈夫曼树,在权为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序

11、列，从而得到每个符号的编码,31,例6-5：请编制哈夫曼编码,一串信号源SZ， K， F， C， U， D， L， E对应频率为p2，7，24，32，37，42，42，120,32,例6-5：请编制哈夫曼编码,E=0 U=100 D=101 L=110 C=1110 Z=111100 K=111101 F=11111,每一码不会是另一码的前缀， 译码时可惟一复原,33,使用RAPTOR产生哈夫曼编码,1、编码的数据的准备：基本数据，通过文件(code_frequence.csv)输入给算法，并按以下字母、频率对的形式排列： “Z， 2，K， 7，F， 24，C， 32，U，37，D， 42，L

12、，42，E， 120”,34,使用RAPTOR产生哈夫曼编码,2、主要数据结构： 使用binlist数组保存带权二叉树,作为叶子的8个节点在代码字段，具有原始代码的值，其他节点则没有； 所有叶子节点的左子，右子字段为空，用“0”表示,35,哈夫曼编码main子图,36,主要子图和子程序,Init子图：binlist、asslist数组初始化，从文件读入编码需要的基本数据； Build_huffman_tree子图： 使用哈夫曼编码的原理，进行建立带权二叉树； Twochild子图：找出当前新建节点的两个子节点 Findmin子图：用于寻找当前asslist中保存的最小权重的节点； Incode子程序：用于带权二叉树建立完成后，进