无损数据压缩

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