数据压缩及信源编码Huffman编码压缩

1、数据压缩与信源编码大作业一-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

2、进行解压，恢复结果存储在*_decode.txt中；（3）默认码表法 / 两遍扫描的基本方法 / 自适应压缩方法 任选其一。三、 算法流程（1） 两遍扫描法进行Huffman压缩编码算法流程（2） Huffman解码算法流程四、 程序设计说明（1） 两遍扫描法进行Huffman压缩编码算法程序说明首先，决定程序好坏优劣以及算法实现难易程度的重要因素便是程序的数据结构。本程序使用了两个数据结构：typedef struct char elem; unsigned int m_weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTre

3、e; typedef struct weight char elem; unsigned int m_weight; Weight;第一个数据结构是为了建立Huffman树而用结构体构造的结构体。其中的成员包括ASCII码的名字elem,权重m_weight（有第一次扫描得到的频数决定），以及用来建立二叉树的父节点，左右孩子节点。第二个数据结构是第一扫描统计各个ASCII码得到的频数而建立的结构体。其次是实现算法的函数。第一步，我们要对文本的内容进行扫描，统计，并且记录下来，在这里使用了方法是：对扫描得到的ASCII码进行从开始进行匹配，有两种情况：第一，改码已经出现则，直接让对应的权值W_w

4、eight增加1；第二，如果扫描遍历后发现没有，则码字总类k增加1，将该新的码字赋给新的结构体，权值设为1。重复值文件扫描结束。第二步，需要对其进行Huffman树的创立，并且要对其进行编码，生成Huffman压缩码。首先，根据Huffman二叉树的算法，我们需要先得到权值最小的两个码字。这里程序中使用了void Select(HuffmanTree HT,int n,int *s1,int *s2)函数，用最简单的比较方法就开变了得出，并通过指针参数s1,s2传递。得到最小的两个后，我们通过函数void HuffmanCoding(HuffmanTree *HT,HuffmanCode *H

5、C,Weight *w,int n)进行Huffman编码实现。算法思想即为普通的二次扫描编码的方法，详细见程序的该函数部分的内容和注释。第三步，将编好的Huffman码写入到压缩文件中，再一次对文件正文进行扫描，没扫描到一个就用编号的Huffman码代替相关的ASCII码。在这之前，考虑到和解码的相对应，在写入到压缩文档之前。需要提供一些信息给解压缩程序，其中包括，文本的大小，用size表示，文本总的总类数目，用k表示，每种ASCII码对应的Huffman码，按照Huffman树的顺序。第四部，输出产生相应的文件即可，同时打印出压缩前后的文件的大小，为计算压缩比提供依据。（2） Huffma

6、n解码算法程序说明第一步，读出文件的前部分内容，包括对应的文本的大小，用size表示，文本总的总类数目，用k表示，每种ASCII码对应的Huffman码。然后就可以恢复出Huffman数。这里用到unsigned int Read()函数和unsigned int Readk(unsigned int k)，这两个函数可以配合着实现Huffman码的读取，详细见程序及其对应的注释。第二部，扫描全文，将之与Huffman码进行匹配，每次匹配均从根节点开始，知道左右节点没有，这样不会出现重复。扫描至文档结束即可。五、 程序压缩性能评价经过压缩，abc.txt的大小S1= 20,370Byte,压缩

7、后的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编码的上限。解码，经过严格比较，发现完全正确。六、 程序源代码/* 程序思路

8、：本程序采用 二次扫描的方法进行编码，首先先扫描一遍，得到各种ASCII字符，并存入到结构Weight里。然后进行Huffman编码。本次编码思想主要体现在，每一个码子“1”“0”得出后直接当成字节存入写入压缩文件中。 压缩文件头部信息：1.文件总字节数目，单位：byte 2.各种ASC的种类数目 3.各种ASCII的编码输出 4.正文写入 */#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <fcntl.h>

9、#include <io.h> typedef char * HuffmanCode; /结构体定义区 typedef struct char elem; unsigned int m_weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /Huffman树对应结点 typedef struct weight char elem; unsigned int m_weight; Weight; /符号及其出现次数 /全局变量定义区 int bits; /记录实际比特数，清空缓冲区 char chl; /字节 i

10、nt lbits; FILE *infp,*outfp; /输入/出文件 /*选择出权值最小并且父亲结点的权值为0的2个结点* void Select(HuffmanTree HT,int n,int *s1,int *s2) int i; (*s1)=(*s2)=0; /初始化s1和s2 for(i=1;i<=n;i+) if(HTi.m_weight<HT(*s2).m_weight&& HTi.parent=0 &&(*s2)!=0) if(HTi.m_weight<HT(*s1).m_weight) /将权值最小的结点地址保存在s1中

11、(*s2)=(*s1); (*s1)=i; else (*s2)=i; if(*s1)=0|(*s2)=0)&&HTi.parent=0) /为s1和s2初始植入结点 if(*s1)=0) (*s1)=i; else if(*s2)=0) if(HTi.m_weight<HT(*s1).m_weight) (*s2)=(*s1); (*s1)=i; else (*s2)=i; if(*s1)>(*s2) i=(*s1); (*s1)=(*s2); (*s2)=i; return; /*Huffman编码算法* void HuffmanCoding(HuffmanTr

12、ee *HT,HuffmanCode *HC,Weight *w,int n) /Huffman编码算法 int i,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=wi-1.elem; (*HT)i.m_weight=wi-1.m_weigh

13、t; (*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; /构造Huffman for(i=n+1;i<=m;+i) Select(*HT,i-1,&s1,&s2); /s1,s2得到的是权值最小的两个点 (*HT)s1.parent=i; (*HT)s2.parent=i; (*HT)

14、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占的空间大小 cdn-1='0' /为每个叶子结点进行编码 for(i=1;i<=n;+i) start=n-1; /从叶子结点开始向上搜索，如果它是其父结点的左孩子，则其编码为0，

15、否则为1，直到根结点 for(c=i,f=(*HT)i.parent;f!=0;c=f,f=(*HT)f.parent) if(*HT)f.lchild =c) cd-start='0' else cd-start='1' (*HC)i=(char *)malloc(n-start)*sizeof(char); /为每个结点的编码分配存储空间 strcpy(*HC)i,&cdstart);/将结点的编码首地址保存到HC中 /printf("%x ",*(*HC)i); /假设编码时正确的 void Select(HuffmanTree

16、,int,int *,int *); /选择结点 /*8向outfp中写入一个比特 *void Write(unsigned int bit) /向outfp中写入一个比特 bits+; chl=(chl<<1)+bit; if(bits=8) /缓冲区已满,写入outfp fputc(chl,outfp); /printf("zhigeshi%d n",chl); bits=0; chl=0; /*向outfp中写入k个比特 *void Writek(unsigned int num,unsigned int h) /向outfp中写入k个比特 int *s;

17、 unsigned int i,bit; bit =0; s=(int *)malloc(h+2)*sizeof(int); for(i=1;i<=h;i+) si=0; si=num & 1; num=num>>1; for(i=h;i>0;) bit=si; Write(bit); i-; /*强行写入outfp* void WriteToOutfp() int i; int l; l=bits; if(l>0) for(i=0;i<8-l;i+) Write(0); /*二进位表示所需的位数 *int NToBits(unsigned int

18、num) /0num之间的整数用二进位表示所需的位数 unsigned int l=0,power=1; while(power<=num) l+;power=power*2; return l; /*从infp中读出一个比特 *unsigned int Read() /从infp中读出一个比特 unsigned int bit; if(bits=0) chl=fgetc(infp); bits=8; bit=(chl & 128)>>7; chl=chl<<1; bits-; return bit; /*8从infp中读出k个比特* unsigned i

19、nt Readk(unsigned int k) /从infp中读出k个比特 unsigned int bit; unsigned int i; int num=0; for(i=0;i<k;) bit=Read(); num=(num<<1)+bit; i+; return num; /*void WriteToOutfp(); int NToBits(unsigned int num); /0num之间的整数用二进位表示所需的最少位数 */ int main() HuffmanTree HT; HuffmanCode HC; Weight *w; char c; /符号

20、unsigned int i; /用于循环 int x; int ch; char y; bits=0; /清空缓冲区 chl=0; unsigned int n; /符号数 int wei; /符号对应的个数 int total=0; int num; unsigned int size,l; unsigned int k=0; /频度大于零的字符数 unsigned int char_index256; /字符对应在树结点表的下标(char_index0到char_indexn-1) char infName256,outfName256; if(infp=fopen("abc.

21、txt","rb")=NULL) printf("不能打开文件:%sn",infName); exit(1); if(outfp=fopen("abc_code.txt","wb")=NULL) printf("不能打开文件:%sn",outfName); exit(1); fseek(infp,0,SEEK_END); size=ftell(infp); /计算打开的文件的大小 printf("压缩前文件的总字节数为:%dn",size); rewind(infp

22、); /将文件指针重新指向开头 w=(Weight *)malloc(256*sizeof(Weight); /为w分配空间 ch=fgetc(infp); /从文件中获取一个字符 w0.elem=ch; w0.m_weight=0; char_indexch=1; /char_index 字符对应在树结点表的下标(char_index0到char_indexn-1) while(ch!=EOF) /保存符合和出现次数 unsigned int i; for(i=0;i<=k;i+) /扫描已经出现过的字符，并且权值加1 if(ch = wi.elem) wi.m_weight=wi.m

23、_weight+1; break; if(i>k) /之前没有出现过字符进行记录，操作 k=k+1; wk.elem=ch; wk.m_weight=1; char_indexch=k+1; ch=fgetc(infp); k=k+1; HuffmanCoding(&HT,&HC,w,k);/进行Huffman编码 num=0; rewind(outfp); /将文件指针重新指向输出文件的开头 fwrite(&size,sizeof(unsigned int),1,outfp); /写入文件的长度 Writek(k-1,8); /写入字符种类数目 for(i=0;

24、i<k;i+) fwrite(&(wi.elem),sizeof(char),1,outfp); /写入各个符合 l=NToBits(2*k-1); /k用二进位表示所需的最少位数 for(i=k+1;i<=2*k-1;i+) Writek(HTi.lchild,l); Writek(HTi.rchild,l); rewind(infp); /将文件指针重新指向输入文件的开头 ch=fgetc(infp); /读取一个字符 while(feof(infp)=0) /将编码写入文件 unsigned int c; c=char_indexch; for(i=0;i<st

25、rlen(HCc);i+) if(HCci='0')Write(0); else Write(1); ch=fgetc(infp); WriteToOutfp(); fseek(outfp,0,SEEK_END); num=ftell(outfp); /计算压缩后文件的大小 printf("压缩后文件的总字节数为:%dn",num); fclose(infp);fclose(outfp); system("pause"); return 0; /* 本程序为解码程序，与编码程序是相对应的。 l->是最长的编码所需要的比特数 bit=

26、read（）->对应的1B表示的一个编码数（0、1） 首先：1.读出文件开始的文件的总长度->size 单位：B 2.读出字符总类数目 3.回复huffman树，进行编码匹配 4.扫描恢复全文。*/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <fcntl.h> #include <io.h> /结构体 struct HTNode1 /压缩用Huffman树结点 unsigned lo

27、ng weight; /字符频度（权值） unsigned int parent,lchild,rchild; ; typedef char ElemType; typedef struct ElemType elem; unsigned int m_weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /Huffman树对应结点 typedef char * HuffmanCode; typedef int Status; typedef struct weight char elem; unsigned int m_

28、weight; Weight; /符号及其出现次数 int bits; /记录实际比特数，清空缓冲区 char chl; /字节 int lbits; void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int); /Huffman编码算法 void Select(HuffmanTree,int,int *,int *); /选择结点 unsigned int Readk(unsigned int k);/从infp中读出k个比特 FILE *infp,*outfp; /输入/出文件 /*函数程序部分* void Write(unsi

29、gned int bit) /向outfp中写入一个比特 bits+; chl=(chl<<1)+bit; if(bits=8) /缓冲区已满,写入outfp ，存起来 fputc(chl,outfp); bits=0; chl=0; /*8向outfp中写入k个比特*void Writek(unsigned int num,unsigned int h) /向outfp中写入k个比特 int *s; unsigned int i,bit; bit =0; s=(int *)malloc(h+2)*sizeof(int); for(i=1;i<=h;i+) si=0; si=

30、num & 1; num=num>>1; for(i=h;i>0;) bit=si; Write(bit); i-; /*强行写入outfp* void WriteToOutfp() int i; int l; l=bits; if(l>0) for(i=0;i<8-l;i+) Write(0); /*0num之间的整数用二进位表示所需的最少位数int NToBits(unsigned int num) /0num之间的整数用二进位表示所需的位数 unsigned int l=0,power=1; while(power<=num) l+;power

31、=power*2; return l; /*从infp中读出一个比特*unsigned int Read() /从infp中读出一个比特 unsigned int bit; if(bits=0) chl=fgetc(infp); bits=8; bit=(chl & 128)>>7; chl=chl<<1; bits-; return bit; /*从infp中读出k个比特 *unsigned int Readk(unsigned int k) / unsigned int bit; unsigned int i; int num=0; for(i=0;i<

32、;k;) bit=Read(); num=(num<<1)+bit; i+; return num; int main(void) HuffmanTree HT; HuffmanCode HC; Weight *w; unsigned int i; unsigned int n; int wei; int total=0; int num; unsigned int size; unsigned int l; unsigned int bit,c; char infName256,outfName256; char Leaf256; /叶结点对应字符(leaf1到leafn) un

33、signed int k; bits=0; /清空缓冲区 chl=0; if(infp=fopen("abc_code.txt","rb")=NULL) printf("不能打开文件:%sn",infName); exit(1); if(outfp=fopen("abc_decode.txt","wb")=NULL) printf("不能打开文件:%sn",outfName); exit(1); fseek(infp,0,SEEK_END); size=ftell(infp)

34、; /计算文件大小 printf("解压缩前文件的总字节数为:%dn",size); bits=0; /清空缓冲区 chl=0; rewind(infp); /将文件指针重新指向输入文件的开头 fread(&size,sizeof(unsigned int),1,infp); k=Readk(8); /读取字符数目 k=k+1; /ASCII码的种类数目 w=(Weight *)malloc(256*sizeof(Weight); /分配空间 for(i=1;i<=k;i+) fread(&Leafi,sizeof(char),1,infp); l=N

35、ToBits(2*k-1); HT=(HuffmanTree)malloc(l+1)*sizeof(HTNode); /分配空间 for(i=1;i<=k;i+) /读出叶结点 HTi.lchild=HTi.rchild=0; for(i=k+1;i<=2*k-1;i+) HTi.lchild=Readk(l); HTi.rchild=Readk(l); bit=Read(); /读一个bit for(i=0;i<size;i+) c=2*k-1; /2*k-1为根结点的下标 while(HTc.lchild!=0|HTc.rchild!=0)&&(feof(

36、infp)=0) if(bit=0) c=HTc.lchild; else c=HTc.rchild; bit=Read(); fputc(Leafc,outfp); /将字符写入outfp中 fseek(outfp,0,SEEK_END); size=ftell(outfp); printf("解压缩后文件的总字节数为:%dn",size); fclose(infp); fclose(outfp); return 0; 七、 测试数据文件-/-/-/ Copyright 251 Mentor Graphics Corporation, 1996-2004, All Rig

37、hts Reserved.-/ UNPUBLISHED, LICENSED SOFTWARE.-/ CONFIDENTIAL AND PROPRIETARY INFORMATION WHICH IS THE-/ PROPERTY OF MENTOR GRAPHICS CORPORATION OR ITS LICENSORS.-/-/LIBRARY ieee ;use IEEE.std_logic_1164.all ;use IEEE.std_logic_arith.all ;package dualport_ram_be_pkg is component dualport_ram_be gen

38、eric (ram_id : integer; words : integer; width : integer; addr_width : integer; a_reset_active : integer; s_reset_active : integer; enable_active : integer; re_active : integer; we_active : integer; num_byte_enables : integer; clock_edge : integer; num_input_registers : integer; num_output_registers : integer; no_of_dualport_readwrite_port : integer ); port ( data_in : in STD_LOGIC_VECTOR(no_of_dualport_readwrite_port * width) - 1 downto 0) ; addr : in STD_LOGIC_VECTOR(no_of_dualport_readwrite_port * addr_width) - 1 downt