算术编码.cpp

实现算术编码的功能

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

char code[100];
double ps=1;
double d=0;
double High,Low,low,high;
int n;
int l;
char code_1[100];
char code_2[100];
double k;
struct MY
{
    char my;
	float p;
	
}myfh[5];


/*double verse()
{

  double m;
  double tem;
  while(code_1[i]!='\0')
  {
		tem=code_1[i]-48;
		for(j=0;j<i+1;j++)
		tem=tem*0.5;
		m=m+tem;
		}
		return m;
		
}*/

float FS(int i)
{
	float fs=0;
	if(i==0)fs=0;
    for(int j=0;j<i;j++)
		fs+=myfh[j].p;
	return fs;
}


void decode(double k)
{
	//	k=verse();
	double D;
	int j=0;
	int i=1;
	while(1)
	{
		if (k<=FS(j)+myfh[j].p&&k>=FS(j))break;
		j++;
		
	}
	Low=FS(j);
	High=Low+myfh[j].p;
	d=myfh[j].p;
	code_2[0]=myfh[j].my;
	j=0;
	
	while (k!=Low&&j<n)
	{
		while(j<n)
		{
			high=Low+d*(FS(j)+myfh[j].p);
			low=Low+d*FS(j);
			D=d*myfh[j].p;
			j++;
			if(k<high&&k>=low)break;
			
		}
		code_2[i]=myfh[j-1].my;
		High=high;
		Low=low;
		d=D;
		j=0;
		i++;
		
	}
	
	
}

void reverse(double m, int l) 
{ 
	//转小数部分 
	int tem,i=0;
	while(m&&l) 
	{ 
		tem=int(m*2);
		code_1[i]=tem+48; 
		m = m*2 - int(m*2); 
		l--;
		i++;
	}
	code_1[i]='\0';
} 

void PS()
{
	int i=0,j=0;
    while(code[i]!=0)
	{
		for(j=0;j<n;j++)
		{
			if(code[i]==myfh[j].my)
				ps*=myfh[j].p;
		}
		i++;
		
	}
}



void length()
{
	
	PS();
	l=ceil(log10(1/ps)/log10(2));
}

void encode()
{
	int i=1;int j;
	for (j=0;j<n;j++)
	{
		if(code[0]==myfh[j].my)
		{
			Low=FS(j);
			High=Low+myfh[j].p;
			d=myfh[j].p;
		}
		
		
	}
	while(code[i]!=10)
	{
		for (j=0;j<n;j++)
		{
			if(code[i]==myfh[j].my)
			{
				high=Low+d*(FS(j)+myfh[j].p);
				low=Low+d*FS(j);
				High=high;
				Low=low;
				d=d*myfh[j].p;
			}
		}
		i++;
	}
	
	
}

void main()
{
	int i;
	printf("请输入码元符号的个数：\n");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("请输入码元符号:\n");
		getchar();
		scanf("%c",&myfh[i].my);
		printf("请输入码元符号的概率:\n");
		scanf("%f",&myfh[i].p);
	}
	printf("请输入要编码的序列:\n");
	scanf("%s",code);
	encode();
	printf("the range is (%.8f      %.8f)  \n",Low,High);
	length();
	reverse(Low,l);
    printf("%s",code_1);
	decode(Low);
	printf("the decoded result is :\n");
	printf("%s",code_2);
	
}