数据压缩第4章统计编码之二_sxq2.ppt

1,,基本原理,2,,霍夫曼编码,3,游程编码,4,算术编码,本章内容,,,5,基于字典的编码,6,哥伦布编码,,4.3 算术编码,算术编码(Arithmetic Coding )：,和霍夫曼编码和游程编码不同，算术编码跳出分组编码的范畴, 从全序列出发, 采用递推形式的连续编码不是将单个信源符号映射成一个码字, 而是将整个输入符号序列映射为实数轴上[0,1)区间内的一个小区间, 其长度等于该序列的概率, 再在该小区间选择一个代表性的二进制小数, 作为实际的编码输出无论是否是二元信源，也不论数据的概率分 布如何，算术编码可以二进制小数表示，其平均码长可以接近无损压缩的熵极限因此：,算术编码的发展历史：,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);,设一个信源，它有两个符号a和b，出现的概率分别是p和1–p，设有一个基准区域[0，1]，对它进行划分，以便与信源输出序列相对应。

图A 符号序列与区域划分示意,算术编码的基本原理,,aa,ba,,0.8,1,,,,0.96,bb,ab,,aa,ba,,,,0.64,bb,ab,,例,设一个信源，它有两个符号a和b，出现的概率分别是0.8和0.2，有3个符号输出时，符号序列与区域划分的对应关系图B 3符号输出时的 符号序列与区域划分示意,字符串 aabaa,对应的区域为 [0.512，0.59392),该区域的二进制表示 [0.1000001…，0.1001100 …),二进制数0.1001 输出编码 1001,因此,,,,对于这个信源：,相比Huffman编码，算术编码的编码效率有明显提高对于长序列，理论上算术编码可以达到信源的熵多元符号编码原理,输入符号串 s 取自符号集 ，,s 后跟 ai (ai∈S)扩展成符号串 sai ,空串记做 , 只有一个符号 ai 的序列就是 ai 算术编码的迭代公式：,① 码字刷新： C(sai) = C(s)+P(ai)A(s) (4.4-1a),② 区间刷新： A(sai) = p(ai)A(s) (4.4-2a),符号串每一步新扩展的码字 C(sai) 都是由原符号串的码字 C(s) 与新区宽度 A(sai) 的算术相加而得。

算术码”的由来,例4-9,设某信源取自符号集 S={a,b,c,d,e,!} , 各符号概率和初始区间如表4.4表4.4 固定模式举例,设待编码的字符串为单词“dead”，编码器和解码器都知道区间初值为[0,1]表4.5 6元信源的算术编码过程,编码过程如图4.6所示,编码端无需发送最后的区间范围 [0.61804, 0.6184) 实际上只要发送其间的某一个值即可, 如0.6181 解码端收到0.6181，得知区间范围为[0.4, 0.7) ，立即解得第一个字符为d，此后解码区间由初始[0,1)变为[0.4, 0.7)得到这一范围后，再对所有字符按照公式计算,并与最终的区间范围[0.61, 0.67) 相比较,得出第二个字符为e依此类推，解码器就唯一地解出字符串“dead！”解码过程,,,算术编码过程:,依据字符的发生概率对码区间的分割过程(即子区间宽度与正编码字符发生概率相乘的过程)算术解码过程:,只需知道最终编码区间中的某一个值就可以解码算术编码每次递推都要做乘法，而且必须在一个信源符号的处理周期内完成，有时难以实时，为此采用了查表等许多近似计算来代替乘法小结：,固定编码模式,概率统计与区间分配直接影响编码效率。

自适应模式,各符号的概率初始值都相同，但依据实际出现的符号而相应地改变两种编码模式：,二进制编码,编码对象是二元序列:,符号概率较小者为p(L)=2-Q形式, 以右移Q位代替乘2-Q;,符号概率较大者为p(H)=1-2-Q形式, 以移位和相减代替;,完全避免了乘法，因此算术编码很适合二元序列，而p(L)常用2-Q来近似从而算术编码的迭代公式在具体实现时的计算格式为：,① 码字刷新： C= C+P(ai)A (4.4-1b),② 区间刷新： A= p(ai)A (4.4-2b),有限长寄存器C实现C(s): 存在进位问题, 采用插入“填充位”解决, 对编码效 率略有影响;有限长寄存器A来实现A(s)实际中只能用,令 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)已经估计出的二进制算术编码的具体步骤如下:,① 初始化： , ;,如果A(sx)<0.10···0, 则A、C重复左移，直到A≥ 0.10···0为止(即保持A(s)的小数点后的第1位总是“1”);,⑤ 如果紧靠C的小数点前有连续v个“1”,则紧靠小数点前插 入1个“0”(填充位);,⑥ 按上述步骤对字符串中所有字符进行迭代运算,直到最 后一个字符输出C(s)代码。

参数q与Q的选择直接关系到编码器精度例4-10,对字符串“01000101”来说，H符号是“0”，L符号“1”：取q=4，v=3和Qmax=3，并假定由某个编码模型提供的Q(s)值为(2,1,2,2,3,1,1,2),对其进行算术编码字符串 s =“01000101” 可由最终子区间[0.11110101, 0.11111)表示,,编码端传送码字“1111011” 即可，码长7位二进制解码,解码只能逐字符译出:,检测移入C的v位码字: 如果发现“全1”,则检测第v+1位即填充位的值; 若该值为0, 说明无法进位, 则去掉该位“0”后正常解码; 若该值为1, 则删去这个填充的“1”、在v位码字最后一 位上加1做进位后再解码;,子区间宽度A(s)迭代： A(s’1)=A(s’)2-Q(s’) A(s’0)=〈A(s’)- A(s’1),① 置初值：A( s’ )=0.11···1;,⑤ 如果A(sx)<0.10 ··· 0, 则A、C重复左移，直到A≥ 0.10···0；,⑥ 按回到步骤②,直到解出x后面的所有字符Q(s)的确定与编码效率,不对称数Q(s),要从一个二进制序列 s 来确定 Q 值，有待于根据该序列的统计特性, 选择合适的概率模型。

例如根据符号串s后出现字符1 (L) 的条件概率来确定 Q 值4.4-9),p(L|s)简单记为p，意味着每个Q值要对应着一个概率区间 按2-Q编码，每个“L”需要Q位，每个“H”需要-log(1- 2-Q )位 则每个符号的平均码长：l(p)=pQ-(1-p)log(1- 2-Q ) (4.4-10),信源符号的熵为：H(p)=p log p-(1-p)log(1- p ) (4.4-11),用 2-Q 来近似所造成的编码效率的损失最大只有5%, 而计算量却可减少很多编码效率:,(4.4-13),表4.7 小概率用2-Q来近似时最坏情况下的编码效率,算术编码最鲜明的特点：,效率高,对于大部分黑白文件数据：,对一个具体序列:,平均编码效率约为98.5%,看其概率分布是否集中2-Q附近, 在p= 2-Q处, 编码效率为100%, 实际应用中的关键问题就是要选择合适的概率模型, 使大部分条件概率接近于2-Q算术码评述,能够自适应地估计条件概率, 从信源的统计特性 出发, 建立数据的概率模型。

它不必预先定义信 源的概率模型, 尤其适用于不可能进行概率统计 的场合;,适用于信源符号概率比较接近的场合，在几种主 要的统计编码中（Huffman，LZ家族以及算术编 码中），算术编码具有最高的压缩效率优点：,缺点：,比霍夫曼编码复杂，特别是硬件实现；,由于是变长码，也需要输入输出缓冲存储器， 只适用于分段信息；,误差扩散比分组码更严重，误码不会自动恢复， 会一直延续下去，传输要求高质量的信道，或 采用检错反馈重发的方式1,,基本原理,2,,霍夫曼编码,3,游程编码,4,算术编码,本章内容,,,5,基于字典的编码,6,哥伦布编码,,4.5 基于字典的编码,基于字典的压缩方法,将长度不同的符号串(短语)编码成一个个新单词, 用其形成一本短语词典的索引若单词的码长短于它所替代的短语，就实现了数据的无损压缩，而且该短语字典都是自适应生成的LZ码基本概念,1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 发表了论文“顺序数据压缩的一个通用算法”(A Universal Alogrithem for Sequential Data Compression)。

1978 年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(Compression of Individual Sequences via Variable-Rate Coding)在这两篇论文中提出的两个压缩技术被称为LZ77和LZ78简单地说LZ码思路完全不同于从Shannon到Huffman到算术压缩的传统思路，人们将基于这一思路的编码方法称作“字典”式编码LZ码,字典式编码不但在压缩效果上大大超过了Huffman编码，而且易于实现，其压缩和解压缩的速度也异常惊人LZ编码一例,英文字母和符号串编码成12位码字的压缩字符串表表4.8,LZ码的特点,能有效地利用字符出现频率冗余度、字 符重复性和高使用率模式冗余度，但通 常不能有效地利用位置冗余度；,算法是自适应的，无需有关输入数据统 计量的先验信息，运算时间正比于消息 的长度；,。