mm09.cpp

多媒体无损编码实现。（ 霍夫曼编码

// MM09.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
using namespace std;

typedef struct{
  float weight;//权值
  int parent,lchild,rchild;//父亲、左孩子、右孩子
}HTNode,*HuffmanTree;//霍夫曼树

void Huffman(int n);//Huffman coding
void arithmetic(int n);//arithmetic coding
void lzw(int n);//LZW
long double value(char *s);//算术编码中二进制字符串进行求值
bool isExist(string c,int n,string *dictionary,int &pid);

char c[1000];
float w[1000];
float ww[1000];
char text[10000];

int main()
{
	int n = 0,i,j,type;


    printf("*****************************网络多媒体实验（一）*****************************\n");
	printf("请输入想要编码的正文:");
	gets(text);

	printf("初始化......\n");
	printf("记录各个字符以及计算各自出现的概率.\n");

	int nC = 0;//正文字符的个数
	i = 0;
    while(text[i] != '\0'){
		nC++;
		for(j = 0;c[j] != NULL;j++){
			if(c[j] == text[i]){
				ww[j]++;
				break;
			}
		}

		if(c[j] == NULL){
		   c[j] = text[i];
		   ww[j] = 1;
		   n++;
		}

		i++;
	}

	i = 0;
	while(ww[i] != NULL ){
	  w[i] = ((float)ww[i])/nC;
	  i++;
	}

	printf("正文大小：%dB\n",sizeof(char)*nC);

	printf("初始化完毕......\n");
	system("pause");
	system("cls");
    printf("*****************************网络多媒体实验（一）*****************************\n");
	printf("选择编码的方式：1、Huffman coding 2、arithmetic coding 3、LZW 0、退出\n");
	scanf("%d",&type);
	getchar();
	while(type != 0){
	  if(type == 1){
	      Huffman(n);
	  }else if(type == 2){
	      arithmetic(n);
      }else if(type == 3){
	      lzw(n);
      }
	  system("cls");
	  printf("*****************************网络多媒体实验（一）*****************************\n");
      printf("选择编码的方式：1、Huffman coding 2、arithmetic coding 3、LZW 0、退出\n");
	  scanf("%d",&type);
      getchar();
	}
	return 0;
}

void Huffman(int n){//哈弗曼编码
   int i,j,m;//m为总结点数，i,j为计数器
   char code[5000];//储存编码
   int i_code = 0;//code 的下标计数器

   //初始化哈弗曼树
   HuffmanTree HT;

   if(n <= 1) return;

   m = 2*n-1;//为m赋值
   HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));//为哈夫曼树分配内存空间
   HuffmanTree p = HT + 1;//设一临时哈弗曼树指针

   for(i = 1;i <= n;++i,++p) {
	   (*p).weight = w[i-1];
	   (*p).lchild=(*p).parent=(*p).rchild=0;
   }//建立n个结点并赋权值
   for(;i <= m;++i,++p) (*p).lchild=(*p).parent=(*p).rchild=(*p).weight=0;//初始化从n+1到m的结点值
   
   for(i = n+1;i <= m;++i){
       int tempS,s1,s2,k=1;//s1 s2 标志最小的两个权值的结点位置，tempS暂存位置
	   float min1,min2,temp;//min1为最小的权值,min2为次小的权值,temp暂存权值


	   while(HT[k].parent != 0) k++;//寻找第一个没有父结点的结点
	   min1 = HT[k].weight;
	   s1=k;
	   k++;
	   while(HT[k].parent != 0) k++;//寻找第二个没有父节点的结点
	   min2 = HT[k].weight;
	   s2=k;
	   if(min2 < min1){
	     temp = min1;
		 min1 = min2;
		 min2 = temp;
		 tempS = s1;
		 s1 = s2;
	     s2 = tempS;
	   }//若min1>min2则交换位置


	   //寻找最小权值以及次小权值
	   for(j = k + 1;j <= i-1;j++){
		 if(HT[j].parent != 0) continue;

		 temp = min2;tempS = s2;

		 if (HT[j].weight < min1){
			 temp = min1;
			 tempS = s1;
			 min1 = HT[j].weight;
			 s1 = j;
		 }else if(HT[j].weight >= min1&&HT[j].weight < min2){
			 min2 =HT[j].weight;
			 s2 = j;
		 }
		 if(temp < min2){
			 min2 = temp;
             s2 = tempS;
		 }
	   }

	   //为最小权值和次小权值的结点赋予父亲，并给父亲赋予权值
	   HT[s1].parent = HT[s2].parent = i;
	   HT[i].lchild = s1;
	   HT[i].rchild = s2;
	   HT[i].weight = HT[s1].weight + HT[s2].weight;
   } 

   //以下是对输入的字符串进行编码
   printf("编码如下:\n");
   int f,start,c1;
   char command;
   for(i = 0;text[i] != NULL;i++){
	     char * cd = (char *)malloc(n*sizeof(char));//储存对每一个字符的编码
         cd[n-1] = '\0';

	     for(j = 1;j <= n;j++){
	        if(c[j-1] != text[i]) continue;
            start = n-1;
		    for(c1 = j,f = HT[j].parent;f != 0;c1 = f,f = HT[f].parent){
			  if(HT[f].lchild == c1) cd[--start] = '0';
			  else cd[--start] = '1';
		   }
		 }
	     j = start;

	     for(;j < n-1;j++){
	       printf("%c",cd[j]);
		   code[i_code++] = cd[j];
	     }
		 
	     free(cd);
   }
   code[i_code] = '\0';
   printf("\n编码后的大小：%dB\n",(i_code%8 == 0) ? i_code/8 : i_code/8+1);

   printf("要解码吗？y/n\n");
   command = getchar();
   getchar();
   if(command == 'y'){//解码算法   
      int tempM;
       m = 2*n-1;//求哈夫曼树的总结点数
	   tempM = m;
	   for(i = 0;code[i] != '\0';i++){
		 if(HT[tempM].lchild == 0){
		    printf("%c",c[tempM-1]);
		    tempM = m;
		    i--;//回退一步
		 }else{
		   	if(code[i] == '0') tempM = HT[tempM].lchild;
		    else tempM = HT[tempM].rchild;
		 }
	   }
	   if(HT[tempM].lchild == 0) {
		 printf("%c",c[tempM-1]);
	   }//打印最后一个编码对应的字符    
       putchar('\n');
   }
      
   system("pause");
}

void arithmetic(int n){//算术编码
	int i = 0;
	int j;
    long double low,high,range,range_low[1000],range_high[1000]; 
    low = 0.0;
    high = range = 1.0;
    
	//计算各个字符的range_low,range_high
	long double start = 0.0;
	for(j = 0;j < n;j++){
	    range_low[j] = start;
		range_high[j] = start + w[j]; 
		start = range_high[j];
	}

	while(text[i] != '\0'){
	   for(j = 0;j < n;j++){
		   if(text[i] == c[j]) break;
	   }

	   high = low + range*range_high[j];
	   low = low + range*range_low[j];

	   range = high - low;
	   i++;
	}

	//产生编码
    char *code;
	int k = 2;
    code = (char *)malloc(sizeof(char)*1000);
	code[0] = '0';
	code[1] = '.';
	code[2] = '0';
	code[3] = '\0';

	while(value(code) < low){
	   code[k] = '1';
	   code[k+1] = '\0';
	   if(value(code) > high){
	      code[k] = '0';
	   }
	   k++;
	}

    printf("编码如下:\n%s\n",code);
	printf("编码后的大小：%dB\n",(k-3)%8 == 0? (k-3)/8:(k-3)/8+1);

	printf("要解码吗？y/n\n");
	char command;
    command = getchar();
    getchar();
    if(command == 'y'){//解码算法   
       long double valueD = value(code);
	   do{
		   for(j = 0;j < n;j++){
			   if(range_low[j]  <= valueD && range_high[j] > valueD){
				   			    printf("%c",c[j]);
								break;
			   }
		   }
		   low = range_low[j];
		   high = range_high[j];
		   range = high - low;
		   valueD = (valueD - low)/range;
	   }while(c[j] != '$');
    }

	putchar('\n');
    system("pause");
}


long double value(char *s){
   int i;
   long double f = 0.0;
   int j = -1;
   for(i = 2;s[i] != '\0';i++){
       f += (s[i]-'0')*pow(2.0,j);
	   j--;
   }

   return f;
}

void lzw(int n){//LZW编码算法
   int i,j,d;
   d = 1;//默认用一位来表示编码 
   string dictionary[1000],s,cLzw,temp,dictionary1[1000];
   int code[1000],n1;
   int k = 0;

   for(i = 0;i < n;i++){
	   dictionary[i] = c[i];
	   dictionary1[i] = c[i];
   }//初始字符串表

   n1 = n;
   
   s = text[0];
   int pid;
   for(i = 0;i < n;i++){
	   if(s == dictionary[i]){
	       pid = i+1;
		   break;
	   }
   }
    
    printf("编码如下：\n");
   for(i = 1;text[i] != '\0';i++){
	  cLzw = text[i];

      temp = s + cLzw;

	  if(isExist(temp,n,dictionary,pid)){
		  s.append(cLzw);
	  }
	  else{
	     printf(" %d",pid);
		 while((int)(pow(2.0,d)-1) < pid) d++ ;
		 code[k++] = pid;
		 dictionary[n++] = temp;
		 s = cLzw;
		 for(j = 0;j < n;j++){
	       if(cLzw == dictionary[j]){
	           pid = j+1;
		       break;
	       }
         }
	  }
   }
   printf(" %d\n",pid);
   code[k] = pid;
   printf("编码后的大小：%dB\n",(k*d)%8 == 0? (k*d)/8:(k*d)/8+1);

   printf("要解码吗？y/n\n");
   char command;
   int k1;
   string entry;

   command = getchar();
   getchar();
  if(command == 'y'){//解码算法 
	   s.clear();
	   for(i = 0;i <= k;i++){
	       k1 = code[i];
           entry = dictionary[k1-1];

		   if(entry.empty()){
			   entry = s + s.c_str()[0];
		   }

		   cout<<entry;
		   if(!s.empty()){ 
			  temp = s + entry.c_str()[0];
		      dictionary1[n1++] = temp;
		   }
		   s = entry;
	   }
	   putchar('\n');
   }
   system("pause");
}

bool isExist(string c,int n,string *dictionary,int &pid){
    int i;
	for(i = 0;i < n;i++){
		if(c == dictionary[i]) {
			pid = i+1;
			return true;
		}
	}
    return false;
}