算术编码的C++实现.doc

算术编码的C+实现#include #include #include #include using namespace std;#define N 50 /输入的字符应该不超过50个struct L /结构用于求各字符及其概率char ch; /存储出现的字符（不重复） int num; /存储字符出现的次数double f;/存储字符的概率 ;/显示信息void disp();/求概率函数，输入：字符串；输出：字符数组、字符的概率数组;返回：数组长度；int proba(string str,char c,long double p,int count);/求概率的辅助函数int search(vector arch,char,int n);/编码函数，输入：字符串，字符数组，概率数组，以及数组长度；输出：编码结果long double bma(char c,long double p,string str,int number,int size);/译码函数，输入：编码结果，字符串，字符数组，概率数组，以及它们的长度；输出：字符串/该函数可以用于检测编码是否正确void yma(string str,char c,long double p, int number,int size,long double input);int main()string str; /输入要编码的String类型字符串int number=0,size=0; /number-字符串中不重复的字符个数；size-字符串长度char cN; /用于存储不重复的字符 long double pN,output; /pN-不重复字符的概率，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); /调用译码函数，输出要编码的字符串， /以验证编码是否正确return 0;/显示信息void disp()coutendl;cout*算术编码*n;cout*作者：heiness*n;coutendl;cout此程序只需要输入要编码的字符串，不需要输入字符概率n; coutendl;/求概率函数int proba(string str,char c,long double p, int count) cout.setf(ios:fixed); /“魔法配方”规定了小数部分位数为三位cout.setf(ios:showpoint);cout.precision(3);vectorpt; /定义了结构类型的向量，用于同时存储不重复的字符和其概率 L temp; /结构类型的变量temp.ch = str0; /暂存字符串的第一个字符，它的个数暂设为1temp.num=1; temp.f=0.0;pt.push_back(temp); /将该字符及其个数压入向量 for (int i=1;icount;i+)/对整个字符串进行扫描temp.ch=stri; /暂存第二个字符temp.num=1;temp.f=0.0;for (int j=0;j=0)ptk.num+;break;else pt.push_back(temp);break;for (i=0;ipt.size();i+) /计算不重复字符出现的概率pti.f=double(pti.num)/count; intnumber=pt.size(); /计算不重复字符出现的次数 cout各字符概率如下：n; for (i=0;inumber;i+) /显示所得的概率，验证是否正确 if (count=0) coutNO sample!n; else ci=pti.ch; pi=pti.f; coutci的概率为：piendl; return number; /返回不重复字符的个数/求概率的辅助函数/若搜索发现有重复字符返回正数/否则，返回-1int search(vector arch,char ch1,int n)for (int i=0;in;i+) if(ch1=archi.ch) return i;return -1;/编码函数long double bma(char c,long double p,string str,int number,int size)long double High=0.0,Low=0.0,high,low,range;/High-下一个编码区间的上限，Low-下一个编码区间的下限；/high-中间变量，用来计算下一个编码区间的上限；/low-中间变量，用来计算下一个编码区间的下限；/range-上一个被编码区间长度int i,j=0;for(i=0;inumber;i+)if(str0=ci) break; /编码第一个字符while(ji)Low+=pj+; /寻找该字符的概率区间下限range=pj; /得到该字符的概率长度High=Low+range; /得到该字符概率区间上限for(i=1;isize;i+) /开始编码第二个字符for(j=0;jnumber;j+) /寻找该字符在c数组中的位置if(stri=cj)if(j=0) /若该字符在c数组中的第一个字符low=Low; /此时该字符的概率区间下限刚好为零high=Low+pj*range;High=high;range*=pj; /求出该字符的编码区间长度else /若该编码字符不是c数组中的第一个float proba_next=0.0;for(int k=0;k=j-1;k+)proba_next+=pk; /再次寻找字符的概率区间下限low=Low+range*proba_next; /编码区间下限high=Low+range*(proba_next+pj);/编码区间上限Low=low; /编码区间下限High=high; /编码区间上限range*=pj; /编码区间长度else continue; /i+，编码下一个字符coutendl;cout输入字符串的编码为:Lowendl;return Low;/译码函数void yma(string str,char c,long double p, int number,int size,long double input)vector v; /定义char类型向量vlong double temp; /中间变量long double sumN; /存储不重复字符概率区间的下限sum0=0.0; /数组第一个元素为0 for (int i=1;inumber+1;i+) /计算数组各元素的值 sumi=sumi-1+pi-1; for (int j=0;jsize;j+) for (int k=0;ksumk)&(inputsumk+1) /发现在哪就将属于该段的字符压入向量vv.p