四川大学多媒体课件3.pptVIP

四、无损压缩LosslessCompression编码:把每个符号“翻译”成一个二进制码（binarycodeword）每个二进制码可以不同长度，目标是平均码长最小。减少平均码长的基本思路:出现次数多的符号翻译成较短二进制码；出现次数少的符号翻译成较长二进制码morefrequentlysymbols?shortercodewordslessfrequentlysymbols?longercodewords熵:符号i在信息源中出现的概率l(i):符号i的二进制码长度平均码长L=∑iN=1p(i)l(i)熵熵的定义(Entropy):熵是信息源平均信息量，是信息源的特性当所有符号概率相等时，熵的最大值为log2N；当符号概率相差大时，熵的值较小。冗余量: ∑iN=1p(i)l(i)-H最优码:冗余量最小的编码编码符号的平均二进制码长度≥信息源的熵（entropyH）(熵是最小平均码长)熵{0.25,0.25,0.25,0.25}{1,0,0,0}熵假定:某些符号出现概率比其他符号大例:N=8symbols:{a,b,c,d,e,f,g,h},3bitspersymbol(N=23=8)P(a)=0.01P(b)=0.02P(c)=0.05P(d)=0.09P(e)=0.18P(f)=0.2P(g)=0.2P(h)=0.25HuffmancodingHuffmancoding平均代码长度(编码前):熵:平均代码长度(Huffmancoding):Shannon-Fanocoding符号出现的次数分配的代码需要的位数A15(0.375)1.41500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5(0.125)3.000011115Shannon-FanocodingShannon-Fano算法步骤:Step1:将源符号及其概率按非增次序排列；Step2:将符号分成概率和最接近的两组（各1/2），第1组以0开始编码，第2组以1开始编码；Step3:每组重复Step2，在已有编码后按规则追加0/1，直到每个组只有一个符号时，算法终止。优点:简单；不保证最优；H+1≥平均码长≥HShannon-FanocodingHuffmancoding例1S-FHuffmana10.35001a20.1701011a30.1710010a40.16110001a50.15111000平均码长2.312.30Huffmancoding静态Huffman编码算法步骤:Step1:以每个源符号的概率为权，组成N个只有根节点的二叉树的集合；Step2:将2个权值最小的二叉树wi和wj,合并成一个根为wi+wj,的二叉树，其左、右子树分别为wi和wj,，将wi+wj插入到集合中，并将wi和wj从集合中删除；Step3:重复Step2，直到集合只有一个权值；Step4:从根到每一叶子节点（源符号）路径上（左0右1）的字符串即为该符号的编码。评价:最优码（最小冗余）Shannon-FanocodingHuffmancoding例2:“aabbbccccdddddeeeeeefffffffgggggggg”Shannon-FanocodingHuffmancoding

例2:“aabbbccccdddddeeeeeefffffffgggggggg”H=2.894(116)S-F(117)Huffman(117)g8/400000f7/40010110e6/40011111d5/40100010space5/40101101c4/40110011b3/4011101000a2/4011111001数据压缩的模型建立建立模型（modeling）:给消息源中每一符号指定概率建立模型的方式: 静态的(static):对所有信息源使用同一模型；