https://blog.csdn.net/shakingwaves/article/details/52426244
2016年09月03日 23:18:04
shakingwaves 阅读数：4260
2. 算术编码
与变长编码不同，算术编码的本质是为整个输入序列分配一个码字，而不是给每个字符分别指定码字，因此平均意义上可以为单个字符分配码长小于1的码字。
算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在L到H之间。编码过程中的间隔决定了符号压缩后的输出。
给定事件序列的算术编码步骤如下：
1. 编码器在开始时将“当前间隔”设置为[ L， H)；
2. 对每一事件，编码器按步骤a）和b）进行处理：
a) 编码器将“当前间隔”分为子间隔，每一个事件一个；
b) 一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”；
3. 最后输出的“当前间隔”的下边界和上边界之间的一个合适的值就是该给定事件序列的算术编码。
2.1. 浮点算术编码
在做算术编码前需要定义一个模型，有很多定义模型的算法，其主要目的都是为了能够精确的估计符号出现的概率，同时保证编码和解码的概率是一致的。为了简单起见，本节定义一个静态的概率模型：假设我们对大写字母进行编码，且前24个字母的概率为均为0.04，最后2个字母的概率均为0.02，如此，26个字母的概率之和为1。
按照以上定义，我们将[0，1)区间划分为26份，其中A拥有区间[0，0.04)，B拥有区间[0.04，0.08)，…，M拥有区间[0.48，0.52)，…，Y拥有区间[0.96，0.98) ，Z拥有区间[0.98，1)。
算术编码时，采用了子区间划分的方法，计算公式如下：
range =high – low； (1)
high =low + range * prob_high; (2)
low =low + range * prob_low； (3)
其中，range表示当前编码是区间大小，low和high分别表示当前区间的最小值和最大值，prob_low和prob_high分别表示当前待编码字符的概率区间的最小值和最大值。
假设我们编码“PASS”，由上述定义可知：“P”对应区间[0.6，0.64)，“A”对应区间[0，0.04)，“S”对应区间[0.72，0.76)，计算过程如图2所示。
1) 当编码“P”时，按照公式(1)、(2)和(3)计算如下：
range =1.0 – 0 =1；
high =0 + 1 * 0.64 = 0.64；
low =0 + 1 * 0.6 = 0.6；
2) 当编码“A”时，按照公式计算如下：
range = 0.64 – 0.6 = 0.04；
high =0.6 + 0.04 * 0.04 = 0.6016；
low =0.6 + 0.04 * 0 = 0.6；
3) 当编码“S”时，按照公式计算如下：
range = 0.6016 – 0.6 = 0.0016；
high =0.6 + 0.0016 * 0.76 = 0.601216；
low =0.6 + 0.0016 * 0.72 = 0.601152；
4) 当编码“S”时，按照公式计算如下：
range = 0.601216 – 0.601152 =0.000064；
high =0.601152 + 0.000064 * 0.76 = 0.60120064；
low =0.601152 + 0.000064 * 0.72 = 0.60119808；
图2. 编码“PASS”过程
从最后的结果可以看出，字符串“PASS”编码后的区间是[0.60119808，0.60120064)，从该区间中选择一个合适的值即可作为字符串“PASS”最终的算术编码值。
解码时使用和编码时类似的公式，如公式(4)、(5)、(6)和(7)。
range =high – low； (4)
c =(val - low) / range； (5)
high =low + range * c_prob_high； (6)
low =low + range * c_prob_low； (7)
假设我们最终选择了0.6012作为“PASS”算术编码后的值。其对应的解码过程如下所示：
1) high = 1；
low =0；
val =0.6012；
range = high – low = 1；
c = (val - low) / range = (0.6012 - 0) / 1 =0.6012，可知0.6012∈[0.6，0.64)，对应字符“P”，因此解码的第一个字符为“P”；
high = low + range * c_prob_high = 0 + 1 * 0.64 =0.64；
low = low + range * c_prob_low = 0 + 1 * 0.6 =0.6；
2) high = 0.64；
low =0.6；
val =0.6012；
range = high – low = 0.04；
c = (val - low) / range = (0.6012 – 0.6) / 0.04 = 0.03，可知0.003∈[0，0.04)，对应字符“A”，因此解码的第二个字符为“A”；
high = low + range * c_prob_high = 0.60 + 0.04 * 0.04 = 0.6016；
low = low + range * c_prob_low = 0.60 + 0.04 * 0 = 0.60；
3) high = 0.6016；
low =0.60；
val =0.6012；
range = high – low = 0.0016；
c = (val - low) / range = (0.6012 – 0.60) / 0.0016 = 0.75，可知0.75∈[0.72，0.76)，对应字符“S”，因此解码的第三个字符为“S”；
high = low + range * c_prob_high = 0.60 + 0.0016 * 0.76 = 0.601216；
low = low + range * c_prob_low = 0.60 + 0.0016 * 0.72 = 0.601152；
4) high =0.601216；
low =0.601152；
val =0.6012；
range = high – low = 0.000064；
c = (val - low) / range = (0.6012 –0.601152) / 0.000064 = 0.75，可知0.75∈[0.72，0.76)，对应字符“S”，因此解码的第四个字符为“S”；
high = low + range * c_prob_high = 0.601152 + 0.000064 * 0.76 = 0.60120064；
low = low + range * c_prob_low = 0.601152 + 0.000064 * 0.72 = 0.60119808；
经过以上步骤，就解码出了“PASS”字符串，但由于计算机的精度问题，浮点算术编码在实际情况下回带来诸多不便，因此在实际中使用的基本都是基于定点数的算术编码。
2.2. 定点算术编码
在浮点数编码时，区间被限定在[0，1)之间，做定点算术编码时，区间范围视寄存器位数而定，本节假设为32位的定点算术编码。
在浮点算术编码中：
low=0；
high=1.0；
在32位定点算术编码中，由于寄存器只能表示整数，因此我们假想在low和high的最前面有一个小数点存在。
即：
low = 0；
high = 0xFFFFFFFFU；
可以被假想为：
low = 0.0；
high = 0x0.FFFFFFFFU；
由于寄存器位数有限(本节假设为32位)，但是算术编码时需要的是一个无限趋近于1的一个数，因此：
low = 0.0；
high = 0x0.FFFFFFFFU；
进一步可以被假想为：
low = 0.00000000…；
high = 0x0.FFFFFFFF…U；
也就是说，我们可以假设在寄存器有限的精度之后还存在着无限多个后缀：low之后存在无限多个0，high之后存在无限多个F(针对16进制)或者无限多个1(针对二进制)，每次当寄存器中low的高位移出之后，低位都补0，high高位移出之后，低位都补1(因为，前面说high后有无限个F是针对16进制而言，针对移位操作而言，高位每移出一位二进制数，低位就补1)。
在浮点算术编码中，我们可以发现，随着编码的进行，在编码过程中将满足三个不变式：
a) low将单步递增；
b) high将单步递减；
c) high >= low；
在满足以上三个条件的基础上，一旦high的二进制最高位为0，那么它将在以后的编码过程中保持不变，同理，low的二进制最高位为1，那么它在以后的编码过程中也不会发生变化。由于寄存器的位数有限，为了充分的利用寄存器进行接下来的编码，当high和low的二进制最高位相同的时候，可以将他们移出寄存器，保存起来，然后将low末尾的无穷个0移进一位到low的最低位，从high末尾的无限个1移进一位到high的末尾，如此这样可以保证寄存器的位数被充分利用，且不会造成算法错误。
下面以定点算术编码方式来编码上面的“PASS”字符串如下：
1) 编码“P”字符时low和high值如下，这里为了简单直接用概率与区间大小相乘，编码后寄存器状态如图3所示：
range = 0xffffffff；
low = 0.6 *0xffffffff = 0x99999999；
high = 0.64 * 0xffffffff = 0xa3d70a3c；
图3. 编码“P”字符后寄存器状态
由上面分析可知，low和high的前两位都不再发生变化，因此可以直接移出寄存器存储起来，同时将尾部的0移入low，将尾部的1移入high。经过移出和移入操作后，low和high值如下：
low =0x66666664；
high =0x8f5c28f3；
2) 编码“A”字符时，low和high值如下公式所示，移出移入后寄存器状态如图4所示，“Emitted”部分移出了6个比特，其中最高2比特是在第一步操作中移出的；
range = high – low = 0x8f5c28f3 – 0x6666664 =0x28f5c28f；
high = low + 0.04 * range = 0x66666664+ 0.04 * 0x28f5c28f = 0x6809d493；
low =low + 0 * range = 0x66666667；
图4. 编码字符“A”后寄存器状态
按照同样的原理可以得出编码第一个字符“S”和第二个字符“S”后寄存器状态如图5(a)和5(b)所示。
(a)编码第一个字符“S”后寄存器状态
(b)编码第二个字符“S”后寄存器状态图5. 编码字符“S”后寄存器状态2.3. 区间缩放
为了充分利用寄存器有限的位宽，保证计算精度，定点算术编码的同时结合了区间缩放。在上一节中，提到的当low和high最高位相同时可以移出寄存器，同时在末尾移入0或1，就属于区间缩放中的两种情况。定点数算术编码中区间缩放一共分为三种。
1) 当low的最高位为1时，也就是low > mid时，由于high > low这个不变式一直成立，因此high的最高位也是1，此时可以将high和low的最高位移出，也就是将high和low左移一位，同时低位补上相应的1和0。由于high和low都左移一位，相当于对区间进行了第一种情况的缩放，如图6(a)所示。此时类似于：
low = (low – 0.5) * 2；
high = (high – 0.5 * 2；
图3中编码后移出了二进制“10”，其中最高位移出的“1”就是这种情况。
2) 当high的最高位为0时，也就是high < mid时，由于high > low这个不变式一直成立，因此low的最高位也是0，此时可以将high和low的最高位移出，也就是将high和low左移一位，同时低位补上相应的1和0。由于high和low都左移一位，相当于对区间进行了第二种情况的缩放，如图6(b)所示。此时类似于：
low = low * 2；
high = high * 2；
图3中编码后移出了二进制“10”，其中次高位移出的“0”就是这种情况。
3) 当high的最高两位为“10”，而low的最高两位为“01”时，也就是low属于[1/4 full range，1/2 full range)这个区间，而high属于[1/2 full range，3/4 full range)时，需要将high的次高位“0”和low的次高位“1”移出寄存器，最高位都保持不变，同时记录下次高位移出的次数cnt。当遇到第一种方式的区间扩展时，向缓冲区输出一个1和cnt个0，作为算术编码的结果；当遇到第二种区间扩展方式时，向缓冲区输出一个0和cnt个1作为算术编码的结果。如图6(c)所示，其对应的公式如下。
low = (low – 0.25) * 2；
high = (high – 0.25 * 2；
(a) 第一种区间缩放
(b) 第二种区间缩放
(c) 第三种区间缩放图6. 算术编码区间缩放 对于第三种缩放形式，通过如下的例子来进行说明。我们仍然采用浮点数算术编码部分的概率模型，假设我们编码字符串“MMMMMMM”，也就是连续编码7个字符“M”，按照定点数算术编码的方式进行计算，可以得到如下结果。编码第一个字符“M”之后： low = 0x7ae147ad， high = 0x851eb851， range = 171798692；编码第二个字符“M”之后： low = 0x7fcb9239， high = 0x80346dc4， range = 6871947；编码第三个字符“M”之后： low = 0x7ffde71f， high = 0x800218dd， range = 274878；编码第四个字符“M”之后： low = 0x7fffea84， high = 0x80001577， range = 10995；编码第五个字符“M”之后： low = 0x7fffff21， high = 0x 800000d9， range = 440；编码第六个字符“M”之后： low = 0x7ffffff4， high = 0x80000005， range = 17；编码第七个字符“M”之后： low = 0x7ffffffc， high=0x7ffffffc， range = 0。 从上面的编码字符“M”之后的low和high可以看出，前六次编码后的结果low和high都没有相同的最高位，且low和high无限趋近于中点值mid=0x80000000；同时还可以看出第六次之后range=17，但概率模型中一共存在26种字符(“A”~“Z”)，该range值太小，会导致无法为每个字符都分配独立的概率区间，因此是需要缩放的；且每次编码字符“M”后low的最高两位是“01”，high的最高两位是“10”，从第七次的编码结果来看，low和high最终的结果是0x7ffffffc，可以知道这也是符合第三种缩放的算法的，即一个0后有cnt个1，或者一个1后有cnt个0，至于cnt的数值大小，这里不再计算，可以按照第三种缩放算法的方式自行计算。
