fano_cd.c

fano编码的c语言实现

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>

char key[100];

struct DATA
{
	char Xi;
	float PXi;
	char code[11];
	int len;
};

struct INFO 
	{
	float length;/*平均码长*/
	float then;/*编码效率*/
	};

double hen(float a)
	{
	return a*(-log(a)/log(2));
	}

struct DATA data[8];
struct INFO aa;
int k,b=0;
float appro(char data[100],int num);
void code(struct DATA *p,int end);
void sort();

main()
{
	int i,j=0,datanum=0;
	float h=0.0,len=0.0;
	printf("please input 100 data from 8 key:\n");
	/*
	do
	{
		//for(i=0;i<=99;i++)
		gets(key);
		if(key[i]=='*') break;
		if(i>=10) break;
	}while(1);*/
	gets(key);
	for(i=0;i<=99&&key[i]!='\0';i++)
		datanum++;
	//datanum=j;/*输入的符号长度*/

	for(i=0;i<=7;i++)
		for(j=0;j<=11;j++)
			data[i].code[j]='\0';
	
	appro(key,datanum);
	sort();
	code(data,8);
	for(i=0;i<=7;i++)
		len+=(data[i].len+1)*data[i].PXi;
	printf("每个符号的概率:\n");
	printf("符号:        概率:\n");
	for(i=0;i<=7;i++)
		printf("%c          %f\n",data[i].Xi,data[i].PXi);
	printf("输出编码:\n");
	for(i=0;i<=99;i++)
		for(j=0;j<=7;j++)
		if(key[i]==data[j].Xi)
			printf("%s",data[j].code);
		printf("\n");
	printf("平均码长为:\n");
	printf("%f\n",len);
	for(i=0;i<=7;i++)
	h+=hen(data[i].PXi);
	printf("编码效率为:\n");
	printf("%f\n",h/len);
	
	
	//return 0;
}


float appro(char key[100],int datanum)
{
	char temp[8]={'\0','\0','\0','\0','\0','\0','\0','\0'};
	int i,j,k;
	int num[8]={1,1,1,1,1,1,1,1};/*假设每一种符号都会出现，则肯定至少出现一次*/
	temp[0]=key[0];
	//num[0]=1;
	for(i=1,j=1;i<=99&&key[i]!='\0';i++)
	{
		k=0;
		while(key[i]!=temp[k])
		{
			k++;
			if(k==8) break;
			
		}
		if(k==8) 
		{
			temp[j]=key[i];
			j++;
		}
		else
		{
			num[k]++;
		}
	}
	for(i=0;i<=7;i++)
	{
		data[i].PXi=(float)num[i]/datanum;
		data[i].Xi=temp[i];
	}/*若输入字符不满8个符号？*/

}

void code(struct DATA *p,int end)
{
	
	int i,j,m,n,b;
	double y=1.0;
	int mark=0,end1,end2;
	int k=0;
	//p=data;
	//k++;//递归自增值，用于字符数组定位
	//z=0i<1表示只有一个概率了
	while(1)//分01组
	{
		float l=0,z=0;
		if(end==1) break;
		for(i=0;i<=mark;i++)
		{
			if(i==(end)) break;
			l=l+p[i].PXi;
			
		}
		
		for(j=i;j<end;j++) 
			z+=p[j].PXi;
		if(y>fabs(l-z))//判断两组值之差是否最小
		{
			y=fabs(l-z);
			k=i;/*k为下一组值的起始点*/
			mark++;
			continue;
		}
		else
		{
			for(n=0;n<k;n++)
				{	
					for(b=0;(p+n)->code[b]!='\0';b++);
					(p+n)->code[b]='0';
					(p+n)->len=b;
				}
			for(m=k;m<end;m++)
				{
					for(b=0;(p+m)->code[b]!='\0';b++);
					(p+m)->code[b]='1';
					(p+m)->len=b;
				}
			
			//return 0;
		}
		
		end1=k;
		end2=end-k;
		code(p+k,end2);
		code(p,end1);
		break;
	}
	

//	if(end==1) mark=-1;//z=0i<1表示只有一个概率了
	
}

void sort()
{
	int i,j,k;
	float temp1,temp2;
	char ctemp;
	for(j=0;j<=7;j++)
		for(i=j;i<=7;i++)
		{
			if(data[i].PXi>data[j].PXi)
			{
				temp1=data[i].PXi;
				ctemp=data[i].Xi;
				data[i].PXi=data[j].PXi;
				data[i].Xi=data[j].Xi;
				data[j].PXi=temp1;
				data[j].Xi=ctemp;
			}	
		}

}