算术编码与解码

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.，将它变成二进制 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){ //定义上下限

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(shu < low+sa/count * cha && shu >low+sb/count * cha){ }

//将译码结果存入字符串 info = info + deal.charAt(j); //得到新的上限

high = low + sa/count * cha; //得到新的下限

low = low + sb/count*cha; zifu[j]++;

}

//重置sa sa = 0; i++; }

//输出译码结果

System.out.println(info);

实验结果：（运行环境：win10）