四章算术编码

第四章：算术编码算术编码：越来越流行（在很多中被采用）适合的场合：小字母表：如二进制信源概率分布不均衡建模与编码分开内容：算术编码的基本思想一些性质实现有限精度：区间缩放（浮点数/整数实现）计算复杂度：用移位代替乘法二进制编码自适应模型QM编码器：自适应二进制编码回顾：Huffman编码例1：信源的符号数目很少0ab1a=0,b=1回顾：扩展的Huffman编码例2：信源的符号的概率严重不对称：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symbolHuffman编码：a0b11c10l=1.05bits/symbol冗余（Redundancy）=l-H=0.715bits/sym(213%!)问题：能做得更好吗？10abc01回顾：扩展的Huffman编码基本思想：考虑对两个字母序列而不是单个字母编码1100100.0006cb11010.0190ba1100110.0004bb1100010.0006bc0.00090.02850.02850.01900.9025Probability1100001011001110CodeaccaccabaaLetterl=1.222/2=0.611冗余=0.276bits/symbol（27%）回顾：扩展的Huffman编码该思想还可以继续扩展考虑长度为n的所有可能的mn序列(已做了32)理论上：考虑更长的序列能提高编码性能实际上：字母表的指数增长将使得这不现实例如：对长度为3的ASCII序列：2563=224=16M需要对长度为n的所有序列产生码本很多序列的概率可能为0分布严重不对称是真正的大问题：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symboll1=1.05,l2=0.611,…当n=8时编码性能才变得可接受但此时|alphabet|=38=6561!!!算术编码（ArithmeticCoding）算术编码：从另一种角度对很长的信源符号序列进行有效编码对整个序列信源符号串产生一个唯一的标识（tag）直接对序列进行编码（不是码字的串联）：非分组码不用对该长度所有可能的序列编码标识是[0,1)之间的一个数（二进制小数，可作为序列的二进制编码）概率复习随机变量：将试验的输出映射到实数用数字代替符号X(ai)=i,其中aiA(A={ai},i=1..n)给定信源的概率模型P概率密度函数（probabilitydensityfunction,pdf）累积密度函数（cumulativedensityfunction,cdf）产生标识定义一一映射：ak[FX(k-1),FX(k)],k=1..m,FX(0)=0[FX(k-1),FX(k)]区间内的任何数字表示ak对2字母序列akaj编码对ak，选择[FX(k-1),FX(k)]然后将该区间按比例分割并选取第j个区间：将[0,1)分为m个区间：产生标识：例考虑对a1a2a3编码：A={a1,a2,a3},P={0.7,0.1,0.2)映射：a11,a22,a33cdf:FX(1)=0.7,FX(2)=0.8,FX(3)=1.0映射成实数A={a1,a2,…,am}对公平掷骰子的例子：{1,2,3,4,5,6}词典顺序（Lexicographicorder）字符串的词典顺序：其中表示“在字母顺序中，y在x的前面”n为序列的长度词典顺序：例考虑两轮连续的骰子：输出={11,12,…,16,21,22,…,26,…,61,62,…,66}注意：为了产生13的标识，我们不必对产生其他标识但是，为了产生长度为n的字符串的标识，我们必须知道比其短的字符串的概率这与产生所有的码字一样繁重！应该想办法来避免此事区间构造观察包含某个标识的区间与所有其他标识的区间不相交基本思想递归：将序列的下/上界视为更短序列的界的函数上述骰子的例子：考虑序列：322令u(n),l(n)为长度为n序列的上界和下界，则u(1)=FX(3),l(1)=FX(2)u(2)=FX(2)(32),l(2)=FX(2)(31)区间构造区间构造产生标识通常，对任意序列x=x1x2…xn只需知道信源的cdf，即信源的概率模型算术编码：编码和解码过程都只涉及算术运算（加、减、乘、除）产生标识：例考虑随机变量X(ai)=i对序列1321编码：1131321321解码标识AlgorithmInitializel(0)=0,u(0)=1.Foreachi,i=1..nComputet*=(tag-l(k-1))/(u(k-1)-l(k-1)).Findthexk:FX(xk-1)t*FX(xk).Updateu(n),l(n)Ifdone--exit,otherwisegoto1.解码：例AlgorithmInitializel(0)=0,u(0)=1.Computet*=(tag-l(k-1))/(u(k-1)-l(k-1)).Findthexk:FX(xk-1)t*FX(xk).Updateu(k),l(k)Ifdone--exit,otherwisegoto1.1131321321算术编码的唯一性和效率上述产生的标识可以唯一表示一个序列，这意味着该标识的二进制表示为序列的唯一二进制编码但二进制表示的精度可以是无限长：保证唯一性但不够有效为了保证有效性，可以截断二进制表示，但如何保证唯一性？：为了保证唯一性和有效性，需取小数点后l位数字作为信源序列的码字，其中注意：P(x)为最后区间的宽度，也是该符号串的概率符合概率匹配原则：出现概率较大的符号取较短的码字，而对出现概率较小的符号取较长的码字算术编码的唯一性和效率长度为n的序列的算术编码的平均码长为：算术编码的效率高：当信源符号序列很长，平均码长接近信源的熵实现迄今为止已有能工作的编码/解码算法假设实数（无限精度）最终l(n)和u(n)将集中到一起我们需要对字符串增量式编码观测：当区间变窄时[l(n),u(n)][0,0.5),或[l(n),u(n)][0.5,1),或l(n)[0,0.5),u(n)[0.5,1).先集中处理1.&2，稍后再讨论3实现编码器：一旦我们到达1.或2.，就可以忽略[0,1)的另一半还需要告知解码器标识所在的半区间：发送0/1比特用来指示下上界所在区间将标识区间缩放到[0,1):E1:[0,0.5)=>[0,1);E1(x)=2xE2:[0.5,1)=>[0,1);E2(x)=2(x-0.5)注意：在缩放过程中我们丢失了最高位但这不成问题—我们已经发送出去了解码器根据0/1比特并相应缩放与编码器保持同步标识产生：带缩放的例子考虑随机变量X(ai)=i对序列1321编码：Input:1321Output:Input:-321Output:1标识产生：带缩放的例子Input:--21Output:11Input:---1Output:110Input:---1Output:1100Input:---1Output:11000标识产生：带缩放的例子EOT:[l(n),u(n)]区间内的任何一个数字在此选0.510=0.12Input:---1Output:110001Input:---1Output:110001Input:---1Output:110001Output:11000110…注意：0.1100011=2-1+2-2+2-6+2-7=0.7734375[0.7712,0.77408]增量式标识解码我们需要增量式解码如：网络传输问题如何开始？必须有足够的信息，可以对第一个字符无歧义解码接收到的比特数应比最小标识对应的区间更小怎样继续？一旦有一个非歧义的开始，只要模拟编码器即可如何结束？标识解码：例假设码字长为6输入：1100011000000.1100012=0.76562510第1位：1Output:1Input:110001100000Output:13Input:-10001100000(左移)Input:-10001100000(0.546875)Output:132Input:---001100000(左移)Input:--0001100000(左移)此时解码最后一个符号标识解码：例Input:----01100000(左移)Input:-----1100000(左移)Input:-----100000(左移)Input:-----100000Output:1321第三种情况：E3回忆三种情况[l(n),u(n)][0,0.5):E1:[0,0.5)=>[0,1);E1(x)=2x[l(n),u(n)][0.5,1):E2:[0.5,1)=>[0,1);E2(x)=2(x-0.5)l(n)[0,0.5),u(n)[0.5,1):E3(x)=???E3缩放E3:[0.25,0.75)=>[0,1);E3(x)=2(x-0.25)编码E1=0,E2=1,E3=???注意：E3…E3E1=E1E2…E2E3…E3E2=E2E1…E1规则：E3连续的次数，并在输出下一个E2/E1之后发送该次数证明请见文献：Witten,Radford,Neal,Cleary,“ArithmeticCodingforDataCompression”CommunicationsoftheACM,vol.30,no.6,pp.520-540,June1987.第三种情况：E3整数实现假设码字长度为n，则ni=长度为TotalCount（TC）的序列中字符i出现的次数累积计数：CC整数实现MSB(x)=MostSignificantBitofxLSB(x)=LeastSignificantBitofxSB(x,i)=ithSignificantBitofxMSB(x)=SB(x,1);LSB(x)=SB(x,m)E3(l,u)=(SB(l,2)==1&&SB(u,2)==0)l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TC//lowerboundupdateu=l+(u-l+1)CC(x)/TC-1//upperboundupdatewhile(MSB(u)==MSB(l)ORE3(u,l))//MSB(u)=MSB(l)=0E1rescalingif(MSB(u)==MSB(l))//MSB(u)=MSB(l)=1E2rescalingsend(MSB(u))l=(l<<1)+0//shiftleft,setLSBto0u=(u<<1)+1//shiftleft,setLSBto1while(e3_count>0)send(!MSB(u))//encodeaccumulatedE3rescalingse3_count--endwhileendifif(E3(u,l))//performE3rescaling&rememberl=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildone整数编码器整数编码器：例序列：1321Count{1,2,3}={40,1,9}TotalcountTC=50CumulativecountCC{0,1,2,3}={0,40,41,50}记住：区间的终点不会重叠n=?最小的[l(n),u(n)]=整个范围内的1/4，仍能区分0..TC的最小区间：=>28x¼>50/1=>最小n=8(28=256)l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildone整数编码器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:1321Output:Input:-321Output:1整数编码器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:--21Output:110e3_count=1整数编码器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:---1Output:1100Input:---1Output:11000Input:---1Output:110001整数编码器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:---1Output:1100010Input:---1e3_count=1整数编码器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:---1Output:1100010结束通常，发送l(4):(00000000)2但是e3_count=1，因此在发送l(4)的第一个‘0’后发送‘1’最后output:1100010010000000Initializel,u,t//t=firstnbitsrepeatk=0while(((t-l+1)TC-1)/(u-l+1)CC(k)k++x=decode_symbol(k)l=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))//PerformE1/E2rescalingofl,u,tl=(l<<1)+0//add0totherightoflu=(u<<1)+1//add1totherightofut=(t<<1)+next_bitendifif(E3(u,l))//PerformE3rescalingofl,u,tl=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bitcomplementMSB(u),MSB(l),MSB(t)endifendwhileuntildone整数解码器整数解码器：例Initializel,u,trepeatk=0while((t-l+1)CC(x-1)/TCCC(k)k++x=decode_symbol(k)l=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bitendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bitcomplementMSB(u),MSB(l),MSB(t)endifendwhileuntildoneInput:1100010010000000Output:1Output:13整数解码器：例Input:1100010010000000Input:1100010010000000Input:1100010010000000Initializel,u,trepeatk=0while((t-l+1)CC(x-1)/TCCC(k)k++x=decode_symbol(k)l=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bitendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bitcomplementMSB(u),MSB(l),MSB(t)endifendwhileuntildone整数解码器：例Output:132结束已解码接收到了预定数目的字符，或接收到EOTInitializel,u,trepeatk=0while((t-l+1)CC(x-1)/TCCC(k)k++x=decode_symbol(k)l=l+(u-l+1)CC(x-1)/TCu=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bitendifif(E3(u,l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bitcomplementMSB(u),MSB(l),MSB(t)endifendwhileuntildoneOutput:1321算术编码vs.Huffman编码n=序列长度平均码长：算术：扩展Huffman：观察二者的积渐近性质相同Huffman有一个微小的边际扩展的Huffman要求巨大数量的存储和编码mn而算术编码不用实际应用中可以对算术编码假设较大的长度n但Huffman不可我们期望算术编码表现更好（除了当概率为2的整数次幂的情况）算术编码vs.Huffman编码增益为字母表大小和分布的函数较大的字母表（通常）较适合Huffman不均衡的分布更适合算术编码很容易将算术编码扩展到多个编码器QM编码器很容易将算术编码适应到统计变化模型（自适应模型、上下文模型）不必对树重新排序可以将建模与编码分开应用：图像压缩1.171.711.121.23RatioArithmetic1.146.84Omaha4.677.126.52Bits/pixel1.671.271.16RatioHuffmanEarthSensinSenaImage1.282.041.752.06RatioArithmetic1.266.27Omaha3.924.563.89Bits/pixel2.041.732.08RatioHuffmanEarthSensinSenaImage自适应算术编码：对像素值自适应算术编码：对像素差分自适应算术编码统计编码技术需要利用信源符号的概率，获得这个概率的过程称为建模。不同准确度（通常也是不同复杂度）的模型会影响算术编码的效率。建模的方式：静态建模：在编码过程中信源符号的概率不变。但一般来说事先知道精确的信源概率是很难的，而且是不切实际的。自适应动态建模：信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。算术编码很容易与自适应建模相结合。自适应算术编码自适应算术编码：在编码之前，假设每个信源符号的频率相等（如都等于1），并计算累积频率从输入流中读入一个字符，并对该符号进行算术编码更新该符号的频率，并更新累积频率由于在解码之前，解码器不知道是哪个信源符号，所以概率更新应该在解码之后进行对应的，编码器也应在编码后进行概率更新自适应算术编码为了提高解码器的搜索效率，信源符号的频率、累积频率表按符号出现频率降序排列在自适应算术编码中，可以用平衡二叉树来快速实现对频率和累积频率的更新平衡二叉树可用数组实现（类似Huffman编码中的堆）最可能出现的符号安排在根附近，从而平均搜索的次数最小详见《数据压缩原理与应用》第2.15节自适应算术编码例：信源符号及其出现频率为：数组下标：12345678910信源符号：频率：辅助变量：辅助变量为该节点左子树的总计数，用于计算累积频率例：计算a6的累积频率得到从节点10（a6）到根节点的路径：10521a6a1a2a82.令af=0,沿树枝从根节点向节点10（a6）1)取根节点的左分支到子节点a2，af不变2)取节点a2的右分支到到节点a1，将该节点的两个数值加到afaf=af+12+16=282)取节点a1的左分支到到节点a6后，将其左子树计数0加至af，最后af=28为累积频率区间的起点自适应算术编码数组下标：12345678910信源符号：频率：辅助变量：频率、累积频率表：[79,84)5a5[67,79)12a3[59,67)8a10[40,59)19a8[29,40)11a1[28,29)1a6[16,28)12a2[14,16)2a7[2,14)12a9[0,2)2a4自适应算术编码在平衡二叉树上更新频率：例：读进符号a9，将其频率计数从12变为13在数组中寻找符号a9的左边、离a9最远的、频率小于a9的元素，同时更新左子树计数值总结直接对序列进行编码（不是码字的串联）：非分组码可证明是唯一可译码渐近接近熵界对不均衡的分布，比Huffman更有效只产生必要的码字但是实现更复杂允许将建模和编码分开，容易与自适应模型和上下文模型结合对错误很敏感，如果有一位发生错误就会导致整个消息译码错误下节课内容作业：Sayood3rd,pp.114-115必做：5,6,7,8下节课内容：JPEG、JPEG2000和JBIG中的算术编码：QM编码器HistoryTheideaofencodingbyusingcumulativeprobabilityinsomeordering,anddecodingbycomparisonofmagnitudeofbinaryfractionwasintroducedinShannon’scelebratedpaper[1948].TherecursiveimplementationofarithmeticcodingwasdevisedbyElias(anothermemberinFano’sfirstinformationtheoryclassatMIT).ThisunpublishedresultwasfirstintroducedbyAbramsonasanoteinhisbookoninformationtheoryandcoding[1963].TheresultwasfurtherdevelopedbyJelinekinhisbookoninformationtheory[1968].Thegrowingprecisionproblempreventedarithmeticcodingfrompracticalusage,however.TheproposalofusingfiniteprecisionarithmeticwasmadeindependentlybyPasco[1976]andRissanen[1976].HistoryPracticalarithmeticcodingwasdevelopedbyseveralindependentgroups[Rissanen1979,Rubin1979,Guazzo1980].Awell-knowntutorialpaperonarithmeticcodingappearedin[Langdon1984].ThetremendouseffortsmadeinIBMleadtoanewformofadaptivebinaryarithmeticcodingknownastheQ-coder[Pennebaker1988].BasedontheQ-coder,theactivitiesofJPEGandJBIGcombinedthebestfeaturesofthevariousexistingarithmeticcodersanddevelopedthebinaryarithmeticcodingprocedureknownastheQM-coder[pennebaker1992].ReadingW.B.Pennebaker,J.L.Mitchell,G.G.Langdon,Jr.,R.B.Arps,“AnoverviewofthebasicprinciplesoftheQ-Coderadaptivebinaryarithmeticcoder,”IBMJ.Res.Develop.,vol.32,no.6,November1988.Witten,Radford,Neal,Cleary,“ArithmeticCodingforDataCompression”CommunicationsoftheACM,vol.30,no.6,pp.520-540,June1987.Moffat,Neal,Witten,“ArithmeticCodingRevisited,”ACMTransactionsonInformationSystems,vol.16,vo.3,pp.256–294,July1998.附：产生随机样本产生随机样本：对分布采样均匀分布伪随机数很多统计软件包中都有此工具如在Matlab中：rand其他分布直接方法：概率积分变换通过对均匀分布的采样实现对任意分布的采样间接方法：接受/拒绝算法（重要性采样）MCMC方法概率积分变换例：[概率积分变换]X有连续CDF，定义随机变量Y为，则Y为[0,1]上的均匀分布，即对随机数产生特别有用0.51.00概率积分变换X有连续严格递增的CDF，定义随机变量Y为，则Y为[0,1]上的均匀分布，即令则对任意分布采样通过对均匀分布采样，实现对任意分布的采样从随机产生一个样本y令，其中为X的CDF计算结果为对的采样对任意分布采样对任意分布采样例：对指数分布采样变形若X为离散型随机变量，其取值为则可以通过以下方式产生随机样本从随机产生一个样本y若，令定义例：为了从产生一个随机样本，从产生一个随机样本y，则