算术编码与解码

算术编码与解码

1、编码过程

算术编码方法是将被编码的一则消息或符号串（序列）表示成0和1之间的一个间隔（Interval），即对一串符号直接编码成[0,1]区间上的一个浮点小数。符号序列越长，编码表示它的间隔越小，表示这一间隔所需的位数就越多。信源中的符号序列仍然要根据某种模式生成概率的大小来减少间隔。可能出现的符号概率要比不太可能出现的符号减少范围小，因此，只正加较少的比特位。

在传输任何符号串之前，0符号串的完整范围设为[0,1]。当一个符号被处理时，这一范围就依据分配给这一符号的那一范围变窄。算术编码的过程，实际上就是依据信源符号的发生概率对码区间分割的过程。

输入：一个字符串

输出：一个小数

考虑某条信息中可能出现的字符仅有a b c 三种，要压缩保存的信息为bccb。

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

+-- 1.0000 | Pc = 1/3 | | +-- 0.6667 | Pb = 1/3 | | +-- 0.3333 | Pa = 1/3 | | +-- 0.0000

对于第一个字符b，选择b 对应的区间0.3333 - 0.6667。这时由于多了字符b，三个字符的概率分布变成：Pa = 1/4，Pb = 2/4，Pc = 1/4。再按照新的概率分布比例划分0.3333 - 0.6667 这一区间，划分的结果可以用图形表示为：

+-- 0.6667 Pc = 1/4 | +-- 0.5834 | | Pb = 2/4 | | | +-- 0.4167 Pa = 1/4 | +-- 0.3333

接着字符c，上一步中得到的 c 的区间0.5834 - 0.6667。新添了c 以后，三个字符的概率分布变成Pa = 1/5，Pb = 2/5，Pc = 2/5。用这个概率分布划分区间0.5834 - 0.6667：

+-- 0.6667 | Pc = 2/5 | | +-- 0.6334 | Pb = 2/5 | | +-- 0.6001 Pa = 1/5 | +-- 0.5834

现在输入下一个字符c，三个字符的概率分布为：Pa = 1/6，Pb = 2/6，Pc = 3/6。划分c 的区间0.6334 - 0.6667：

+-- 0.6667 | | Pc = 3/6 | | | +-- 0.6501 | Pb = 2/6 | | +-- 0.6390 Pa = 1/6 | +-- 0.6334

输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的 b 的区间为0.6390 - 0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前面没有太多意义的0 和小数点，我们可以输出1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程。我的代码：

publicstaticvoidBianMa(String info,StringDeal sd){

int i = 0, j = 0;

//定义上下限

double low = 0, high = 1;

double count = sd.getCount();

//定义初始各字符频率

double[] zifu = new double[(int)(count)];

for(i = 0;i < zifu.length;i++){

zifu[i] = 1;

}

String deal = sd.getDeal();

for(i = 0;i < info.length();i++){

//得到频率范围

double cha = high - low;

double sa = 0;

for(j = 0; j < deal.length(); j++){

//sa表示频率上限分子

sa += zifu[j];

//sb表示频率下限分子

double sb = sa - zifu[j];

if(info.charAt(i) == deal.charAt(j)){

//得到新的上限

high = low + sa/count * cha;

//得到新的下限

low = low + sb/count*cha;

zifu[j]++;

}

} //重置sa为0

sa = 0;

//频率分母

count++; }

shu = (low+high)/2;

System.out.println(shu);

}

2、解码过程

解码是编码的逆过程，对应每个频率范围，若输入位于某各字符的频率范围之内，则将该字符记录，并得到新的上下限。

我的代码：

publicstaticvoid JieMa(StringDeal sd,double shu){

//定义上下限

double low = 0, high = 1;

double count = sd.getCount();

int j = 0, i =0;

String deal = sd.getDeal();

//定义一个初始字符串存储译码结果

String info = "";

//字符初始字符量设置为1

double[] zifu = newdouble[(int)(count)];

for(i = 0;i < zifu.length;i++){

zifu[i] = 1;

}

while((low+high)/2 != shu){

//定义上下限