参考了太多资料，没办法标明出处了。

算术编码有2种，静态的和自适应的，静态的要求预先知道编码字符的概率。下面主要讲讲自适应算数编码怎么应用到编程的。分为3步讲解：1、算术编码原型  2、规整化  3、重归一化

1、算术编码原型

算术编码：

算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于 0 和 1 之间的二进制小数。例如算术编码对某条信息的输出为 1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。

例子：数据范围为abc，要输出的数据为bccb，分为下面4步。

1、现在拿到第一个字符 b，由于对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），暂时认为三者的出现概率相等，也就是都为 1/3，将 0 - 1 区间按照概率的比例分配给三个字符，即 a 从 0.0000 到 0.3333，b 从 0.3333 到 0.6667，c 从 0.6667 到 1.0000。表示如下：

[0.0000, 0.3333)      [0.3333, 0.6667)       [0.6667, 1.0000)

Pa                            Pb                            Pc    

我们将为下一步分割做2步准备，第一：Pb对应的区间[0.3333, 0.6667)将成为下次要分割的区间。 第二：更新概率表，由于多了一个b，三个字符的概率变成：Pa = 1/4，Pb =2/4，Pc = 1/4。    

2、接着拿到字符c，我们将对上一步得到的新区间，即Pb[0.3333, 0.6667) 进行分配，字符概率上一步已经得出了，划分的结果表示如下：

[0.3333, 0.4167)      [0.4167, 0.5834)       [0.5834, 0.6667)

Pa                            Pb                            Pc 

同样为下一步分割做2步准备，第一：Pc对应的区间[0.5834, 0.6667)将成为下次要分割的区间。 第二：更新概率表，由于多了一个c，三个字符的概率变成：Pa = 1/5，Pb =2/5，Pc = 2/5。 

3、接着我们拿到字符c，我们将对上一步得到的新区间，即Pc[0.5834, 0.6667) 进行分配，字符概率上一步已经得出了，划分的结果表示如下：

[0.5834, 0.6001)      [0.6001, 0.6334)       [0.6334, 0.6667)

Pa                            Pb                            Pc 

同样为下一步分割做2步准备，第一：Pc对应的区间[0.6334, 0.6667)将成为下次要分割的区间。 第二：更新概率表，由于多了一个c，三个字符的概率变成：Pa = 1/6，Pb =2/6，Pc = 3/6。

4、现在输入最后一个字符b，我们将对上一步得到的新区间，即Pc[0.6334, 0.6667) 进行分配，字符概率上一步已经得出了，划分的结果表示如下：

[0.6334, 0.6390)      [0.6390, 0.6501)       [0.6501, 0.6667)

Pa                            Pb                            Pc 

Pb[0.6390, 0.6501)是我们得到的最后区间，在这个区间内随便选择一个容易变成二进制的数，例如 0.64，将它变成二进制 0.1010001111，去掉前面没有太多意义的 0 和小数点，我们可以输出 1010001111，这就是信息被压缩后的结果。

 

算术解码详解：

知道了压缩算法，解压过程就比较简单了。

1、同编码第1步得到如下概率分布:

[0.0000, 0.3333)      [0.3333, 0.6667)       [0.6667, 1.0000)

Pa                           Pb                             Pc 

输出值0.64在Pb里，得到数据b;

2、同编码第2步得到如下概率分布:

[0.3333, 0.4167)      [0.4167, 0.5834)       [0.5834, 0.6667)

Pa                            Pb                            Pc  

输出值0.64在Pc里，得到数据c;

3、同编码第3步得到如下概率分布:

[0.5834, 0.6001)      [0.6001, 0.6334)       [0.6334, 0.6667)

Pa                            Pb                            Pc  

输出值0.64在Pc里，得到数据c;

4、同编码第4步得到如下概率分布:

[0.6334, 0.6390)      [0.6390, 0.6501)       [0.6501, 0.6667)

Pa                            Pb                            Pc 

输出值0.64在Pb里，得到数据b;

5、继续划分，上一步得到的新区间[0.6390, 0.6501)，三个字符的概率变成：Pa = 1/7，Pb =3/7，Pc = 3/7。 得到如下概率分布: 

[0.6334, 0.64058)      [0.64058, 0.64533)       [0.64533, 0.6501)

Pa                             Pb                                 Pc

然后呢，问题来了，会无限制的划分下去。我们要引入下面的概念，称为规整化吧。

 

2、规整化

像上面使用无限精度的分数，计算概率区间范围，然后在编码结束的时候将这个分数转换成二进制形式的方法是不可行。算术编码器应该使用优先精度的数值计算，而不是去模拟无限精度的分数，因为它们知道解码器能够匹配。该方法本质就是把小数的操作转化为整数的操作。

我们用4位整数模拟一下。如下只列出映射区间:

输入数据    当前数据       映射区间                 区间长度                

开始                               [0000，9999]         10000  

B                B                 [3333，6665]          3333

BC              C                 [5832，6665]          834

BCC            C                 [6332，6665]          334

BCCB          B                 [6387，6498]          112

我们现在是不是可以用[6387，6498]里的一个整数表示压缩值了呢。这样做的问题在于，区间长度不断减小，最后会变成0，就完蛋了。所以我们要引入另一个概念，称为重归一化。

 

3、重归一化

所谓重归一化是当区间长度小到一定值时，把上下沿相同的最高位输出，改变上下沿的值，扩大区间长度。对于上面的例子，还有后续数据的话，可以把千位6输出，区间扩大到[3870, 4980]，这样说只是为了让读者有个直观的印象，编程的时候不会这样做。正确的做法是把上下沿相同的最高位输出，最高位指的是二进制位。把上下沿和区间长度都左移相应位数。这样既能保证改变后的上沿值一定大于下沿值，还能方便的求出改变后的区间长度。定义下沿为L,上沿为H,区间长度为R，精度为p。以p=8为例，正常情况是：

L 00101101   或   10101101

H 01001011        11001011 

此时移除最高位作为输出码流，再把L、H、R左移一位即可。把高位都为0的情况简称HB0,高位都为1的情况简称HB1。

但是有一种特殊情况，如下：

L 01111111   

H 10000000

此时L和H最高位不相同，但区间长度已为1，无法再继续编码了。所以在最高位不相同时，我们还要关心次高位。如下：

L 01xxxxxx   

H 10xxxxxx

这种情况简称为HB3。

下面画出这3种情况的L、H范围:

 http://s11/bmiddle/0065Tpbqgy6Uf6H7hDs4a&690

HB3的处理：出现HB3情况时，我们并不知道次高位的趋向。只能忽略次高位，并记录连续忽略的次数c。直到出现HB0或HB1，出现HB0时说明次高位趋向0，应该输出一个0和c个1，出现HB1时说明次高位趋向1，应该输出一个1和c个0。

这种方法每次都要判断最高2位，我们引入阈值的概念，设阈值为(1 << (p - 1))，如果R小于阈值(1 << (p - 1))，认为L和H的最高位相同，最高位作为输出编码流，同时把L和R左移一位即可。但仅仅是认为L和H的最高位相同，其实也会出现HB3，这时L和R左移一位后再继续求新的L和R，会出现L的值大于(1 << p)的情况，称为进位。进位时L值的有效位为p + 1，最高位的1实际上是已输出码流的最后一位，所以需要对已输出码流加1。这样做为什么和分为HB0、HB1、HB3三种情况等价呢？希望弄明白了的给我补充一下。

算术编码的实数区间为[L, H],R为区间长度H - L。更新实数区间的方程为:

L(i + 1) = L(i) + R * (S(i) / S);

H(i + 1) = L(i) + R * (S(i + 1) / S);

R(i + 1) = H(i + 1) - L(i + 1);

其中S为数据的整体频率，假设第i + 1个数据为C, S(i + 1)为C及C之前数据(这里说的之前数据是指频率表里的位置，并非输入的数据)的累积频率，S(i)为C之前的数据的累积频率。对于上面的例子，字符在频率表的位置顺序为a、b、c。累积频率如下：

I值     当前数据/频率表前的数据   S     S(i)     s(i + 1)              

1        B/A                       3     1        2

2        C/AB                      4     3        4

3        C/AB                      5     3        5

4        B/A                       6     1        3  

由上面分析可知，实际编程时只需L和R。方程简化如下：  

L(i + 1) = L(i) + R * (S(i) / S);

R(i + 1) = R * ((S(i + 1) / S) - S(i) / S);

阈值为(1 << (p - 1))时，一次产生1bit的编码流数据，效率比较慢。我们把阈值变为(1 << (p - 8))，一次输出8bit的编码流。

下面程序里，用temp表示L << (p - 8)后的数据。用buf保存要输出的不为0xFF的编码流，用c表示输出码流为0xFF的次数，z表示是否进位。

temp值会出现如下3种情况。

1、temp < 0xFF：把temp值给buf。

2、temp == 0xFF：c++。

3、temp > 0xFF：z赋值1。

Encode_initialize()

{

    Unsigned int p = 16;

    Unsigned int L = 0;

    Unsigned int R = 1 << p;

    byte buf = -1;

    byte c = 0;

    byte z = 0;

}

Encode()

{

    Encode_Update();

    Encode_Renormalize();

}

Encode_Update()

{

    L(i + 1) = L(i) + R * (S(i) / S);

    R(i + 1) = R * ((S(i + 1) / S) - S(i) / S);

    Temp = L >> (p - 8);

    if (temp > 0xff)     //进位

    {

        Buf += 1;

        L -= (1 << p);

        Z = 1;

    }

}

Encode_Renormalize()

{

    While(R < (1 << (p - 8)))

    {

         Temp = L >> (p - 8);

         if (temp < 0xff)

         {

             //输出上次的编码流

             If (buf > 0)

             {

                 Put_Byte(buf);   //输出编码流

             }

             While(c > 0)   //输出编码流里的0xFF

             {

                 If(z == 1)

                 {

                     Put_Byte(0);   //输出编码流

                 }

                 Else

                 {

                     Put_Byte(0xFF);   //输出编码流

                 }

                 C--;

             }

              //获取本次的编码流

             Buf = temp;

         }

         Else if (temp == 0xff)

         {

             C++;

         }

         R <<= 8;

         L = (L << 8) & ((1 << p) - 1); //左移8位，并保证有效位为p。

         Z = 0;

    }

}

有几点要指出：

1、上面未给出计算符号累积频率的代码，在统计累积频率的数据结构中，二进制索引树结构是目前公认最快的，网上有资料，大家可以自己研究一下。

2、输入最后一个数据后，如果R值出现这种情况：(1 << (p - 8)) <= R < (1 << (p - m))其中0 <= m < 8。这时不满足重归一化的条件，但L的p - 7位到p - m为将要输出的编码流，该怎样处理这几位数据呢？希望弄明白的人给我补充一下。

3、图片压缩时只编码数据0和1，为了提高效率引进2个概率：MPS(More Probable Symbol)大概率符号，LPS(Less Probable Symbol)小概率符号，并规定MPS始终处于区间下部。当MPS和LPS改变时需求重新求L和R。网上有资料(公开库jbig.c里有相关代码实现)，大家自己研究吧。

 

解码过程需要引入2个变量，V存放压缩数据，pOut数组存放解码数据，过程如下：

Decode_initialize()

{

    Unsigned int L = 0;

    Unsigned int R = 1 << p;

    V初始为编码流数据最前b bit数据。

}

Decode()

{

    Decode_Get_Symbol();

    Decode_Update();

    Decode_Renormalize();

}

Decode_Get_Symbol()          //获取解码字符

{

    If(V < L)     //进位

    { 

        V += (1 << b);

    }

    T = (V - L + 1) * S / R;    //变量T表示字符对应的累积频率值。

    在频率表找到T对应的字符放入pOut里，并更新频率表。

}

Decode_Update()

{

    实现同Encode_Update()

}

Decode_Renormalize()

{

    While(R < (1 << (p - 8)))

    {

        R <<= 8;

        L = (L << 8) & ((1 << p) - 1); //左移8位，并保证有效位为p。

        V = (V << 8) & ((1 << p) - 1); //左移8位，并保证有效位为p。

        从编码流读取8 bits，放入V的低8位里。

    }

}