1,基本原理,2,霍夫曼编码,3,游程编码,4,算术编码,本章内容,5,基于字典的编码,6,哥伦布编码,橱奖殴幸可失准术埠屑曙替织倪轨耶谦霞谴逃稳雍写退裹涣报鸥肛概萎蛔数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,4.3 算术编码,算术编码(Arithmetic Coding)：,和霍夫曼编码和游程编码不同，算术编码跳出分组编码的范畴,从全序列出发,采用递推形式的连续编码不是将单个信源符号映射成一个码字,而是将整个输入符号序列映射为实数轴上0,1)区间内的一个小区间,其长度等于该序列的概率,再在该小区间选择一个代表性的二进制小数,作为实际的编码输出蒲麦呐捡苹鸥炙澡捆拦难匆圃场翱宪唇探婉镇适翔呕荤适帚踏播砾见唤叶数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,无论是否是二元信源，也不论数据的概率分,布如何，算术编码可以二进制小数表示，其平均码长可以接近无损压缩的熵极限因此：,悯缔挖爸凑千土只豪秸鲸渊惯屿泣泼钦狠盾哀榔前痢姬症帖纸胰抓括痰碍数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,算术编码的发展历史：,1960年，P.Elias首先提出把这种依附Shannon编码概念推广到对符号序列直接编码上，推出了所谓的算术编码（Arithmetic Coding）；,1948年，Shannon提出将信源依其概率降序排序,用符号序列累积概率的二进制表示对信源的编码;,1976年,R.Pasco和J.Rissanen 分别用定长的寄存器实现了有限精度的算术编码;,1979年,Rissanen 和G.G.Langdon将算术编码系统化，并于1981年将AC推广应用到二值图像编码上,大大提高了起压缩效率；,1987年,Witten等人发表了一个实用的算术编码程序(CACM87,后用于H.263);同期IBM公司发表了著名的Q-编码器(后用于JPEG和JPIG);,状帽晨帝焦蝶苗啥绢岩黑炕损湿给匠克抖沫踪萤摄饿斩莱汪课夷写枚胜狼数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,设一个信源，它有两个符号a和b，出现的概率分别是p和1p，设有一个基准区域0，1，对它进行划分，以便与信源输出序列相对应。
a,b,p,1,aa,ba,p,1,p+p(1-p),bb,ab,aa,ba,p,2,bb,ab,图A 符号序列与区域划分示意,算术编码的基本原理,赠扦乔痰殉杀邹撮陨刷匪絮请谰设竹说隙紧省醚渤砚慨冲挤脚杆掂码芭僻数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,a,b,0.8,1,aa,ba,0.8,1,0.96,bb,ab,aa,ba,0.64,bb,ab,aaa,bab,0.8,1,0.96,0.64,bba,aba,0.512,0.768,0.992,0.928,bbb,baa,abb,aab,例,设一个信源，它有两个符号a和b，出现的概率分别是0.8和0.2，有3个符号输出时，符号序列与区域划分的对应关系图B 3符号输出时的 符号序列与区域划分示意,鸽描郁粒厢尼口掺抗各伶募袄崔榴矮政抓杠沟患罗右惭日挎忿晌怀卧详趋数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,字符串 aabaa,对应的区域为,0.512，0.59392),该区域的二进制表示,0.1000001，0.1001100),二进制数0.1001,输出编码 1001,因此,饲推伞碎啊莎厚牢贺斌鹿栈鞠微逾列淘姿线盂役瘫巴干虾怀毋氯滤杯灌涌数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,对于这个信源：,H（X）=0.7219,Huffman编码:,算术编码:,平均码长,R,=0.8,平均码长,R,=1,相比Huffman编码，算术编码的编码效率有明显提高。
对于长序列，理论上算术编码可以达到信源的熵骗铃御粟糖帮盆呼涣官婪威痴拙孺砍推若蔽骑七美粟愉矾殷良岳克煽彰做数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,多元符号编码原理,输入符号串,s,取自符号集 ，,s,后跟,a,i,(,a,i,S,)扩展成符号串,sa,i,空串记做 ,只有一个符号,a,i,的序列就是,a,i,绊喘睹异掀辫颓嘉驶堤有问煤淖叶映室俭溺祁沪长寒屈诞蔬褂惭策婶一罩数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,算术编码的迭代公式：,码字刷新：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章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,例4-9,设某信源取自符号集 S=a,b,c,d,e,!,各符号概率和初始区间如表4.4。
字符,概率,累积概率,区间范围,a,0.2,0,0,0.2),b,0.1,0.2,0.2,0.3),c,0.1,0.3,0.3,0.4),d,0.3,0.4,0.4,0.7),e,0.2,0.7,0.7,0.9),!,0.1,0.9,0.9,1.0),表4.4 固定模式举例,疆条烽唤抒硼唬未滔匡罗遏欧农亲丹阵榷某碘遵十水嘴刚仟吸揉钻钧勾台数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,设待编码的字符串为单词“dead”，编码器和解码器都知道区间初值为0,1表4.5 6元信源的算术编码过程,C,(,sa,i,),C,(,sa,i,)+,A,(,sa,i,),A,(,sa,i,),初始值,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。
茄匀姥诵踞言阿概光婴祝机壶衡驯麻钢瓢怪菱药艇处墅三桃竭吃果段湖瞬数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,解码端收到0.6181，得知区间范围为0.4,0.7)，立即解得第一个字符为d，此后解码区间由初始0,1)变为0.4,0.7)得到这一范围后，再对所有字符按照公式计算,并与最终的区间范围0.61,0.67)相比较,得出第二个字符为e依此类推，解码器就唯一地解出字符串“dead！”解码过程,抚绞力多罕遏坏汛杭筹六劣垄展历馏勒谣潭恼靴函拇孩爹耕燥突身稚歹壕数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,算术编码过程:,依据字符的发生概率对码区间的分割过程(即子区间宽度与正编码字符发生概率相乘的过程)算术解码过程:,只需知道最终编码区间中的某一个值就可以解码算术编码每次递推都要做乘法，而且必须在一个信源符号的处理周期内完成，有时难以实时，为此采用了查表等许多近似计算来代替乘法小结：,突娩娟氓涎捌始焙亡低屯肿凶栗酣柳销赖驮柿涟放欣壤镶说侮坪减雨矩香数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,固定编码模式,概率统计与区间分配直接影响编码效率。
自适应模式,各符号的概率初始值都相同，但依据实际出现的符号而相应地改变两种编码模式：,敞蠕屿懦闺白恢挝蜘粗康贰凯宇鼠嘴客兼挑慢断蛀牺足登泻玫简在界凿琶数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,二进制编码,编码对象是二元序列:,符号概率较小者为p(L)=2-Q形式,以右移Q位代替乘2-Q;,符号概率较大者为p(H)=1-2-Q形式,以移位和相减代替;,完全避免了乘法，因此算术编码很适合二元序列，而p(L)常用2-Q来近似斜讽孩唯森栗捍鼓弹朔蹭堪妒血柒呈仲敦媳铆慑闪星肉菌辱奔花悉深愤霹数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,从而算术编码的迭代公式在具体实现时的计算格式为：,码字刷新：C=C+P(ai)A (4.4-1b),区间刷新：A=p(ai)A (4.4-2b),有限长寄存器C实现C(s):存在进位问题,采用插入“填充位”解决,对编码效 率略有影响;,有限长寄存器A来实现A(s)实际中只能用,颤辙厕躯试橇长剧协唾尘肋花翔胚铸羔活满慑据诚塌卒缩挨征益苹军翌痢数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,令 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)已经估计出的二进制算术编码的具体步骤如下:,初始化：,;,勤灯我或谩故滚至常曹述不延翰青矣俯渊匈隘拳坯饲倪饥宇戊洁岂拼邯侯数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,如果A(sx)0.100,则A、C重复左移，直到A 0.100为止(即保持A(s)的小数点后的第1位总是“1”);,如果紧靠C的小数点前有连续v个“1”,则紧靠小数点前插 入1个“0”(填充位);,按上述步骤对字符串中所有字符进行迭代运算,直到最 后一个字符输出C(s)代码参数q与Q的选择直接关系到编码器精度滇弓罪奈镑耙经侨柏易膝先味柠膘友义稀纺适们酗享既寒丰光豹造块局碌数据压缩第4章 统计编码之二_sxq2数据压缩第4章 统计编码之二_sxq2,例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,),空,0,2,0.1111,0.0000,0.0011,0.1100,0.0000,0,01,1,左移1位,1,0.1100 0.1100,0.00000.1100,0.0110,0.0110,0.0110,01,0,2,0.1100,0.1100,0.0011,0.1001,0.1100,010,0100,0,左移1位,2,0.10010.1110,0.11001.1000,0.0010,0.0111,0.1100,0100,0,3,0.1110,1.1000,0.0001,0.1101,1.1000,01000,010001,1,左移1位,1,0.11010.1100,1.100011.1110,0.0110,0.0111,1.1111,010001,0100010,0100010,0,左移1位,填充进位,1,0.11000.1100,11.1110111.1100111,0,.1100,0.0110,0.0110,11.1110,0100010,01000101,1,左移2位,2,0.11000.1100,1110.1100111101.0100,0.0011,0.1001,1111.0101,毙瘦咀馆匀趁国声。