数据压缩与信源编码第4讲算术编码

数据压缩与信源编码第4讲算术编码ArithmeticCoding西安电子科技大学电子工程学院主讲：林三虎算术编码的提出Huffman编码是最佳变长码，但仍包含冗余信息。符号a1a2a3a4a5概率0.20.40.20.10.1Huffman编码10011011101111Huffman编码平均码长=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits信源的熵Huffman编码冗余度=Huffman编码平均码长-信源的熵=0.078bits/symbolsymbolbitaPaPaiaPAHiiii/122.2)(log)()()()(算术编码的提出为什么Huffman编码不能达到理论上的极限？符号a1a2a3a4a5概率0.20.40.20.10.1信息量bit2.321.322.323.323.32Huffman编码10011011101111Huffman编码的问题在于每个符号的编码长度只能为整数，而信息论告诉我们，对每个符号的最佳编码长度为其信息量。能否用小数个二进制位来进行编码呢？行！这就是算术编码。1948年，香农提出了算术编码的基本思想，并证明了其优越性。算术编码的主要步骤算术编码主要步骤10①将当前区间定义为[0,1)。算术编码的主要步骤算术编码主要步骤SWIM空格10.50.40.20.10②把当前区间分割为长度正比于符号概率的子区间。示例1：对输入序列”SWISSMISS”进行压缩符号SWIM空格频率51211概率0.50.10.20.10.1算术编码的主要步骤算术编码主要步骤SWIM空格10.50.40.20.10③为输入的符号选择一个子区间，将其定义为新的当前区间。示例1：对输入序列”SWISSMISS”进行压缩第一个字符为S，对应区间为[0.5,1.0)，将其作为当前区间，按照概率进行分割10.50.5+0.5*0.1=0.550.5+0.5*0.2=0.60.5+0.5*0.4=0.70.5+0.5*0.5=0.75算术编码的主要步骤算术编码主要步骤SWIM空格10.750.70.60.550.5③为输入的符号选择一个子区间，将其定义为新的当前区间。示例1：对输入序列”SWISSMISS”进行压缩第二个字符为W，对应区间为[0.7,0.75)，将其作为当前区间，按照概率进行分割0.70.750.7+0.05*0.1=0.7050.7+0.05*0.2=0.710.7+0.05*0.4=0.720.7+0.05*0.5=0.725算术编码的主要步骤算术编码主要步骤SWIM空格③为输入的符号选择一个子区间，将其定义为新的当前区间。示例1：对输入序列”SWISSMISS”进行压缩第三个字符为I，对应区间为[0.7,0.75)，将其作为当前区间，按照概率进行分割0.70.750.7050.710.720.7250.710.720.71+0.01*0.1=0.7110.71+0.01*0.2=0.7120.71+0.01*0.4=0.7140.71+0.01*0.5=0.715算术编码的主要步骤算术编码主要步骤①将当前区间定义为[0,1)。②把当前区间分割为长度正比于符号概率的子区间。③为输入的符号选择一个子区间，将其定义为新的当前区间。④重复②③两步，知道所有符号输入完成。以当前区间中的任意一个数字作为输入符号序列的编码。SWIM空格0.70.750.7050.710.720.7250.710.720.71+0.01*0.1=0.7110.71+0.01*0.2=0.7120.71+0.01*0.4=0.7140.71+0.01*0.5=0.715算术编码的示例1示例1：对输入序列”SWISSMISS”进行压缩符号下限上限S0.51.0W0.70.75I0.710.72S0.7150.72S0.71750.72空格0.71750.71775M0.7175250.71755I0.7175300.717535S0.71753250.717535S0.717533750.717535算术编码的示例1示例1：对输入序列”SWISSMISS”进行压缩输入序列”SWISSMISS”对应区间为输入序列”SWISSMISS”包含10个字符，0.717534只包含6个十进制数字，数码缩短，完成数据压缩。算术编码基本过程可以用下面两个式子迭代来完成)()(XHighRangeOldLowOldHighOldLowNewHigh)()(XLowRangeOldLowOldHighOldLowNewLow[0.71753375,0.717535)选择该区间中任意一个数字可代表该输入序列，如0.717534。算术编码的示例1示例1：对压缩序列0.717534进行解码0.717534在[0.5,1)范围内，因此第一个符号为S。435068.05.0/)5.0717534.0(0.435068在[0.4,0.5)范围内，因此第二个符号为W。35068.01.0/)4.0435068.0(0.35068在[0.2,0.4)范围内，因此第三个符号为I。7534.02.0/)2.035068.0(0.7534在[0.5,1.0)范围内，因此第四个符号为S。SWIM空格10.50.40.20.10算术编码的示例1示例1：对压缩序列0.717534进行解码5068.05.0/)5.07534.0(0.5068在[0.5,1.0)范围内，因此第五个符号为S。0136.05.0/)5.05068.0(0.0136在[0.0,0.1)范围内，因此第六个符号为空格。136.01.0/)0.00136.0(0.136在[0.1,0.2)范围内，因此第七个符号为M。SWIM空格10.50.40.20.10算术编码的示例1示例1：对压缩序列0.717534进行解码8.02.0/)2.036.0(0.8在[0.5,1.0)范围内，因此第九个符号为S。6.05.0/)5.08.0(0.6在[0.5,1.0)范围内，因此第十个符号为S。36.01.0/)1.0136.0(0.36在[0.2,0.4)范围内，因此第八个符号为I。RangeXLowRangeCodeCode/))((解码过程可以用下式来表示SWIM空格10.50.40.20.10算术编码的示例1问题1：第十个符号S解码出来以后，数值为0.6，如何知道码流解码已经结束？6.05.0/)5.08.0(0.6在[0.5,1.0)范围内，因此第十个符号为S。解答1：在编码过程中记录码流的长度，添加在压缩码流的前面进行存储/传送。解码时首先获得码流长度，当解码到指定长度时结束。解答2：人为添加一个概率非常小的字符EOF在原始码流的最后一起编码，当解码出现EOF的时候结束。算术编码的示例2示例2：对输入序列”SWIS”进行压缩符号SWIEOF频率5111概率0.40.20.20.2区间[0.6,1.0)[0.4,0.6)[0.2,0.4)[0.0,0.2)符号下限上限S0.61.0W0.6+0.4*0.4=0.760.6+0.4*0.6=0.84I0.76+0.2*0.08=0.7760.76+0.4*0.08=0.792S0.776+0.016*0.6=0.78560.792EOF0.7856+0.0064*0=0.78560.7856+0.0064*0.2=0.78688算术编码的示例2示例2：对输入序列”SWIS”进行压缩符号SWIEOF频率5111概率0.40.20.20.2区间[0.6,1.0)[0.4,0.6)[0.2,0.4)[0.0,0.2)符号下限上限S0.61.0W0.6+0.4*0.4=0.760.6+0.4*0.6=0.84I0.76+0.2*0.08=0.7760.76+0.4*0.08=0.792S0.776+0.016*0.6=0.78560.792EOF0.7856+0.0064*0=0.78560.7856+0.0064*0.2=0.78688可以选择0.7856或者0.786作为输出算术编码的示例2示例2：对压缩序列0.786进行解码0.786在[0.6,1)范围内，因此第一个符号为S。465.04.0/)6.0786.0(0.465在[0.4,0.6)范围内，因此第二个符号为W。325.02.0/)4.0465.0(0.325在[0.2,0.4)范围内，因此第三个符号为I。625.02.0/)2.0325.0(0.625在[0.6,1.0)范围内，因此第四个符号为S。0.125在[0,0.2)范围内，因此第五个符号为EOF，解码结束。125.04.0/)6.0625.0(SWIEOF10.60.40.20整数算术编码在算术编码中，当前区间的下限LOW和上限HIGH随着码流长度的增大，将变的无限长。而实际上，双精度的实数也只有16位有效数字，更长精度的数无法表示。比如一个1MB的文件被压缩成100KB，即当前区间需要用100KB长的数来表示，而两个这样的数进行加减乘除都需要很长的时间。因此，一个实用的方案应当采用有限长度的整数运算。即使有一种方法能够表示足够长的数据精度，两个很长的数进行运算，花费的时间也无法承受。整数算术编码早在1948年，香农就提出了算术编码的基本思想。1960年，PeterElias提出了算术编码的概念，但他发现实际当中根本无法实现。直到1976年，R.Pasco和J.Rissanen才分别用定长的寄存器实现了有限精度的算术编码。1987年Witten等人发表了一个实用的算术编码程序，后用于ITU-T的H.263视频压缩标准。整数算术编码示例1：对输入序列”SWISSMISS”进行压缩符号下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500如何利用有限字长寄存器来实现算术编码？整数算术编码示例1：对输入序列”SWISSMISS”进行压缩符号下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500在算术编码中，当前区间的下限LOW和上限HIGH左边的数字一旦相同，就不会再变化。整数算术编码示例1：对输入序列”SWISSMISS”进行压缩相同的数字可以直接输出到压缩码流，这样LOW和HIGH中可以不用再保留它们，将它们从LOW和HIGH中移出去。这个特点使得LOW和HIGH可以使用较短的长度来表示。符号下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500整数算术编码示例1：对输入序列”SWISSMISS”进行压缩相同的数字可以直接输出到压缩码流，这样LOW和HIGH中可以不用再保留它们，将它们从LOW和HIGH中移出去。这个特点使得LOW和HIGH可以使用较短的长度来表示。符号下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500整数算术编码110/)()1(XqHighCumFreOldLowOldHighOl