算术编码原理与实现【转载】
1. 算术编解码原理
编码
与哈夫曼编码一样，算数编码是熵编码的一种，是基于数据中字符出现的概率，给不同字符以不同的编码。
算数编码的原理我个人感觉其实并不太容易用三言两语直观地表达出来，其背后的数学思想则更是深刻。当然在这里我还是尽可能地将它表述，并着重结合例子来详细讲解它的原理。
简单来说，算数编码做了这样一件事情：
- 假设有一段数据需要编码，统计里面所有的字符和出现的次数。
- 将区间 [0,1) 连续划分成多个子区间，每个子区间代表一个上述字符， 区间的大小正比于这个字符在文中出现的概率 p。概率越大，则区间越大。所有的子区间加起来正好是 [0,1)。
- 编码从一个初始区间 [0,1) 开始，设置:
- 不断读入原始数据的字符，找到这个字符所在的区间，比如 [ L, H )，更新:
- 最后将得到的区间 [low, high)中任意一个小数以二进制形式输出即得到编码的数据。
乍一看这些数学和公式很难给人直观理解，所以我们还是看例子。例如有一段非常简单的原始数据：
ARBER
统计它们出现的次数和概率：
| Symbol | Times | P |
|---|---|---|
| A | 1 | 0.2 |
| B | 1 | 0.2 |
| E | 1 | 0.2 |
| R | 2 | 0.4 |
将这几个字符的区间在 [0，1) 上按照概率大小连续一字排开，我们得到一个划分好的 [0，1)区间：
开始编码，初始区间是 [0，1)。注意这里又用了区间这个词，不过这个区间不同于上面代表各个字符的概率区间 [0，1)。这里我们可以称之为编码区间，这个区间是会变化的，确切来说是不断变小。我们将编码过程用下图完整地表示出来：
拆解开来一步一步看：
-
刚开始编码区间是 [0，1)，即
-
第一个字符A的概率区间是 [0，0.2)，则 L = 0，H = 0.2，更新
-
第二个字符R的概率区间是 [0.6，1)，则 L = 0.6，H = 1，更新
-
第三个字符B的概率区间是 [0.2，0.4)，则 L = 0.2，H = 0.4，更新
-
…
上面的图已经非常清楚地展现了算数编码的思想，我们可以看到一个不断变化的小数编码区间。每次编码一个字符，就在现有的编码区间上，按照概率比例取出这个字符对应的子区间。例如一开始A落在0到0.2上，因此编码区间缩小为 [0，0.2)，第二个字符是R，则在 [0，0.2)上按比例取出R对应的子区间 [0.12，0.2)，以此类推。每次得到的新的区间都能精确无误地确定当前字符，并且保留了之前所有字符的信息，因为新的编码区间永远是在之前的子区间。最后我们会得到一个长长的小数，这个小数即神奇地包含了所有的原始数据，不得不说这真是一种非常精彩的思想。
解码
如果你理解了编码的原理，则解码的方法显而易见，就是编码过程的逆推。从编码得到的小数开始，不断地寻找小数落在了哪个概率区间，就能将原来的字符一个个地找出来。例如得到的小数是0.14432，则第一个字符显然是A，因为它落在了 [0，0.2)上，接下来再看0.14432落在了 [0，0.2)区间的哪一个相对子区间，发现是 [0.6，1)， 就能找到第二个字符是R，依此类推。在这里就不赘述解码的具体步骤了。
编程实现
算数编码的原理简洁而又精致，理解起来也不很困难，但具体的编程实现其实并不是想象的那么容易，主要是因为小数的问题。虽然我们在讲解原理时非常容易地不断计算，但如果真的用编程实现，例如C++，并且不借助第三方数学库，我们不可能简单地用一个double类型去表示和计算这个小数，因为数据和编码可以任意长，小数也会到达小数点后成千上万位。
怎么办？其实也很容易，小数点是可以挪动的。给定一个编码区间，例如从上面例子里最后的区间 [0.14432，0.1456)开始，假定还有新的数据进来要继续编码。现有区间小数点后的高位0.14其实是确定的，那么实际上14已经可以输出了，小数点可以向后移动两位，区间变成 [0.432，0.56)，在这个区间上继续计算后面的子区间。这样编码区间永远保持在一个有限的精度要求上。
上述是基于十进制的，实际数字是用二进制表示的，当然原理是一样的，用十进制只是为了表述方便。算数编码／解码的编程实现其实还有很多tricky的东西和corner case，我当时写的时候debug了好久，因此我也建议读者自己动手写一遍，相信会有收获。
2.算术编码实现（C++）
#include <iostream>
#define M 100
#define N 4
using namespace std;
class suanshu
{
int count, length;
char number[N], n;
long double chance[N], c;
char code[M];
long double High, Low, high, low, d;
public:
suanshu()
{
High = 0; Low = 0;
}
void get_number();
void get_code();
void coding();
void jiema();
~suanshu(){}//此为析构函数 作用就是对象离开生存空间时执行的,用来清理分配的空间之类
};
void suanshu::get_number()
{
cout << "please input the number and its chance." << endl;
int i = 0;
for (; i < N; i++)
{
cin >> n >> c;
number[i] = n;
chance[i] = c;
}
if (i == 20)
cout << "the number is full." << endl;
count = i;
}
void suanshu::get_code()
{
cout << "please input the code's length:";
cin >> length;
while (length >= M)
{
cout << "the length is too larger,please input a smaller one.";
cin >> length;
}
cout << "输出的code:";
for (int i = 0; i < length; i++)
{
cin >> code[i];
}
}
void suanshu::coding()
{
//找到第一个字符的编码区间
int i, j = 0;
for (i = 0; i < count; i++)//判断第一个字符下标
if (code[0] == number[i]) break;
while (j < i)//寻找第一个字符的概率区间上下限
Low += chance[j++];
d = chance[j];
High = Low + d;
for (i = 1; i < length; i++)//需要编码的字符串
for (j = 0; j < count; j++)//对应编码的字符及其概率
{
if (code[i] == number[j])
{
if (j == 0)//若第二个字符为'A'
{
low = Low;
high = Low + chance[j] * d;
High = high;
d *= chance[j];
}
else//若第二个字符为其它字符
{
long double chance_l = 0.0;
for (int k = 0; k <= j - 1; k++)
chance_l += chance[k];
low = Low + d*chance_l;
high = Low + d*(chance_l + chance[j]);
Low = low;
High = high;
d *= chance[j];
}
}
else continue;//未在字典的字符
}
cout << "the result is:" << Low << endl;
}
void suanshu::jiema()
{ // Low=(Low+High)/2;
int i, j;
char out[10];//解码字符数不超过10个
for (i = 0; i < length; i++)//逐个解码字符
{
long double m0 = 0.0;
long double m1 = 0.0;
for (j = 0; j < count; j++)
{
//不断改变编码区间进行判断
m0 = m1;
m1 = m0 + chance[j];
//cout<<Low<<m0<<m1<<endl;
if ((Low >= m0) && (Low < m1))//Low即为算术编码的最终结果
{
out[i] = number[j];
Low -= m0;
Low = Low / (chance[j]);
break;
}
continue;//未在字典的字符
}
cout << out[i];
}
cout << endl;
}
int main()
{
suanshu a;
a.get_number();//获取字符和概率
a.get_code();//获取待编码的字符串
a.coding();//
a.jiema();
system("pause");
return 0;
}
实验结果
以上博文整理自：