数据压缩第4章 统计编码之二_sxq2.ppt

《数据压缩第4章 统计编码之二_sxq2.ppt》由会员分享，可在线阅读，更多相关《数据压缩第4章 统计编码之二_sxq2.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1基本原理基本原理2霍夫曼编码霍夫曼编码 3游程编码游程编码 4算术编码算术编码 本章内容本章内容5基于字典的编码基于字典的编码 6哥伦布编码哥伦布编码 4.3 算术编码算术编码(Arithmetic Coding)：和霍夫曼编码和游程编码不同，算术编码跳出分组编码的范畴,从全序列出发,采用递推形式的连续编码。不是将单个信源符号映射成一个码字,而是将整个输入符号序列映射为实数轴上0,1)区间内的一个小区间,其长度等于该序列的概率,再在该小区间选择一个代表性的二进制小数,作为实际的编码输出。无论是否是二元信源，也不论数据的概率分布如何，算术编码可以二进制小数表示，其平均码长可以接近无损压缩的熵极

2、限。因此：算术编码的发展历史：1960年，P.Elias首先提出把这种依附Shannon编码概念推广到对符号序列直接编码上，推出了所谓的算术编码（Arithmetic Coding）；1948年，Shannon提出将信源依其概率降序排序,用符号序列累积概率的二进制表示对信源的编码;1976年,R.Pasco和J.Rissanen 分别用定长的寄存器实现了有限精度的算术编码;1979年,Rissanen 和G.G.Langdon将算术编码系统化，并于1981年将AC推广应用到二值图像编码上,大大提高了起压缩效率；1987年,Witten等人发表了一个实用的算术编码程序(CACM87,后用于H.2

3、63);同期IBM公司发表了著名的Q-编码器(后用于JPEG和JPIG);设一个信源，它有两个符号a和b，出现的概率分别是p和1p，设有一个基准区域0，1，对它进行划分，以便与信源输出序列相对应。abp1aabap1p+p(1-p)bbabaabap2bbab图A 符号序列与区域划分示意算术编码的基本原理ab0.81aaba0.810.96bbabaaba0.64bbabaaabab0.810.960.64bbaaba0.5120.7680.9920.928bbbbaaabbaab例设一个信源，它有两个符号a和b，出现的概率分别是0.8和0.2，有3个符号输出时，符号序列与区域划分的对应关系。

4、图B 3符号输出时的 符号序列与区域划分示意字符串 aabaa对应的区域为0.512，0.59392)该区域的二进制表示0.1000001，0.1001100)二进制数0.1001输出编码 1001因此对于这个信源：H（X）=0.7219Huffman编码:算术编码:平均码长 R=0.8平均码长 R=1相比Huffman编码，算术编码的编码效率有明显提高。对于长序列，理论上算术编码可以达到信源的熵。多元符号编码原理多元符号编码原理输入符号串 s 取自符号集 ，s 后跟 ai(aiS)扩展成符号串 sai ,空串记做 ,只有一个符号 ai 的序列就是 ai。算术编码的迭代公式算术编码的迭代公式：

5、码字刷新：C(sai)=C(s)+P(ai)A(s)(4.4-1a)区间刷新：A(sai)=p(ai)A(s)(4.4-2a)其中:(4.4-3)是符号的累积概率。初始条件为C()=0,A()=1和P()=0,p()=1。符号串每一步新扩展的码字 C(sai)都是由原符号串的码字 C(s)与新区宽度 A(sai)的算术相加而得。“算术码”的由来例4-9设某信源取自符号集 S=a,b,c,d,e,!,各符号概率和初始区间如表4.4。字符概率累积概率区间范围a0.200,0.2)b0.10.20.2,0.3)c0.10.30.3,0.4)d0.30.40.4,0.7)e0.20.70.7,0.9)

6、!0.10.90.9,1.0)表4.4 固定模式举例设待编码的字符串为单词“dead”，编码器和解码器都知道区间初值为0,1。表4.5 6元信源的算术编码过程C(sai),C(sai)+A(sai)A(sai)初始值0,1)1.0编完 d 后0.4,0.7)0.3编完 e 后0.61,0.67)0.06编完 a 后0.61,0.622)0.012编完 d 后0.6148,0.6184)0.0036编完!后0.61804,0.6184)0.00036编码过程如图4.6所示编码端无需发送最后的区间范围 0.61804,0.6184)实际上只要发送其间的某一个值即可,如0.6181。解码端收到0.6

7、181，得知区间范围为0.4,0.7)，立即解得第一个字符为d，此后解码区间由初始0,1)变为0.4,0.7)。得到这一范围后，再对所有字符按照公式计算,并与最终的区间范围0.61,0.67)相比较,得出第二个字符为e。依此类推，解码器就唯一地解出字符串“dead！”。解码过程算术编码过程:依据字符的发生概率对码区间的分割过程(即子区间宽度与正编码字符发生概率相乘的过程)。算术解码过程:只需知道最终编码区间中的某一个值就可以解码。算术编码每次递推都要做乘法，而且必须在一个信源符号的处理周期内完成，有时难以实时，为此采用了查表等许多近似计算来代替乘法。小结：固定编码模式概率统计与区间分配直接影响

8、编码效率。自适应模式各符号的概率初始值都相同，但依据实际出现的符号而相应地改变。两种编码模式：二进制编码二进制编码编码对象是二元序列:符号概率较小者为p(L)=2-Q形式,以右移Q位代替乘2-Q;符号概率较大者为p(H)=1-2-Q形式,以移位和相减代替;完全避免了乘法，因此算术编码很适合二元序列，而p(L)常用2-Q来近似。从而算术编码的迭代公式在具体实现时的计算格式为：码字刷新：C=C+P(ai)A (4.4-1b)区间刷新：A=p(ai)A (4.4-2b)有限长寄存器C实现C(s):存在进位问题,采用插入“填充位”解决,对编码效 率略有影响;有限长寄存器A来实现A(s)。实际中只能用令

9、 S=H,L,并设 p(L)=2-Q,p(H)=1-2-Q,则P(H)=0,P(L)=1-2-Q。对子区间宽度A(s)做迭代运算:A(sL)=A(s)2-Q(s)(右移Q位)(4.4-4a)A(sH)=A(s)-A(sL)(X 表示X的小数点后取q位)(4.4-4b)对码字C(s)做迭代运算：C(sH)=C(s)(4.4-5a)C(sL)=C(s)+A(sH)(4.4-5b)有限精度、不做乘法且假设Q(s)已经估计出的二进制算术编码的具体步骤如下:初始化：,;如果A(sx)0.100,则A、C重复左移，直到A 0.100为止(即保持A(s)的小数点后的第1位总是“1”);如果紧靠C的小数点前有

10、连续v个“1”,则紧靠小数点前插 入1个“0”(填充位);按上述步骤对字符串中所有字符进行迭代运算,直到最 后一个字符输出C(s)代码。参数q与Q的选择直接关系到编码器精度。例4-10对字符串“01000101”来说，H符号是“0”，L符号“1”：取q=4，v=3和Qmax=3，并假定由某个编码模型提供的Q(s)值为(2,1,2,2,3,1,1,2),对其进行算术编码。已编码的字符串编码符号x有限精度附加操作Q(s)A(s)C(s)A(s 1)A(s 0)C(sx)空020.11110.00000.00110.11000.00000011左移1位10.1100 0.11000.00000.11

11、000.01100.01100.011001020.11000.11000.00110.10010.110001001000左移1位20.10010.11100.11001.10000.00100.01110.11000100030.11101.10000.00010.11011.1000010000100011左移1位10.11010.11001.100011.11100.01100.01111.1111010001010001001000100左移1位,填充进位10.11000.110011.1110111.11001110.11000.01100.011011.1110010001001

12、0001011左移2位20.11000.11001110.1100111101.01000.00110.10011111.0101字符串 s=“01000101”可由最终子区间0.11110101,0.11111)表示,编码端传送码字“1111011”即可，码长7位。二进制解码解码只能逐字符译出:检测移入C的v位码字:如果发现“全1”,则检测第v+1位即填充位的值;若该值为0,说明无法进位,则去掉该位“0”后正常解码;若该值为1,则删去这个填充的“1”、在v位码字最后一 位上加1做进位后再解码;子区间宽度A(s)迭代：A(s1)=A(s)2-Q(s)A(s0)=A(s)-A(s1)置初值：A(

13、s)=0.111;如果A(sx)0.10 0,则A、C重复左移，直到A 0.100；按回到步骤,直到解出x后面的所有字符。字符判决:若C(s)A(s0):则x=0,置A(s)=A(s0);若C(s)A(s0):则x=1,置C(s)=C(s)-A(s0),A(s)=A(s1);Q(s)的确定与编码效率不对称数Q(s)要从一个二进制序列 s 来确定 Q 值，有待于根据该序列的统计特性,选择合适的概率模型。例如根据符号串s后出现字符1(L)的条件概率来确定 Q 值。(4.4-9)p(L|s)简单记为p，意味着每个Q值要对应着一个概率区间。按2-Q编码，每个“L”需要Q位，每个“H”需要-log(1-

14、2-Q)位。则每个符号的平均码长：l(p)=pQ-(1-p)log(1-2-Q)(4.4-10)信源符号的熵为：H(p)=p log p-(1-p)log(1-p)(4.4-11)图4.10 按2-Q的近似时的效率损失pH(p)11/2011/81/4l(1/8)l(1/4)用 2-Q 来近似所造成的编码效率的损失最大只有5%,而计算量却可减少很多。编码效率:(4.4-13)p0.3690.1820.09050.04520.02260.0113Q1或或22或或33或或44或或55或或66或或7H(p)0.9500.6840.4380.2660.1560.089L(Q,p)10.7040.447

15、0.2700.1580.090(%)95.097.298.098.598.798.9表4.7 小概率用2-Q来近似时最坏情况下的编码效率算术编码最鲜明的特点：效率高对于大部分黑白文件传真数据：对一个具体序列:平均编码效率约为98.5%看其概率分布是否集中2-Q附近,在p=2-Q处,编码效率为100%,实际应用中的关键问题就是要选择合适的概率模型,使大部分条件概率接近于2-Q。算术码评述 能够自适应地估计条件概率,从信源的统计特性 出发,建立数据的概率模型。它不必预先定义信 源的概率模型,尤其适用于不可能进行概率统计 的场合;适用于信源符号概率比较接近的场合，在几种主 要的统计编码中（Huffm

16、an，LZ家族以及算术编 码中），算术编码具有最高的压缩效率。优点：缺点：比霍夫曼编码复杂，特别是硬件实现；由于是变长码，也需要输入输出缓冲存储器，只适用于分段信息；误差扩散比分组码更严重，误码不会自动恢复，会一直延续下去，传输要求高质量的信道，或 采用检错反馈重发的方式。1基本原理基本原理2霍夫曼编码霍夫曼编码 3游程编码游程编码 4算术编码算术编码 本章内容本章内容5基于字典的编码基于字典的编码 6哥伦布编码哥伦布编码 4.5 基于字典的编码基于字典的压缩方法将长度不同的符号串(短语)编码成一个个新单词,用其形成一本短语词典的索引。若单词的码长短于它所替代的短语，就实现了数据的无损压缩，而

17、且该短语字典都是自适应生成的。LZ码基本概念1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 发表了论文“顺序数据压缩的一个通用算法”(A Universal Alogrithem for Sequential Data Compression)。1978 年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(Compression of Individual Sequences via Variable-Rate Coding)。在这两篇论文中提出的两个压缩技术被称为LZ77LZ77和LZ78LZ78。简单地说LZ码思路完全不同于从Shannon到Huf

18、fman到算术压缩的传统思路，人们将基于这一思路的编码方法称作“字典”式编码。LZ码字典式编码不但在压缩效果上大大超过字典式编码不但在压缩效果上大大超过了了Huffman编码，编码，而且易于实现，其压缩而且易于实现，其压缩和解压缩的速度也异常惊人和解压缩的速度也异常惊人。LZ编码一例英文字母和符号串编码成12位码字的压缩字符串表。符号串符号串码字码字A1AB2AN3AND4AD5Z6D7DO8DO空空9空空10空空空空11空空空空空空12空空空空空空空空13空空空空空空空空空空14空空空空空空空空空空空空150160017000180000190000120$4095表4.8 LZ码的特点 能

19、有效地利用字符出现频率冗余度、字 符重复性和高使用率模式冗余度，但通 常不能有效地利用位置冗余度；算法是自适应的，无需有关输入数据统 计量的先验信息，运算时间正比于消息 的长度；对每一消息的起始端的压缩效果很差，对整段消息压缩得更好。如果信源非均匀且冗余度特性随消息而 变动，那么消息长度远大于算法实现的 自适应范围，压缩效率就会降低。LZW算法1984年，Terry Welch发表了名为“高性能数据压缩技 术”(A Technique for High-Performance Data Compression)的论文，实现了LZ78算法的一个变种 LZW。LZW保留了保留了LZ码的自适应性能，

20、码的自适应性能，压压缩比也大致相同，其显著特点是逻辑缩比也大致相同，其显著特点是逻辑简单、硬件实现廉价、运算速度快简单、硬件实现廉价、运算速度快。UNIX上出现了使用LZW算法的Compress程序，该程序性能优良，很快成为了UNIX世界的压缩程序标准。紧随其后的是MS-DOS环境下的 ARC 程序，还有象 PKWare、PKARC 等仿制品。LZ78和LZW一时间统治了UNIX和DOS两大平台。随后LZW算法将输入字串映射成定长(通常为12位)的码字,其串表具有“前缀性”:表中任何一个字符串的前缀字符也在表中。若由某个字符串和某个单字符K 所组成的字符串K 在表中，则 也在表中。K 叫做前缀

21、串的扩展字符。LZW算法描述初始化：将所有的单字符串放入串表 读第一个输入字符 前缀串 Step：读入下一个输入字符K If 没有这样的K(输入已穷尽):码字()输出;结束。If K 已存在于串表中:K ;repeat Step.else K不在串表中:码字()输出;K 串表;K ;repeat Step.图4.11 LZW编码算法流程 例4-12对一个最简单的3字母字符串“ababcbababaaaaaaa”作LZW编码。字串表另一种形式a 1a 1b 2b 2c 3c 3ab 41b 4ba 52a 5abc 64c 6cb 73b 7bab 85b 8baba 98a 9aa 101a

22、10aaa 1110a 11aaaa 1211a 12表4.9 例4-12的编码字串表输入符号 a b ab c ba bab a aa aaa a输出符号 1 2 4 3 5 8 1 10 11 1加进表中 5 7 9 11 的新字串 4 6 8 10 12图4.12 例4-12的编码过程LZW算法对各种类型的计算机文件都有压缩效果:数据类型压缩比英语课文1.8Cobol文件(8位ASCII码)26倍浮 点 数 据1.0格式化的科学数据2.12.1系统登录数据2.6程序源代码2.3目标代码1.5表表4.10 LZW对不同数据类型的压缩结果对不同数据类型的压缩结果其他应用:TIFF图形图像格式

23、；BMP、GIF等图形图像格式；前CCITT的V.42bis建议(数据通信的国际标准)。通用编码评述即使没有任何信源统计特性的知识，也有可能设计出最佳的编码，即当码组长度趋于无穷时其性能收敛于依赖信源统计特性而设计的编码器性能。1973年，L.D.Davisson称之为通用编码(Universal Coding)理论。广义理解除了确知概率特性的编码方法以外的其他编码方法，都可以作为通用编码的一种。自适应算术编码自适应算术编码；LZ77，LZ78，LZW；派生出PKZIP、LHZRC、ARJ、Stacker、ARC和 PKARC。广泛用于文本和程序的数据压缩中，而大多数计算机系统也都采用LZ方法作为标准的压缩功能。1基本原理基本原理2霍夫曼编码霍夫曼编码 3游程编码游程编码 4算术编码算术编码 本章内容本章内容5基于字典的编码基于字典的编码 6哥伦布编码哥伦布编码 一元码一元码 定义：非负整数n的一元码为n1个1后跟1个0；或n1个0后跟1个1 特点：满足惟一可译性规则简单，生成方便便于消除误码后的同步恢复Golomb编码编码 特点：无需使用霍夫曼算法，即可直接给出最佳变长码可使服从几何分布的正整数数据链的平均码长最短 编码过程：Golomb编码编码 编码过程（续）：整数n的Golomb码可由“前缀码尾码”组成 谢 谢！