算术编码的C++实现

算术编码的C++实现#includeiostream#includestring#includecstring#includevectorusingnamespacestd;#defineN50//输入的字符应该不超过50个structL//结构用于求各字符及其概率{charch;//存储出现的字符（不重复）intnum;//存储字符出现的次数doublef;//存储字符的概率};//显示信息voiddisp();//求概率函数，输入：字符串；输出：字符数组、字符的概率数组;返回：数组长度；intproba(stringstr,charc[],longdoublep[],intcount);//求概率的辅助函数intsearch(vectorLarch,char,intn);//编码函数，输入：字符串，字符数组，概率数组，以及数组长度；输出：编码结果longdoublebma(charc[],longdoublep[],stringstr,intnumber,intsize);//译码函数，输入：编码结果，字符串，字符数组，概率数组，以及它们的长度；输出：字符串//该函数可以用于检测编码是否正确voidyma(stringstr,charc[],longdoublep[],intnumber,intsize,longdoubleinput);intmain(){stringstr;//输入要编码的String类型字符串intnumber=0,size=0;//number--字符串中不重复的字符个数；size--字符串长度charc[N];//用于存储不重复的字符longdoublep[N],output;//p[N]--不重复字符的概率，output--编码结果disp();cout输入要编码的字符串:;getline(cin,str);//输入要编码的字符串size=str.length();//字符串长度number=proba(str,c,p,size);//调用求概率函数，返回不重复字符的个数cout.setf(ios::fixed);//“魔法配方”规定了小数部分的个数cout.setf(ios::showpoint);//在此规定编码结果的小数部分有十个cout.precision(10);output=bma(c,p,str,number,size);//调用编码函数，返回编码结果yma(str,c,p,number,size,output);//调用译码函数，输出要编码的字符串，//以验证编码是否正确return0;}//显示信息voiddisp(){coutendl;cout********************算术编码*********************\n;cout*****************作者：heiness******************\n;coutendl;cout此程序只需要输入要编码的字符串，不需要输入字符概率\n;coutendl;}//求概率函数intproba(stringstr,charc[],longdoublep[],intcount){cout.setf(ios::fixed);//“魔法配方”规定了小数部分位数为三位cout.setf(ios::showpoint);cout.precision(3);vectorLpt;//定义了结构类型的向量，用于同时存储不重复的字符和其概率Ltemp;//结构类型的变量temp.ch=str[0];//暂存字符串的第一个字符，它的个数暂设为1temp.num=1;temp.f=0.0;pt.push_back(temp);//将该字符及其个数压入向量for(inti=1;icount;i++)//对整个字符串进行扫描{temp.ch=str[i];//暂存第二个字符temp.num=1;temp.f=0.0;for(intj=0;jpt.size();j++)//在结构向量中寻找是否有重复字符出现{//若重复，该字符个数加1，并跳出循环intk;//若不重复，则压入该字符，并跳出循环k=search(pt,str[i],pt.size());if(k=0){pt[k].num++;break;}else{pt.push_back(temp);break;}}}for(i=0;ipt.size();i++)//计算不重复字符出现的概率{pt[i].f=double(pt[i].num)/count;}intnumber=pt.size();//计算不重复字符出现的次数cout各字符概率如下：\n;for(i=0;inumber;i++)//显示所得的概率，验证是否正确{if(count==0){coutNOsample!\n;}else{c[i]=pt[i].ch;p[i]=pt[i].f;coutc[i]的概率为：p[i]endl;}}returnnumber;//返回不重复字符的个数}//求概率的辅助函数//若搜索发现有重复字符返回正数//否则，返回-1intsearch(vectorLarch,charch1,intn){for(inti=0;in;i++)if(ch1==arch[i].ch)returni;return-1;}//编码函数longdoublebma(charc[],longdoublep[],stringstr,intnumber,intsize){longdoubleHigh=0.0,Low=0.0,high,low,range;//High--下一个编码区间的上限，Low--下一个编码区间的下限；//high--中间变量，用来计算下一个编码区间的上限；//low--中间变量，用来计算下一个编码区间的下限；//range--上一个被编码区间长度inti,j=0;for(i=0;inumber;i++)if(str[0]==c[i])break;//编码第一个字符while(ji)Low+=p[j++];//寻找该字符的概率区间下限range=p[j];//得到该字符的概率长度High=Low+range;//得到该字符概率区间上限for(i=1;isize;i++)//开始编码第二个字符for(j=0;jnumber;j++)//寻找该字符在c数组中的位置{if(str[i]==c[j]){if(j==0)//若该字符在c数组中的第一个字符{low=Low;//此时该字符的概率区间下限刚好为零high=Low+p[j]*range;High=high;range*=p[j];//求出该字符的编码区间长度}else//若该编码字符不是c数组中的第一个{floatproba_next=0.0;for(intk=0;k=j-1;k++)proba_next+=p[k];//再次寻找字符的概率区间下限low=Low+range*proba_next;//编码区间下限high=Low+range*(proba_next+p[j]);//编码区间上限Low=low;//编码区间下限High=high;//编码区间上限range*=p[j];//编码区间长度}}elsecontinue;//i++，编码下一个字符}coutendl;cout输入字符串的编码为:Lowendl;returnLow;}//译码函数voidyma(stringstr,charc[],longdoublep[],intnumber,intsize,longdoubleinput){vectorcharv;//定义char类型向量vlongdoubletemp;//中间变量longdoublesum[N];//存储不重复字符概率区间的下限sum[0]=0.0;//数组第一个元素为0for(inti=1;inumber+1;i++)//计算数组各元素的值{sum[i]=sum[i-1]+p[i-1];}for(intj=0;jsize;j++){for(intk=0;knumber;k++){//确定被编码字符的下限属于【0，1】之间的哪一段if((inputsum[k])&&(inputsum[k+1]))//发现在哪就将属于该段的字符压入向量v{v.push_back(str[j]);temp=(input-sum[k])/(sum[k+1]-sum[k]);//计算下一个被编码字符的下限input=temp;break;}elsecontinue;}}coutendl;cout译码输出为：;//将译码结果输出for(intm=0;mv.size();m++){coutv[m];}coutendl;}