fano.cpp

费诺码编码...很好

//a 0.25  e 0.0625 f 0.0625 g 0.0625 h 0.0625 b 0.25 c 0.125 d 0.125
//a 0.32 b 0.22 c 0.18 d 0.16 e 0.08 f 0.04
//a 0.2 b 0.15 c 0.15 d 0.15 e 0.1 f 0.1 g 0.1 h 0.05
#include"iostream.h"
#include<iomanip.h>
#include"vector"
#include"algorithm"
#include"math.h"
using namespace std;
struct bitree
{//定义结构用于存储编码结果的二叉树结构,在译码时用到
	char ch;	//用于存储码符号
	char mz;	//用于存储码字
	bitree * lchild;
	bitree * rchild;

};
struct data
{//用于存储相关的信源符号以及其概率
	double p;
	char ch;
	vector<char> code;
	int ml;
};
bool sortspecial(data dt1,data dt2)
{//用于排序时用
	return dt1.p>dt2.p;
}
void print2(vector<char>vd)
{//用于打印译码结果
	for(int i=0;i<vd.size();i++)
		cout<<vd[i]<<" ";
	cout<<endl;
}
void read(vector <data> &vd)
{//用于读入相关的信源符号以及概率
	int n;
	while(true)
	{
		cout<<"请输入信源符号数:"<<endl;
		cin>>n;
		cout<<"请输入相应的信源符号及其概率:"<<endl;
		data dt;
		int	i=0;		
		while(i<n)
		{	
			cin>>dt.ch;
			cin>>dt.p;
			dt.ml=0;
			vd.push_back(dt);
			i++;
			
		}
		double sum=0;
		vector<data>::iterator pit;
		for(pit=vd.begin();pit!=vd.end();pit++)
		{
			sum+=pit->p;
		}
		if(sum!=1)
		{
			cout<<"你输入的概率不符合要求,请重新输入."<<endl;
			sum=0;
			continue;
		}
		sort(vd.begin(),vd.end(),sortspecial);
		break;
	}
}

void append(char ch1,char ch2,bitree *&bt)
{//用于再构造码字二叉树时向其中添加结点
	bitree * bit=new bitree;
	bit->ch=ch1;
	bit->mz=ch2;
	bit->lchild=NULL;
	bit->rchild=NULL;
	if(ch1=='0')
		bt->rchild=bit;
	else bt->lchild=bit;
}
void Creatmz1(vector<data>& vd,int begin1,int end1  ,double pn ,bitree *&bt)
{//进行编码,用递归的方法进行编码
	int begin=begin1,end=end1;
	if(begin==end) return;
	else if(begin+1==end)
	{
		return;
	}
	else if(begin+2==end){
		vd[begin].code.push_back('0');
		vd[begin].ml++;
		append('0',vd[begin].ch,bt);
		vd[end-1].code.push_back('1');
		vd[end-1].ml++;
		append('1',vd[end-1].ch,bt);
		return;
	}
	else{
			double sum0=0,sum1=0,sum2=0;
			do{
				 sum1+=vd[begin].p;
				 sum2=sum1+vd[begin+1].p;
				 begin++;
			 }while(fabs(sum1/pn-0.5)>fabs(sum2/pn-0.5));//用于找到上下两组码的分点使得其概率和近于相同
			for(int i=begin1;i<begin;i++){
				vd[i].code.push_back('0');
				vd[i].ml++;
			}
			if(begin1+1 == begin){
				append('0',vd[begin1].ch,bt);
			}
			else append('0','0',bt);
			for(int j=begin;j<=end1-1;j++){
				vd[j].code.push_back('1');
				vd[j].ml++;
			}
			if(begin+1 == end1){
				append('1',vd[begin].ch,bt);
			}
			else append('1','0',bt);
			Creatmz1(vd,begin1 ,begin,sum1,bt->rchild );//对分点前的进行编码
			Creatmz1(vd,begin ,end1,pn-sum1,bt->lchild);//对分点后的进行编码
	}
}
void print1(vector<data> vd)
{//用于打印编码结果
	cout<<"xi"<<setw(8)<<"P(xi)"<<setw(8)<<"码长"
        <<setw(8)<<"码字"<<setw(8)<<endl;
	for(int i=0;i<vd.size();i++){
		cout<<vd[i].ch<<setw(8)<<vd[i].p<<setw(8)<<vd[i].ml<<setw(8);
		for(int j=0;j<vd[i].code.size();j++)
			cout<<vd[i].code[j];
			cout<<setw(8)<<endl;
	}
}

void clear(bitree * & bt)
{//对二叉树的动态存储空间进行释放
	if(bt!=NULL&&bt->lchild!=NULL)
		clear(bt->lchild);
	if(bt!=NULL&&bt->rchild!=NULL)
		clear(bt->rchild);
	delete bt;
}

bool des_code(vector <char> & vr,vector <char> vt,bitree *bt)
{//用二叉编码树进行解码
	if(bt==NULL)
	{
		cout<<"码树不存在!!!"<<endl;
		return false;
	}
	int pit=0;
	bitree * mbt=bt;
	while ((mbt->lchild!=NULL||mbt->rchild!=NULL)||pit<vt.size())
	{
		if(mbt->lchild==NULL&&mbt->rchild==NULL&&mbt->mz!='0')
		{
			vr.push_back(mbt->mz);
			mbt=bt;
		}
		if(mbt->lchild!=NULL&& vt[pit]=='1')
		{
			mbt=mbt->lchild;
			pit++;
		}
		else if(mbt->rchild!=NULL&& vt[pit]=='0')
		{
			mbt=mbt->rchild;
			pit++;
		}	
		else if(mbt->lchild!=NULL&&mbt->rchild!=NULL) break;
	}
	if(mbt->lchild!=NULL&&mbt->rchild!=NULL)
	{
		cout<<"你输入的是一个错误的码序列,请较正后再输入."<<endl;
		return false;
	}
	else {
		vr.push_back(mbt->mz);
		return true;
	}
}
void read1(vector<char>& vd)
{//用于读入要解码的序列
	cout<<"请输要译码的序列(以'#'结束):"<<endl;
	char dt;
	int	i=0;
	cin>>dt;		
	while(dt!='#')
	{	
		vd.push_back(dt);
		cin>>dt;
	}
}	

void print_H_L_R(vector<data>vd)
{//用于计算并打印信息熵,平均码长,效率
	double H=0,L=0,R=0;
	for(int i=0;i<vd.size();i++)
	{	
		H+=vd[i].p*(log10(1/vd[i].p)/log10(2));
		L+=vd[i].p*(double)vd[i].ml;
	}
	R=H/L;
	cout<<"此码的信息熵(H)是:"<<H<<endl;
	cout<<"此码的平均码长(L)为:"<<L<<endl;
	cout<<"此码的效率(U)为:"<<R<<endl;
}
int main()
{
	bitree * bt=new bitree;
	bt->ch = '#';
	bt->mz = '*';
	bt->lchild=NULL;
	bt->rchild=NULL;
	vector <data> vd;
	vector <char> vr;
	vector <char> vt;
	cout<<"************下面将对Fano编,译码的过程进行演示*************"<<endl;
	cout<<"__________________________________________________________"<<endl;
	cout<<endl;
	cout<<"************下面显示编码的过程及相关参数和结果************"<<endl;
	read(vd);
	if(vd.size()==1)
	{
		vd[0].code.push_back('0');
		vd[0].ml++;
		append('0',vd[0].ch,bt);
	}
	cout<<endl;
	Creatmz1(vd,0,vd.size(),1,bt);
	cout<<"**************    编码结果    **************"<<endl;
	print1(vd);
	print_H_L_R(vd);
	cout<<endl;
	cout<<"************   下面将进行译码过程操作的演示   ************"<<endl;
	cout<<endl;
	read1(vt);
	if(des_code(vr,vt,bt))
		print2(vr);
	clear(bt);
	return 1;
}