输入文件：in2.txt
输出文件：out2.txt
结果分析：对n个符号序列进行游程编码后输出“0”游程长度和“1”游程长度，再对结果进行霍夫曼编码，得到游程编码结果的霍夫曼码。然后进行译码，首先的是霍夫曼译码，得到游程编码结果，再进行游程译码，得到原符号序列。第二组符号序列编码译码过程相同。
5. 设计体会
游程编码相对简单，首先计算每次连续相同字符的个数，然后将每次连续相同的字符及个数保存起来，再使用霍夫曼编码。霍夫曼编码用概率匹配方法进行信源编码，有两个明显的特点：一是霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长吗，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，从而保证霍夫曼编码是即时码。完成哈夫曼的编码首先建立哈夫曼树，定义当前节点的字符，当前节点的左子、右子和父亲指针，之后对所有字符根据权重进行编码（先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点），最后再对文件内容进行编码。
三、算术编码的编码与译码
1. 任务说明
要求：输入字符集为{a,b},且p(a)=1/4,p(2)=3/4.对长度L<=30的序列进行算术编码,并进
反向译码
输入文件:in3.txt，含至少两组输入，每组为满足要求的串 输出文件:out3.txt，对每组输入的编码和译码结果
2. 实现原理
算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。
给定事件序列的算术编码步骤如下：
（1）编码器在开始时将“当前间隔” [ L， H) 设置为[0，1)。 （2）对每一事件，编码器按步骤（a）和（b）进行处理
（a）编码器将“当前间隔”分为子间隔，每一个事件一个。
（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔 对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。 （3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。
3. 实现源码
#include
#pragmawarning(disable:4996) usingnamespace std; #include\
char S[100], A[10]; //用户的码字、保存输入字符 float P[10], f[10], gFs; //字符概率 char bm[100], jm[100]; fstream in(\); fstream out(\);
//编码程序
void bianma(int a, int h) { int i, j; float fr; float ps = 1; float Fs = 0; float Sp[100];
//以待编码的个数和字符个数为循环周期?将待编码的字符所对应的概率存入到Fs中 for (i = 0; i
fr = f[j];//将划分好的[0,1)区间的对应点赋值给fr } } Fs = Fs + ps*fr;//从选择的子区间中继续进行下一轮的分割。不断的进行这个 过程?直到所有符号编码完毕。 ps *= Sp[i]; //求Ps }
cout <<\<< Fs << endl;//显示最终的算术编码 gFs = Fs;
out <<\算术编码结果：?\<< endl; out <<\<< Fs << endl;
float l = log((float)1 / ps) / log((float)2);//计算算术编码的码字长度l if (l>(int)l)l = (int)l + 1;
else l = int(l);//将Fs转换成二进制的形式 int d[20]; int m = 0; while (l>m) { Fs = 2 * Fs; if (Fs>1) { Fs = Fs - 1; d[m] = 1; } elseif (Fs<1)d[m] = 0; else { d[m] = 1; break; } m++; }
int z = m;
//解决有关算术编码的进位问题,给二进制数加 if (m >= l) { while (1) { d[m - 1] = (d[m - 1] + 1) % 2;//最后位加 if (d[m - 1] == 1)break; else m--; } }
cout <<\; out <<\;
for (int e = 0; e < z; e++) { cout << d[e];
}
out << d[e]; }
cout << endl; out << endl;
//解码程序
void jiema(int a, int h) { int i; float Ft, Pt; float Fs = 0, Ps = 1; out <<\算数译码后：\; for (i = 0; i
void main() { cout <<\编码个数\; int a, i, h = 0; in >> a; cout << a << endl; cout <<\输入编码符号和概率值\<< endl; for (i = 0; i < a; i++) {
}
char x; float y; in >> x; cout << x; A[i] = x;//将字符依次存入数组A中 in >> y; cout << y << endl; P[i] = y;//将字符所对应的概率依次存入到数组P中 }
for (i = 1; i < a; i++) { f[0] = 0; f[i] = f[i - 1] + P[i - 1];//将要编码的数据映射到一个位于[0,1)的实数区间中 }
while (!in.eof()) { cout <<\输入需要编码的符号序列，同时用$结尾?\<< endl; h = 0; while (1)//这个while语句的作用是将要编码的字符存入到数组S中 { char cc; in >> cc; if (cc == '$') break;//在以“$”为结尾的时候结束存储 S[h++] = cc; cout << cc; } cout << endl; cout <<\算术编码结果：?\<< endl; bianma(a, h); cout <<\对应的解码结果：?\<< endl; jiema(a, h); system(\); }
in.close(); out.close();
4. 运行结果
输入文件：in3.txt
说明：第一行表示信源符号个数；第二行表示第一个信源符号及其概率，下一行表示第二个信源符号及其概率（若不止两个信源符号也可写入输入文件）。接下来为待编码的码符号序列，每一组以“$”符号结尾。
输出文件：out3.txt
结果分析：对每一组码符号序列输出算术编码的结果，包括累积分布函数和码字，再对该码字进行算术译码，得到原符号序列（观察是否与原来的一致）。因为符号序列在这里较短，压缩的效果不够明显。
5. 设计体会
在课程学习时对于算术编码没有去详细地了解它的编码方法以及实现，在做这个实验的时候，通过一点点地去看去设计，终于对算术编码有了深入的了解。算术编码的设计更多的用到数学计算，通过实现累计分布函数和信源符号序列所对应区间宽度即可完成算术编码的核心部分，依据书上给出的递推公式，实现难度不是很大，得到累积分布函数后还要依据计算出的长度l取其小数点后l位，还要考虑进位的问题。有了编码的铺垫，译码则显得容易的多，进行逆编码即可。在设计的过程中，可以发现算术编码效率很高，编译码的速度也很快。