4.4 算术编码

1第四章统计编码讲课内容：4.1.基本原理4.2.霍夫曼编码4.3.算术编码4.4.LZW编码2【例题】假定用于通信的电文仅由8个字母a,b,c,d,e,f,g,h组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母1）设计定长码；2）设计不等长Huffman编码,并给出该电文的总码数。第四章统计编码对于定长编码,电文的总码数为3×100＝300位3第四章统计编码Huffman编码4第四章统计编码Huffman编码总码数(4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257)54.3算术编码(ArithmeticCoding)一、问题的引入假设某个字符的出现概率为80%，该字符事实上只需要-log2(0.8)=0.322位编码，但Huffman编码一定会为其分配一位0或一位1的编码。难道真的能只输出0.322个0或0.322个1吗？64.3算术编码(ArithmeticCoding)4.3.1多元符号算术编码原理4.3.2自适应模型算术编码4.3.3二进制算术编码4.3.4二进制算术解码4.3.5算术编码评价74.3算术编码(ArithmeticCoding)它是一种非分组编码算法。它是从全序列出发，采用递推形式的连续编码。它不是将单个的信源符号映射成一个码字，而是将整个输入序列的符号依据它们的概率映射为实数轴上区间[01)内的一个小区间，再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出。二、算术编码定义例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.64。84.3.1多元符号算术编码1)码字刷新：C(sai)=C(s)+P(ai)A(s)2)区间刷新：A(sai)=p(ai)A(s)设输入符号串s取自符号集S={a1,a2,a3,…,am}，p(ai)={p1,p2,p3,…,pm}，s后跟符号ai扩展成符号串sai，算术编码的迭代关系为:符号累积概率：初始条件：11)()(ikkiapaP1)(,0)(,1)(,0)(pPAC一、算术编码94.3.1多元符号算术编码当处理ai时，区间A(s)宽度根据ai出现概率p(ai)而变窄，符号序列越长，相应的子区间越窄，编码的位数越多。符号串每一步新扩展的码字C(sai)都是由原符号串的码字C(s)与新区间宽度A(sai)的算术相加，“算术码”由此得名。算术编码在传输任何信号ai之前，信号的完整范围是)1,0[))()(),([ACC104.3.1多元符号算术编码例题1：设某信源取自符号集S={a,b,c,d,e,!}，!表示编码结束，各符号概率和初始子区间如下，设待编码的为“dead！”，编码器和解码器的初值区间[0，1)表1114.3.1多元符号算术编码编码第一个字符d时编码第二个字符e时()()()()()0.20.10.10.30.7()()()()0.40.70.30.61()()()()()0.20.30.06PepapbpcpdCseCdPeAdAsepeAspeAd区间变化：[0.4,0.7)[0.61,0.67)()()()()0.20.10.10.4()()()()()()00.410.4()()()()()()()0.310.3[0,1)[0.4,0.7)PdpapbpcCsdCdCdCPdAAsdAdAdpdAspdA区间变化：124.3.1多元符号算术编码编码第三个字符a时()0()()()()()0.61()()()()()0.20.060.012[0.61,0.67)[0.61,0.622)PaCsaCeaCePaAeAsapaAspaAe依此类推，结果如下表13最后在区间[0.61804,0.6184)中任取一个代表性的小数，譬如0.6183，转化成二进制小数0.1001111，最后编码输出1001111。144.3.1多元符号算术编码编码154.3.1多元符号算术编码二、算术解码解码器首先输入符号及区间，重构表1.然后输入其余码字。比如第一个数字是“6”，解码器立即知道是形如0.6…的数字。该数字位于d的子区间[0.4,0.7)中，所以第一个符号就是d。然后从该数字中减去d子区间的低端值0.4，再除以d子区间宽度0.3，以消除符号d对码字的影响。结果是0.727667，告诉解码器下一个符号是e(因为e的子区间是[0.7,0.9))。16为了从码字中消除符号x的影响，解码器执行Code:=(Code-LowRange(x))/Range的操作，Range是符号x的子区间宽度。表2总结了本例解码步骤。字符低码字范围d0.6183-0.4=0.2183/0.3=0.727667e0.727667-0.7=0.02767/0.2=0.13835a0.13835-0=0.13835/0.2=0.69175d0.69175-0.4=0.29175/0.3=0.9725!解码结束表2算术解码过程174.3.1多元符号算术编码[例2]假设信源符号为{a,b,c,d}，这些符号的概率分别为{0.1,0.4,0.2,0.3}，对输入消息序列cadacdb进行算术编码。符号abcd概率0.10.40.20.3初始编码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)解：根据这些概率可把间隔[0,1)分成4个子间隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)。信息可综合在表中。184.3.1多元符号算术编码编码时首先输入的符号是c，找到它的编码范围是[0.5,0.7)。由于消息中第二个符号a的编码范围是[0,0.1)，因此它的间隔就取[0.5,0.7)的第一个十分之一作为新间隔[0.5,0.52)。依此类推，编码第3个符号d时取新间隔为[0.514,0.52)，…。消息的编码输出可以是最后一个间隔中的任意数。194.3.1多元符号算术编码204.3.2自适应模型算术编码一、自适应模型问题引入？1、静态模型如何实现？对信息bccb中只有两个字符，概率分布为Pb=0.5，Pc=0.5。压缩中不必更新概率分布，每次区间的划分都按此分布。214.3.2自适应模型算术编码2、静态模型缺点（即为什么用自适应模型？）①静态模型无法适应信息的多样性必须消耗一定的空间保存静态模型统计出的概率分布②静态模型需要在压缩前对信息内字符的分布进行统计，这一统计过程将消耗大量的时间，使得本来就比较慢的算术编码压缩更加缓慢。③对较长的信息，静态模型统计出的符号概率是该符号在整个信息中的出现概率，而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率。224.3.2自适应模型算术编码例1：考虑某条信息中可能出现的字符仅有abc三种，我们要压缩保存的信息为bccb。假设我们对abc三者在信息中的出现概率一无所知（我们采用的是自适应模型），不妨设字符出现概率相等{Pa,Pb,Pc}={1/3,1/3,1/3}二、自适应模型算术编码234.3.2自适应模型算术编码{Pa,Pb,Pc}={1/3,1/3,1/3}{Pa,Pb,Pc}={1/4,2/4,1/4}第一个字符为b244.3.2自适应模型算术编码第二个字符为c接着出现c，现在关注上一步中得到的c的区间0.5834-0.6667。新添c后，三个字符的概率分布{Pa,Pb,Pc}={1/5,2/5,2/5}我们用这个概率分布划分区间0.5834-0.6667254.3.2自适应模型算术编码第三个字符为c划分c的区间0.6334-0.6667：三个字符的概率分布为：{Pa,Pb,Pc}={1/6,2/6,3/6}264.3.2自适应模型算术编码最后一个字符b，不用再做进一步的划分了，上一步中得到的b的区间为0.6390-0.6501，在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前面没有太多意义的0和小数点，我们可以输出1010001111。第四个字符为b274.3.2自适应模型算术编码三、自适应算术编码如何解压缩呢？解压缩之前我们仍设三个字符的概率相等，并得出第一幅分布图。先在二进制流数据前面加上0和小数点把它变成小数0.1010001111，也就是十进制0.64。发现0.64在分布图中落入字符b的区间内，我们立即输出字符b，并得出三个字符新的概率分布。类似压缩时采用的方法，我们按照新的概率分布划分字符b的区间。在新的划分中0.64落入了字符c的区间，则输出字符c。同理类推，完成全部解压缩过程。284.3.2自适应模型算术编码如何解压缩呢？b③ccb294.3.2自适应模型算术编码四、算术编码的精度？算术编码实际上采用了化零为整的思想来表示小数个二进制位，我们无法精确表示单个小数位字符，但我们可以将许多字符集中起来表示，仅仅允许在最后一位有很小的误差。我们每输入一个符号，都对概率的分布表做一下调整，并将要输出的小数限定在某个越来越小的区间范围内。对输出区间的限定是问题的关键所在。304.3.3二进制算术编码一、基本工作原理设编码初始化子区间为[0，1)MPS与LPS分配如图大概率PeMPS（MostProbableSymbol）小概率QeLPS（LeastProbableSymbol）Pe=1-Qe设置（C，A）,令C=0A=1C寄存器的值为子区域的起始位置A寄存器的值为子区域的宽度31说明算术编码方法。1．假设“0”小概率―――eQ，“1”为大概率―――eeQP12．算术编码过程：(1)初始值C=0；A=1。(2)C、A的迭代算法1,0,eAQCCC1,10,eeQAAQA(3)C、A统一表达式(对于第J位时的C、A)nemeQQA1，jnm，总共有n个“1”eniiQAC1(4)利用C、A表达式编码(设字符串为8位时)88ACAL，LA：尾，8C：头，则取LACC'8'C为所编的算术码。32例题1:设输入信源为11011111，对其编码0为LPS,Qe=（0.001）b;1为MPS,Pe=（0.111）b初始状态：C=0,A=11)1为MPSC=C+AQe=0+10.001=0.001A=APe=10.111=0.1114.3.3二进制算术编码0.0010.111332)1为MPSC=C+AQe=0.001+0.1110.001=0.001111A=APe=0.1110.111=0.1100010.0011110.1100014.3.3二进制算术编码3)0为LPSC=C=0.001111;A=AQe=0.1100010.001=0.0001100010.0011110.00011000134头0.0101尾传送码字为0101头0.010001111110111100000001+0.000011001001000010111111尾0.010101000111111111000000编码过程4.3.3二进制算术编码35二进制解码：按QePe分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号；设c’=（0.0101）b是被解码的值初始值A=1Qe=0.001当c’落在0-QeA之间，解码符号为D=0；C’=C’；A=QeA；当c’落在QeA-A之间，解码符号为D=1；C’=C’-QeA；A=A（1-Qe）4.3.4二进制算术解码361）C’=0.0101落在QeA-A之间，解码符号为D=1C’=C’-QeA=0.0101-0.001=0.0011A=A（1-Qe）=0.1112）C’=0.0011落在QeA-A之间，解码符号为D=1C’=C’-QeA=0.0011-0.000111=0.000101A=A（1-Qe）=0