lecture4无损数据压缩

lecture4无损数据压缩

ID:42780625

大小:195.50 KB

页数:16页

时间:2019-09-22

lecture4无损数据压缩_第1页
lecture4无损数据压缩_第2页
lecture4无损数据压缩_第3页
lecture4无损数据压缩_第4页
lecture4无损数据压缩_第5页
资源描述:

《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考虑以下几种变长编码:码B唯一可译例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码Ca11/2000a21/411010a31/811110101a41/81111111114.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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。