资源描述：
《lecture4无损数据压缩》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章无损数据压缩方式：无损有损无损，losslesscompression,redundancyreduction压缩后的数据能够完全恢复，如磁盘上的数据文件，压缩后是原来的1/2—1/4算法有：Huffman,RLE,算术编码，词典编码有损：lossy,不可逆压缩。声音、图像中的变换编码，例如，DPCM(图3-14）由于存在量化器4.1Shannon的信息论与数据压缩1.Astory：Europe，Albert,patentauditor主要申请：任意英文文件，压缩到10个字母一个bit。Claude:破坏了信息论的数据压缩理
2、论极限。1948年Shannon创立的信息论：数据压缩理论极限。数据压缩的技术途径。压缩原理：信源中信息分布不均匀；信源中信息含有冗余（相关性）2.信息熵entropy问题：随机变量的一个取值a，携带的信息量是多少？相关概念：消息：数据、电报、电话。信息：对信息加工，有特定价值一个信息带有一定的信息量，大小不等例子一个消息：某试验成功试验人员预计成功的可能性99%：信息量很小试验人员预计成功的可能性1%：信息量很大3.信息量答案：在收到信息以前，处于某种不确定状态中，收到信息之后，消除或部分消除了此不确定性。消除不确定性多少，就可
3、以作为信息的度量。4.Shannon用概率说明这一概念事件出现的概率小，相当于不确定性多，反之，则少。P为事件的概率，对应的不确定性为h(p)=-logp5.信息熵（Entrop）表示每出现一个字符所给出的平均信息量。6.信息熵的理解：处于事件发生之前，根据先验概率Pj,就有不同的确定性存在，h(Pj)与H(x)都是不确定性度量。当处于事件发生之时，是一种惊奇性的度量但出于事件发生之后，不确定性已被解除，则是获得信息的度量可以认为是事件随机性的度量，因其仅仅对概率Pj取另个坐标而已。7.H(x)就是对离散信源进行无失真编码时的码长
4、极限。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/字符信源字母概率码A码B码Ca1１／２０００a2１／４１１０１０a3１／８１１１１０１０１a4１／８１１１１１１１１１４.2算术编码提出Ri
5、ssanen1976年提出。在JPEG与JBIG（Bi-levelimage)中都有算术编码的内容。2.思想把信源符号构成的串S,唯一地映射到实数轴上（0，1）之间的一个实数。前提：知道信源每个符号的概率。3.举例假设信源由四个符号{a1,a2,a3,a4}组成，这些符号的概率分别是（0.1,0.4,0.2,0.3).a1,a2,a3,a4四个符号的二进制编码分别为00，01，10，11符号序列S=a3a1a4a1a3a4a2的二进制序列为10001100101101编码：把S映射到（0，1）之间的实数的过程,见图4-3译码:见教
6、案。4.3RLE编码RLE原理：图像（静止图像）的相邻像素相关性（灰度、彩色）。用二元组（行程，灰度或彩色值）表示。2.举例图4-53.不足：随机的图像，平均码长增加。4.4词典编码思想Huffman编码：符号的概率已知，概率大的符号分配较短的码字。而实际上不太现实。将长度不同的符号串（短语）编码成一个个新的单词。每个符号串分配一个编码。编码等长（如12位二进制）。2.提出：以色列J.Ziv与A.Lempel,LZ77,LZ78,1984,T.A.Welch提出LZW,在Unix中应用。词典编码举例LZ78编码思想：不断从字符流中
7、形成新的缀—符串，缀—符串作为新的词条存入字典中，并给该词条分配一个码字。对字符流的编码就用“(缀的编码,符)”表示，实现压缩。举例：表4-13,字符流为：ABBCBCABALZ78编码举例字符流词典与码字流（输出）位置字符1A2B3B4C5B6C7A8B9A序号位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)问题为什么不直接输出词条的序号？LZ78算法术语字符流字符码字流码字前缀缀—符串词典：缀—符串、码字构成的对应表编码算法译码算法2.LZW与LZ78相比，有如下特点所有可能
8、出现的字符都事先放在字典中。输出的码字流中仅由词典中的码字组成。编码算法例4.7译码算法p59
