搜索
数据压缩与信源编码大作业一----Huffman编解码实现一、实验目的（1）通过本次实验，加深对Huffman编码算法思想的理解，掌握Huffman编码的基本规则，熟悉并且理解Huffman编码的基本步骤。在此基础上，能够通过编写C语言代码实现Huffman编码的编写压缩工作。（2）通过实现Huffman编码压缩工作，进一步进行解码工作，并且用C语言实现，以此进一步加深理解。二、实验内容（1）编写Huffman压缩程序Huffman_Code对abc.txt进行压缩，压缩结果存储在abc_code.txt中；（2）编写Huffman解压缩程序Huffman_Decode对*_code.txt进行解压，恢复结果存储在*_decode.txt中；（3）默认码表法/两遍扫描的基本方法/自适应压缩方法任选其一。三、算法流程（1）两遍扫描法进行Huffman压缩编码算法流程（2）Huffman解码算法流程四、程序设计说明（1）两遍扫描法进行Huffman压缩编码算法程序说明首先，决定程序好坏优劣以及算法实现难易程度的重要因素便是程序的数据结构。本程序使用了两个数据结构：typedefstruct{charelem;unsignedintm_weight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefstructweight{charelem;unsignedintm_weight;}Weight;第一个数据结构是为了建立Huffman树而用结构体构造的结构体。其中的成员包括ASCII码的名字elem,权重m_weight（有第一次扫描得到的频数决定），以及用来建立二叉树的父节点，左右孩子节点。第二个数据结构是第一扫描统计各个ASCII码得到的频数而建立的结构体。其次是实现算法的函数。第一步，我们要对文本的内容进行扫描，统计，并且记录下来，在这里使用了方法是：对扫描得到的ASCII码进行从开始进行匹配，有两种情况：第一，改码已经出现则，直接让对应的权值W_weight增加1；第二，如果扫描遍历后发现没有，则码字总类k增加1，将该新的码字赋给新的结构体，权值设为1。重复值文件扫描结束。第二步，需要对其进行Huffman树的创立，并且要对其进行编码，生成Huffman压缩码。首先，根据Huffman二叉树的算法，我们需要先得到权值最小的两个码字。这里程序中使用了voidSelect(HuffmanTreeHT,intn,int*s1,int*s2)函数，用最简单的比较方法就开变了得出，并通过指针参数s1,s2传递。得到最小的两个后，我们通过函数voidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,Weight*w,intn)进行Huffman编码实现。算法思想即为普通的二次扫描编码的方法，详细见程序的该函数部分的内容和注释。第三步，将编好的Huffman码写入到压缩文件中，再一次对文件正文进行扫描，没扫描到一个就用编号的Huffman码代替相关的ASCII码。在这之前，考虑到和解码的相对应，在写入到压缩文档之前。需要提供一些信息给解压缩程序，其中包括，文本的大小，用size表示，文本总的总类数目，用k表示，每种ASCII码对应的Huffman码，按照Huffman树的顺序。第四部，输出产生相应的文件即可，同时打印出压缩前后的文件的大小，为计算压缩比提供依据。（2）Huffman解码算法程序说明第一步，读出文件的前部分内容，包括对应的文本的大小，用size表示，文本总的总类数目，用k表示，每种ASCII码对应的Huffman码。然后就可以恢复出Huffman数。这里用到unsignedintRead()函数和unsignedintReadk(unsignedintk)，这两个函数可以配合着实现Huffman码的读取，详细见程序及其对应的注释。第二部，扫描全文，将之与Huffman码进行匹配，每次匹配均从根节点开始，知道左右节点没有，这样不会出现重复。扫描至文档结束即可。五、程序压缩性能评价经过压缩，abc.txt的大小S1=20,370Byte,压缩后的abc_code的大小S2=12,165Byte。则：压缩率：r=S2S1=1216520370=0。597可见，其压缩率并不是特比高。分析：因为文件大小仅为20K左右，经过程序对文件的分析，文件中所含有的ASCII码值得种类为77中，Huffman编码最大码长l=8（注意，因为存储方法按字节，所以这里8bit就可以），在存储Huffman编码时浪费BB=（8-1）*77bit=53.9Byte。加上Huffman编码的算法的限制，可以忍受。但是，如果文件更长，会发现压缩率会减小（效果会提高）。但有Huffman编码的上限。解码，经过严格比较，发现完全正确。六、程序源代码/*程序思路：本程序采用二次扫描的方法进行编码，首先先扫描一遍，得到各种ASCII字符，并存入到结构Weight里。然后进行Huffman编码。本次编码思想主要体现在，每一个码子“1”“0”得出后直接当成字节存入写入压缩文件中。压缩文件头部信息：1.文件总字节数目，单位：byte2.各种ASCＩＩ的种类数目3.各种ASCII的编码输出4.正文写入*/#includestdio.h#includestdlib.h#includestring.h#includemath.h#includefcntl.h#includeio.htypedefchar**HuffmanCode;//结构体定义区typedefstruct{charelem;unsignedintm_weight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//Huffman树对应结点typedefstructweight{charelem;unsignedintm_weight;}Weight;//符号及其出现次数//全局变量定义区intbits;//记录实际比特数，清空缓冲区charchl;//字节intlbits;FILE*infp,*outfp;//输入/出文件//**************************选择出权值最小并且父亲结点的权值为0的2个结点*********************voidSelect(HuffmanTreeHT,intn,int*s1,int*s2){inti;(*s1)=(*s2)=0;//初始化s1和s2for(i=1;i=n;i++){if(HT[i].m_weightHT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0){if(HT[i].m_weightHT[(*s1)].m_weight)//将权值最小的结点地址保存在s1中{(*s2)=(*s1);(*s1)=i;}else(*s2)=i;}if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)//为s1和s2初始植入结点{if((*s1)==0)(*s1)=i;elseif((*s2)==0){if(HT[i].m_weightHT[(*s1)].m_weight){(*s2)=(*s1);(*s1)=i;}else(*s2)=i;}}}if((*s1)(*s2)){i=(*s1);(*s1)=(*s2);(*s2)=i;}return;}//****************************************Huffman编码算法***************************voidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,Weight*w,intn)//Huffman编码算法{inti,m,s1,s2,start,c,f;char*cd;if(n=1)return;m=2*n-1;//得到数的节点数目(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//在内存为*HT分配长度为m+1个HTNode结构体大小的连续空间//初始化HuffmanTree前n个节点for(i=1;i=n;++i){(*HT)[i].elem=w[i-1].elem;(*HT)[i].m_weight=w[i-1].m_weight;(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;}//初始化HuffmanTree前n+1到m节点for(;i=m;++i){(*HT)[i].elem='0';(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;}//构造Huffmanfor(i=n+1;i=m;++i){Select(*HT,i-1,&s1,&s2);//s1,s2得到的是权值最小的两个点(*HT)[s1].parent=i;(*HT)[s2].parent=i;(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;}//在内存为*HT分配长度为n个char大小的连续空间(*HC)=(HuffmanCode)malloc(n*sizeof(char*));cd=(char*)malloc(n*sizeof(char));//为cd分配n个char占的空间大小cd[n-1]='\0';//为每个叶子结点进行编码for(i=1;i=n;++i){start=n-1;//从叶子结点开始向上搜索，如果它是其父结点的左孩子，则其编码为0，否则为1，直到根结点for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent){if((*HT)[f].lchild==c)cd[--start]='0';elsecd[--start]='1';}(*HC)[i]=(char*)malloc((n-start)*sizeof(char));//为每个结点的编码分配存储空间strcpy((*HC)[i],&cd[start]);//将结点的编码首地址保存到HC中//printf(%x,*(*HC)[i]);}//假设编码时正确的}voidSelect(HuffmanTree,int,int*,int*);//选择结点//***************8向outfp中写入一个比特******************************voidWrite(unsignedintbit)//向outfp中写入一个比特{bits++;chl=(chl1)+bit;if(bits==8){//缓冲区已满,写入outfpfputc(chl,outfp);//printf(zhigeshi%d\n,chl);bits=0;chl=0;}}//*******************向outfp中写入k个比特******************************voidWritek(unsignedintnum,unsignedinth)//向outfp中写入k个比特{int*s;unsignedinti,bit;bit=0;s=(int*)malloc((h+2)*sizeof(int));for(i=1;i=h;i++){s[i]=0;s[i]=num&1;num=num1;}for(i=h;i0;){bit=s[i];Write(bit);i--;}}//***************************强行写入outfp**************************