算術(shù)編碼的C實(shí)現(xiàn)

1、word算術(shù)編碼的C+實(shí)現(xiàn)#include <iostream>#include <string>#include <cstring>#include <vector>using namespace std;#define N 50 /輸入的字符應(yīng)該不超過(guò)50個(gè)struct L /結(jié)構(gòu)用于求各字符及其概率char ch; /存儲(chǔ)出現(xiàn)的字符不重復(fù) int num; /存儲(chǔ)字符出現(xiàn)的次數(shù)double f;/存儲(chǔ)字符的概率 ;/顯示信息void disp();/求概率函數(shù)，輸入：字符串；輸出：字符數(shù)組、字符的概率數(shù)組;返回：數(shù)組長(zhǎng)度；int proba

2、(string str,char c,long double p,int count);/求概率的輔助函數(shù)int search(vector<L> arch,char,int n);/編碼函數(shù)，輸入：字符串，字符數(shù)組，概率數(shù)組，以及數(shù)組長(zhǎng)度；輸出：編碼結(jié)果long double bma(char c,long double p,string str,int number,int size);/譯碼函數(shù)，輸入：編碼結(jié)果，字符串，字符數(shù)組，概率數(shù)組，以及它們的長(zhǎng)度；輸出：字符串/該函數(shù)可以用于檢測(cè)編碼是否正確void yma(string str,char c,long double

3、p, int number,int size,long double input);int main()string str; /輸入要編碼的String類型字符串int number=0,size=0; /number-字符串中不重復(fù)的字符個(gè)數(shù)；size-字符串長(zhǎng)度char cN; /用于存儲(chǔ)不重復(fù)的字符 long double pN,output; /pN-不重復(fù)字符的概率，output-編碼結(jié)果disp();cout<<"輸入要編碼的字符串:"getline(cin,str); /輸入要編碼的字符串size=str.length(); /字符串長(zhǎng)度numb

4、er=proba(str,c,p,size);/調(diào)用求概率函數(shù)，返回不重復(fù)字符的個(gè)數(shù)cout.setf(ios:fixed); /“魔法配方規(guī)定了小數(shù)局部的個(gè)數(shù)cout.setf(ios:showpoint); /在此規(guī)定編碼結(jié)果的小數(shù)局部有十個(gè)cout.precision(10);output=bma( c, p, str, number, size);/調(diào)用編碼函數(shù)，返回編碼結(jié)果yma(str,c, p, number, size, output); /調(diào)用譯碼函數(shù)，輸出要編碼的字符串， /以驗(yàn)證編碼是否正確return 0;/顯示信息void disp()cout<<endl

5、;cout<<"*算術(shù)編碼*n"cout<<"* heiness*n"cout<<endl;cout<<"此程序只需要輸入要編碼的字符串，不需要輸入字符概率n" cout<<endl;/求概率函數(shù)int proba(string str,char c,long double p, int count) cout.setf(ios:fixed); /“魔法配方規(guī)定了小數(shù)局部位數(shù)為三位cout.setf(ios:showpoint);cout.precision(3);vecto

6、r<L>pt; /定義了結(jié)構(gòu)類型的向量，用于同時(shí)存儲(chǔ)不重復(fù)的字符和其概率 L temp; /結(jié)構(gòu)類型的變量temp.ch = str0; /暫存字符串的第一個(gè)字符，它的個(gè)數(shù)暫設(shè)為1temp.num=1; temp.f=0.0;pt.push_back(temp); /將該字符及其個(gè)數(shù)壓入向量 for (int i=1;i<count;i+)/對(duì)整個(gè)字符串進(jìn)行掃描temp.ch=stri; /暫存第二個(gè)字符temp.num=1;temp.f=0.0;for (int j=0;j<pt.size();j+) /在結(jié)構(gòu)向量中尋找是否有重復(fù)字符出現(xiàn) /假設(shè)重復(fù)，該字符個(gè)數(shù)加1，

7、并跳出循環(huán)int k; /假設(shè)不重復(fù)，那么壓入該字符，并跳出循環(huán)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+) /計(jì)算不重復(fù)字符出現(xiàn)的概率pti.f=double(pti.num)/count; intnumber=pt.size(); /計(jì)算不重復(fù)字符出現(xiàn)的次數(shù) cout<<"各字符概率如下：n" for (i=0;i<number;i+) /顯示所得的概率，驗(yàn)證是否正確 if (c

8、ount=0) cout<<"NO sample!n" else ci=pti.ch; pi=pti.f; cout<<ci<<"的概率為："<<pi<<endl; return number; /返回不重復(fù)字符的個(gè)數(shù)/求概率的輔助函數(shù)/假設(shè)搜索發(fā)現(xiàn)有重復(fù)字符返回正數(shù)/否那么，返回-1int search(vector<L> arch,char ch1,int n)for (int i=0;i<n;i+) if(ch1=archi.ch) return i;return -1;

9、/編碼函數(shù)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-下一個(gè)編碼區(qū)間的上限，Low-下一個(gè)編碼區(qū)間的下限；/high-中間變量，用來(lái)計(jì)算下一個(gè)編碼區(qū)間的上限；/low-中間變量，用來(lái)計(jì)算下一個(gè)編碼區(qū)間的下限；/range-上一個(gè)被編碼區(qū)間長(zhǎng)度int i,j=0;for(i=0;i<number;i+)if(str0=ci) break; /編碼第一個(gè)字符while(j<i)Low+=pj+;

10、/尋找該字符的概率區(qū)間下限r(nóng)ange=pj; /得到該字符的概率長(zhǎng)度High=Low+range; /得到該字符概率區(qū)間上限for(i=1;i<size;i+) /開始編碼第二個(gè)字符for(j=0;j<number;j+) /尋找該字符在c數(shù)組中的位置if(stri=cj)if(j=0) /假設(shè)該字符在c數(shù)組中的第一個(gè)字符low=Low; /此時(shí)該字符的概率區(qū)間下限剛好為零high=Low+pj*range;High=high;range*=pj; /求出該字符的編碼區(qū)間長(zhǎng)度else /假設(shè)該編碼字符不是c數(shù)組中的第一個(gè)float proba_next=0.0;for(int k=

11、0;k<=j-1;k+)proba_next+=pk; /再次尋找字符的概率區(qū)間下限low=Low+range*proba_next; /編碼區(qū)間下限high=Low+range*(proba_next+pj);/編碼區(qū)間上限Low=low; /編碼區(qū)間下限High=high; /編碼區(qū)間上限r(nóng)ange*=pj; /編碼區(qū)間長(zhǎng)度else continue; /i+，編碼下一個(gè)字符cout<<endl;cout<<"輸入字符串的編碼為:"<<Low<<endl;return Low;/譯碼函數(shù)void yma(string

12、 str,char c,long double p, int number,int size,long double input)vector<char> v; /定義char類型向量vlong double temp; /中間變量long double sumN; /存儲(chǔ)不重復(fù)字符概率區(qū)間的下限sum0=0.0; /數(shù)組第一個(gè)元素為0 for (int i=1;i<number+1;i+) /計(jì)算數(shù)組各元素的值 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) /發(fā)現(xiàn)在哪就將屬于該段的字符壓入向量vv.push_back(strj);tem