算术编码的C++实现(共5页).doc
精选优质文档-倾情为你奉上算术编码的C+实现#include <iostream>#include <string>#include <cstring>#include <vector>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<L> 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()cout<<endl;cout<<"*算术编码*n"cout<<"*作者：heiness*n"cout<<endl;cout<<"此程序只需要输入要编码的字符串，不需要输入字符概率n" cout<<endl;/求概率函数int proba(string str,char c,long double p, int count) cout.setf(ios:fixed); /“魔法配方”规定了小数部分位数为三位cout.setf(ios:showpoint);cout.precision(3);vector<L>pt; /定义了结构类型的向量，用于同时存储不重复的字符和其概率 L temp; /结构类型的变量temp.ch = str0; /暂存字符串的第一个字符，它的个数暂设为1temp.num=1; temp.f=0.0;pt.push_back(temp); /将该字符及其个数压入向量 for (int i=1;i<count;i+)/对整个字符串进行扫描temp.ch=stri; /暂存第二个字符temp.num=1;temp.f=0.0;for (int j=0;j<pt.size();j+) /在结构向量中寻找是否有重复字符出现 /若重复，该字符个数加1，并跳出循环int k; /若不重复，则压入该字符，并跳出循环k=search(pt,stri,pt.size();if(k>=0)ptk.num+;break;else pt.push_back(temp);break;for (i=0;i<pt.size();i+) /计算不重复字符出现的概率pti.f=double(pti.num)/count; intnumber=pt.size(); /计算不重复字符出现的次数 cout<<"各字符概率如下：n" for (i=0;i<number;i+) /显示所得的概率，验证是否正确 if (count=0) cout<<"NO sample!n" else ci=pti.ch; pi=pti.f; cout<<ci<<"的概率为："<<pi<<endl; return number; /返回不重复字符的个数/求概率的辅助函数/若搜索发现有重复字符返回正数/否则，返回-1int search(vector<L> arch,char ch1,int n)for (int i=0;i<n;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;i<number;i+)if(str0=ci) break; /编码第一个字符while(j<i)Low+=pj+; /寻找该字符的概率区间下限range=pj; /得到该字符的概率长度High=Low+range; /得到该字符概率区间上限for(i=1;i<size;i+) /开始编码第二个字符for(j=0;j<number;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+，编码下一个字符cout<<endl;cout<<"输入字符串的编码为:"<<Low<<endl;return Low;/译码函数void yma(string str,char c,long double p, int number,int size,long double input)vector<char> v; /定义char类型向量vlong double temp; /中间变量long double sumN; /存储不重复字符概率区间的下限sum0=0.0; /数组第一个元素为0 for (int i=1;i<number+1;i+) /计算数组各元素的值 sumi=sumi-1+pi-1; for (int j=0;j<size;j+) for (int k=0;k<number;k+) /确定被编码字符的下限属于【0，1】之间的哪一段if (input>sumk)&&(input<sumk+1) /发现在哪就将属于该段的字符压入向量vv.push_back(strj);temp=(input-sumk)/(sumk+1-sumk);/计算下一个被编码字符的下限input=temp;break;elsecontinue; cout<<endl;cout<<"译码输出为：" /将译码结果输出 for (int m=0;m<v.size();m+)cout<<vm;cout<<endl;专心-专注-专业
