多媒体核心技术：压缩考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的位数位为：En=-log2(Pn)整条信息的熵也即表示整条信息所需的位数为：E=∑En举个例子，对下面这条只出现了abc三个字符的字符串：aabbaccbaa字符串长度为10，字符abc分别出现了532次，则abc在信息中出现的概率分别为0.50.30.2，他们的熵分别为：Ea=-log2(0.5)=1Eb=-log2(0.3)=1.737Ec=-log2(0.2)=2.322整条信息的熵也即表达整个字符串需要的位数为：E=Ea*5+Eb*3+Ec*2=14.855位如果用计算机中的ASCII编码，表示上面的字符串需要整整80位呢！简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。无损数据压缩概念4.1Shannon的信息论与数据压缩举例8.举例信源取4个符号a1,a2,a3,a4,概率1/2，1/4，1/8，1/8信源的熵H(x)=…=1.75bit/字符若用编码(0,10,110,111),则平均码长=…=1.75考虑以下几种变长编码：码Ｂ唯一可译例1：例4.1例2：8个字符具有等可能性例3：字符的分布已知：P=(0.9,0.02,0.02,0.02,0.01,0.01,0.01,0.01)H(p)=0.74bit/字符练习9.Huffman编码练习４.2算术编码4.3RLE编码（RunLengthEncoding）例子4.4词典编码应用范围词典编码举例词典编码举例LZ78算法LZ78编码算法LZ78编码举例LZ78译码2.LZW与LZ78相比，有如下特点所有可能出现的字符都事先放在字典中。输出的码字流中仅由词典中的码字组成。编码算法思想Greedyparsingalgorithm:检查字符流中的字符串，Prefix.C,其中Prefix是字典中最长的字符串，C是一个字符Prefix.C不在字典中。Prefix.C放入字典中。输出Prefix.C的编号例ABBABABACLZW编码算法2.LZW译码算法（略）词典中包含所有的前缀根（即每个字符组成词典）译码时先记住先前码字（pW）从码字流中读出当前的码字（cW）输出当前的码字（cW）对应的单词,string(cW)string(pW)与string(cW)的第一个字符合在一起，放入词典中。例，ABBABABAC词典中有A,B,C码字流：（1，2，2，4，7，3）练习