第11讲――算术编码与LZ编码

算术编码与LZ编码第十讲算术编码•前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的基础上，这种编码方法通常称为块码或分组码，此时信源符号一般是多元的。•如果要对二元序列进行编码，则需采用合并信源符号方法，把二元序列转换成多值符号，转换时二元符号之间的相关性不予考虑，转换后这些多值符号之间的相关性也不予考虑。这就使信源编码的匹配原则不能充分满足，编码效率一般不高。•为了克服这种局限性，需要跳出分组码范畴，从整个符号序列出发，采用递推形式进行编码。从整个符号序列出发，将各信源序列的概率映射到[0,1)区间上，然后选取区间内的一点（也就是一个二进制的小数）来表示信源序列。算术编码基本思想设信源字母表为{a1,a2},概率p(a1)=0.6,p(a2)=0.4，将[0,1]按概率比例分为区间[0,0.6],[0.6,l]。p(a1)p(a2)00.6100.360.60.841p(a1a1)p(a1a2)p(a2a1)p(a2a2)随着序列的长度不断增加,C所在区间的长度就越短,也就可以更加精确地确定C的位置设信源符号集A={a1,a2,…,an},其相应概率分布为pi,pi0(i=1,2,…,n),定义信源符号的累积概率（分布函数）为P1=0;P2=p1;P3=p1+p2;…11riirpP累积概率r=1,2,…,npr=Pr+1-Pr)1,0[rPP1p1P2P3P41p2p3……0当A={0,1}二元信源时，P(0)=0;P(1)=p0P(0)P(1)01p0p1二元序列的累积概率引例设有二元序列S=011，求S的累积概率P(S)=p(000)+p(001)+p(010)若S后面接0P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S)若S后面接1P(S1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)+p(0110)=P(S)+p(0110)=P(S)+p(S)P1二元序列的累积概率P(Sr)=P(S)+p(S)Pr01100111P(0)0P(1)1p0设符号序列S=011p1P(0)P(1)p(00)=p(0)P1P(01)p(01)P(01)P(1)P(011)p(010)=p(01)P1p(011)二元序列的累积概率P(Sr)=P(S)+p(S)Pr二元信源符号序列的累积概率递推公式1,0)()(),(rPSpSPrSPr信源符号序列所对应区间的宽度递推公式1,0)()(),(),(rrpSprSprSA累积概率递推公式一般多元信源序列的累积概率递推公式rrPSpSPaSP)()(),()()(),(),(rrrapSpaSpaSA序列的概率公式•实际中,求序列累积概率只需两个存储器,起始时可令:A(Φ)=1,C(Φ)=0每输入一个符号,存储器C和A就按照上式更新一次,直至符号输入完毕,这时存储器C的内容即为该序列的累积概率。rrPSpSPaSP)()(),()()(),(),(rrrapSpaSpaSA累积概率递推公式累积概率递推计算注意：计算过程中,每输入一个符号只要进行乘法和加法运算。通过信源符号序列累积概率计算,把区间分割成许多小区间,不同的信源符号序列对应不同的区间为[P(S),P(S)+p(S))，可取小区间内的一点来代表这序列。将符号序列的累积概率写成二进位小数，取小数点后L位,若后面有尾数,就进位到第L位，即)(1logSpL算术编码若P(S)=0.10110001，L=3则C=0.110LLSP.0)(算术编码的唯一可译性由码C的形成方法，)(SPC)(1logSpL又可知可知LSp2)()()(SpSPLSP2)(C由此可见C必在))()(),([SpSPSP))()(),([SpSPSPCLSPC2)(,因而唯一可译。)(1logSpL对于长序列，p(S)必然很小，L与概率倒数对数几乎相等，也就是说取整造成的差别很小，因而平均码长将接近于信源熵H(S)7)(1logSpL设二元无记忆信源S={0,1},p(0)=1/4,p(1)=3/4。S=11111100，对其做算术编码。P(S)=p(00000000)+p(00000001)+p(00000010)+…+p(11111011)=1-p(11111111)-p(11111110)-p(11111101)-p(11111100)=1-p(111111)=1-(3/4)6=0.110100100111从而得C=0.1101010，S的码字为1101010解：p(S=11111100)=p2(0)p6(1)=(1/4)2(3/4)6例题1101001)1()()1()1()0()()0()0()0()()()1()()0(pppApppAppPPPPSSSSSSSSSSS+=p(1)=3/4=(0.11)2p(11)=(3/4)2=(0.1001)2+=…p(0)=(1/4)=2-2p(S)p(0)→p(S)右移2位1log14()npu设无记忆信源U={a1,a2,a3,a4}，其概率分布依次为0.5,0.25,0.125,0.125，对信源序列做算术编码。解：例题21134121aaaaaaaau42214()(0.5)(0.25)(0.125)2Pu序号uip(ui)P(ui)l(ui)C0空1001a21/41/220.102a11/81/230.1003a11/161/240.10004a31/12835/6470.10001105a41/1024567/1024100.10001101116a11/2048567/1024110.100011011107a21/81922269/4096130.10001101110108a11/163842269/4096140.10001101110100算术编码递推过程a1,a2,a3,a40.5,0.25,0.125,0.12521134121aaaaaaaaurrPSpSPaSP)()(),(1()0Pa2()1/2Pa3()3/4Pa4()7/8Pa1log14()Lpu设无记忆信源U={a1,a2,a3,a4}，其概率分布依次为0.5,0.25,0.125,0.125，对信源序列做算术编码。由算术编码递推表得C=0.100110111010000，从而U的码字为1001101110100解：例题RUH)(1.75100%14/821134121aaaaaaaau42214()(0.5)(0.25)(0.125)2Pu()0.5log0.50.25log0.2520.125log0.1251.75HU()logHUnDP(0)0P(1)1p(0)译码输出序列011p(1)P(0)P(1)p(00)P(01)p(01)P(01)P(1)P(011)p(010)p(011)算术编码译码CCC()CP()(0)Ap对二元算术码而言，其译码过程是一系列比较过程：每一步比较与，这里为前面已译出的序列串，是序列串对应的宽度，是序列的累积概率值，即为对应区间的下界限，是此区间内下一个输入为符号“0”所占的子区间宽度。译码规则为：若＜，则译输出符号为“0”；若＞，则译输出符号为“1”。()CP()(0)Ap()A()P()(0)Ap()CP()(0)Ap()CP()(0)Ap算术编码译码•算术编码的编码效率很高，当信源符号序列很长时，L很大时，平均码长接近信源熵。•从性能上来看，算术编码具有许多优点，它所需的参数较少、编码效率高、编译码简单，不象哈夫曼码那样需要一个很大的码表。算术编码在图像数据压缩标准（如JPEG）中得到广泛的应用。算术编码两位以色列研究者J.Ziv和A.Lempel独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的通用压缩算法——LZ算法。LZ编码对于统计特性确知的平稳信源，已有huffman编码和算术编码高效编码方法，其平均码长可逼近信源的平均符号熵，而且实现困难不算太大，所以已进入实用。要确知信源的统计特性相当困难。通用编码指在信源统计特性不知时，对信源进行编码，而且编码效率很高。12{,,,}KAaaa设输入信源符号序列为尽可能取最少个相连的信源符号，并保证各段都不相同。Luuuu,,,21iu，其中，编码时将此序列分成不同的段。分段规则则编码的码字由段号加后面一个符号组成。设序列分段结果为cyyyy,321，若ij则rijayy或者说编码码字可用两个数段号i和符号序号r组成。LZ78码设U={a1,a2,a3,a4}，信源序列为121324243114aaaaaaaaaaaa按照分段规则，可以分为121324243114,,,,,,aaaaaaaaaaaa段号短语ir编码1a100000002a201000013a1a312001104a2a423010115a2a4a342100106a1a110001007a40300011符号编码表a1a2a3a40123000110113512n35log12RnD例题可以看出LZ78编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典，无需传输字典本身。当编码的信源序列较短时，LZ性能似乎会变坏，但是当序列增长时，编码效率会提高，平均码长会逼近信源熵。例题段号短语ir编码1a100000002a201000013a1a312001104a2a423010115a2a4a342100106a1a110001007a40300011符号编码a1a2a3a4012300011011例题00000000010011001011100100010000011码序列可以看出LZ78编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典，无需传输字典本身。当编码的信源序列较短时，LZ性能似乎会变坏，但是当序列增长时，编码效率会提高，平均码长会逼近信源熵。例题目前算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的WinZIP、WinRAR、gzip等压缩工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者。作业3.73.123.14本节小结算术编码LZ编码–编码方法（映射、选取）（本节内容见课本73-79页）–基本思想–基本思想–编码方法（字典）