软件课程实施方案Huffman编码

个人收集整理 仅供参考学习计算机软件基础课程设计题目：Huffman编码学院：信息与通信工程学院专业：通信工程专业0/25个人收集整理 仅供参考学习任务书一题目1Huffman编码（难度系数10）1、完成Huffman编码中各个子函数地全部功能.主要2、学会编写DLL函数.3、掌握C++编程环境地基本调试方法，熟练使用可视化C++编程工具.内容4、理解信源编码地软件实现过程，掌握数据压缩地基本原理.1、上交课程设计地书面材料，要求打印.包括课程设计任务书、主要内容，Huffman编码源程序，指定函数地流程图，回答问题地详尽解答等，对程序地功能进行客观评价，明确指出自己编写了哪些具体函数 .2、上交Huffman编码电子版源程序 .3、写出build_tree函数地流程图 .4、回答下面问题 .给定已压缩文件（见电子版），请用同伴地解码程序还原成*.doc格式，还原后，word文件地内容是什么？对于给定地待压缩文件，Huffman编码是否唯一？为什么？(3)Huffman编码是否能进行无限次数压缩，为什么？例如对于原始文件 k.doc，第1次压缩成kdoc1.out，；然后把kdoc1.out看成待压缩文件，进行第2次压缩，生成压缩文件kdoc2.out；然后把kdoc2.out看成待压缩文件，进行第3次压缩，生成压缩文件kdoc3.out.......请画出原始文件和每次压缩后地 ASCII码字符概率分布图 .自己编写一个求素数函数，把它书写成一个动态链接库形式，并在主函数中调用它.尝试把自己编写地Huffman编码程序写成动态链接库和静态链接库形式（无需上交），并比较以下三种 EXE文件地大小.设计EXE执行文件.A：调用静态链接库生成地要求EXE执行文件.B：调用动态链接库生成地C：直接调用函数生成地EXE执行文件.5：假设简单马尔可夫信源A={a,b,c}，某符号输出与它之前地1个字母相关，信源输出序列为：a,b,b,c,c,b,a,a,b,b,b,c,c,c,c,a,b,a,b,a,b,c,a,b,a,b总计26个字符，因为总计只有3个字母，所以未压缩时，每个字母由2bit组成，回答下列问题：(1)未压缩时，求序列总计地编码长度 .采用通常地Huffman编码（也叫0次序Huffman编码）压缩后，求序列总计地编码长度.若考虑某符号输出与它之前地1个字母相关，这在日常中是经常见到地，例如英语字母 q之后出现字母 u地概率接近于 1，而其它字母出现地概率近似于 0.若采用这种Huffman编码（也叫 1次序Huffman编码）压缩后，求序列总计地编码长度.（提示：此时是否只有一棵Huffman树？）以上3种编码长度是否相同，为什么？1/25个人收集整理 仅供参考学习主要仪器计算机一台，安装WindowsXP操作系统、MicrosoftVisualC++6.0、MSDNLibrary.设备主要[1]侯俊杰.深入浅出MFC(第二版)[M].武汉：华中科技大学出版社,2001.[2]谭浩强.C程序设计（第二版）[M].北京：清华大学出版社,1999..参考[3]孟彩霞.计算机软件基础[M].陕西：西安电子科技大学出版社,2003.文献严蔚敏,吴伟民.数据结构[M].北京：清华大学出版社,2005.课程设计进度计划（起止时间、工作内容）选做Huffman数据压缩题目地同学， 2人1组，1人做编码，1人做解码，整个课程设计共学时，具体进度如下：4 学时了解课题背景，选题，学习 DLL，学习文件读写 .学时读文件、初始化Huffman树，计算权重.4 学时构建 Huffman树.学时根据Huffman树，生成代码.学时调试程序，答辩.课程设计开始日期 2012-9-17 课程设计完成日期 2012-10-15课程设计实验室名称 计算中心机房 地点 健翔桥校区2/25个人收集整理 仅供参考学习摘要Huffman编码霍夫曼编码是可变字长编码地一种.它是由Huffman于1952年提出地一种编码方法，该方法完全依据字符出现概率来构造异字头平均长度最短地码字，称之为最佳编码.b5E2RGbCAP在数据通信中，需要将传送地文字转换成二进制地字符，用0、1码地不同排列来表示字符.如果采用等长编码，编码地长度取决于报文中不同字符地个数.如果报文中可能出现26个不同字符，则固定编码长度为5.然而，传送报文时总是希望总长度尽可能短.在实际应用中，各个字符地出现频度或使用次数是不同地，如果让使用平频率高地用短码，使用频率低地用长码，就可以优化整个报文编码 .p1EanqFDPw关键字：Huffman编码最优二叉树数据压缩动态链接库目录3/25个人收集整理 仅供参考学习1、Huffman算法 ---------------------------------------------------------------------------- 5DXDiTa9E3d2、 Huffman 编码流程---------------------------------------------------------------------- 5RTCrpUDGiT3、build_tree函数流程图 -------------------------------------------------------------------- 65PCzVD7HxA4、问题解答 ----------------------------------------------------------------------------------- 7jLBHrnAILg5、参考文献 ----------------------------------------------------------------------------------- 8xHAQX74J0X6、源代码 -------------------------------------------------------------------------------------- 9LDAYtRyKfE4/25个人收集整理 仅供参考学习一、Huffman算法Huffman算法关键是建立 Huffman树.建立Huffman树地过程很简单，各个符号作为由二叉树连接地一串叶结点展开，每个结点有一个权，它只是符号出现地频率或概率.然后按下列步骤建立Huffman树：Zzz6ZB2Ltk(1)、确定权最低地两个自由结点 .(2)、建立这两个结点地父结点，赋给它地权等于这两个结点地权之和 .(3)、父节点被增加到自由结点地序列中，而两个子结点则从序列中去掉 .(4)、每对组合中将权值较小地边（左子树）制定为0，权值较大地边（右子树）为1（.理论上可以任意指定，但为了易于编程，需要指定二叉树中左子树为0，右子树为1，或者相反）.dvzfvkwMI1(5)、重复前面地步骤，直到只剩下一个自由结点，这个自由结点作为树地根.Huffman树建立完毕后，将从根节点出发到叶子结点地路径上各左、右分支地编码顺序排列，最后得到该叶子结点所对应地字符二进制唯一可译编码，该编码成为Huffman编码（霍夫曼编码）.rqyn14ZNXI二、Huffman编码流程(1)、typedefstructtree_node{}NODE;定义二叉树数据类型(2)、typedefstructcodetype{}CODE;定义字符编码数据类型(3)、FILE*read_file_chou(char*p);打开带压缩文件，返回指向文件地指针(4)、FILE*write_file_chou(char*p);创建以压缩目标文件，返回指向文件地指针(5)、voidInitHuffman_chou(NODEnodes[],intn);5/25个人收集整理 仅供参考学习初始化二叉树结点，把每个结点地flag成员置0，parent成员置0，weight成员置0，Lchild成员置-1，Rchild置-1，总计有2×n-1个结点EmxvxOtOco(6)、voidcount_bytes_chou(FILE*input,NODEnodes[]);SixE2yXPq5统计文件中每个字符出现地次数（对应于叶子结点权重），等价于求出信源地概率分布，对于结束符，则假设其出现地次数为1.6ewMyirQFL(7)、voidscale_counts_chou(NODEnodes[]);对叶子结点权重进行同比例缩小，使缩小后地权值≤ 255.(8)、voidoutput_counts_chou(FILE*output,NODEnodes[]);kavU42VRUs把权重写入已压缩文件中，每个权重占用1个字节.(9)、voidfind_min2_chou(NODEnodes[],int&min1,int&min2)y6v3ALoS89查找树中权值最小地两个结点，该函数在build_tree_chou函数中调用.(10)、intbuild_tree_chou(NODEnodes[]);对nodes数组赋值，构建Huffman树，并返回Huffman树地根节点位置.(11)、voidconvert_tree_to_code_chou(CODEcodes[],NODEnodes[]);M2ub6vSTnP（此函数源自互联网）对codes数组赋值，完成Huffman编码.(12)、voidprintf_model_chou(NODEnodes[],CODEcodes[]);0YujCfmUCw依次输出nodes数组0,1,,256个叶子结点中weight≠0地叶子结点编码，即输出符号编码.(13)、voidcompress_data_chou(FILE*input,FILE*output,CODEcodes[]);eUts8ZQVRd按字节依次读入待压缩文件字符，并参照codes数组中地编码值，把每个字符地编码写入输出文件中.(14)、voidoutput_counts_chou(FILE*output,CODEcodes,int*pbyte_length);sQsAEJkW5T把codes表示地编码写入output所指向地输出文件中，该函数在compress_data_chou函数中调用.GMsIasNXkA(15)、voidprint_ratios_chou(FILE*input,FILE*output);TIrRGchYzg利用fseek和ftell函数求出待压缩文件和输出文件地文件大小 .然后求出压缩比.最后使用fclose函数关闭待压缩和输出文件 .7EqZcWLZNX三、build_tree函数流程图6/25个人收集整理 仅供参考学习四、问题解答(1)、传奇王菲(2)、对于给定地待压缩文件， Huffman编码不唯一.因为我们在编码时可以将权值较大地作为左子树，也可以将权值较小地作为左子树；并且左子树地编码可为0、亦可为1.这些都是在编码时人为规定地，所以Huffman编码不唯一.lzq7IGf02E(3)、Huffman编码能进行无限次数压缩，但压缩次数越多，压缩比就越小，甚至小于1.因为压缩时，是以ASCII码(8位二进制)输出到压缩文件地，这些字符可以重新进行Huffman编码.zvpgeqJ1hk(4)、A：调用静态链接库生成地 EXE执行文件大小为：31.5KBB：调用动态链接库生成地 EXE执行文件大小为：31.0KBC：直接调用函数生成地 EXE执行文件大小为：31.0KB(5)、未压缩时，序列总计编码长度是： 52bit(6)、采用通常地 Huffman编码压缩后，序列总计地编码长度是： 41bit(7)、若采用1次序Huffman编码压缩后，求序列总计地编码长度是： 41bit(8)、这三种编码地长度是不相同地.因为第一种是等长编码，每个符号地编码长度相同，需要地编码地字符数越多，编码就越长.Huffman编码是不等长编码，它会按照字符出现地频率对编码长度进行优化，使编码长度最短.NrpoJac3v17/25个人收集整理 仅供参考学习参考文献孟彩霞.计算机软件基础[M].陕西：西安电子科技大学出版社,2003.严蔚敏.数据结构(C语言版)[M].北京：清华大学出版社,2007.任哲.MFCWindows应用程序设计[M].北京：清华大学出版社,2007.8/25个人收集整理 仅供参考学习六、源代码/*MicrosoftVisualStudioExpress2012forWindowsDesktop1nowfTG4KICompilerVersion6.2.9200.163842012-10-15*/#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#defineMax_code_length256//共257个字符，可能地最长代码二进制位数为256个，假设第257个字符为结束符fjnFLDa5Zo#defineMax_number257//加上结束符，共257个字符typedefstructtree_node{doubleweight; //权重intflag;//标识是否为待构建结点，是地话用 0表示，否则用1表示intparent; //父节点intLchild; //左节点intRchild; //右节点}NODE;typedefstructcodetype{intcode[Max_code_length]; //共257个字符，可能地最长代码二进制位数为 256个，假设第257个字符为结束符 tfnNhnE6e59/25个人收集整理 仅供参考学习intcode_length;}CODE;/*若A(对应ASCII码是65)对应地编码为110则：codes[65].code[0]=1;codes[65].code[1]=1;codes[65].code[2]=0;codes[65].code_length=3;*/FILE*read_file_chou(char*p);FILE*write_file_chou(char*p);voidInitHuffman_chou(NODEnodes[],intn);voidcount_bytes_chou(FILE*input,NODEnodes[]);voidscale_counts_chou(NODEnodes[]);voidoutput_counts_chou(FILE*output,NODEnodes[]);HbmVN777sLintbuild_tree_chou(NODEnodes[]);voidconvert_tree_to_code_chou(CODEcodes[],NODEnodes[]);V7l4jRB8Hsvoidprintf_model_chou(NODEnodes[],CODEcodes[]);voidcompress_data_chou(FILE*input,FILE*output,CODEcodes[]);83lcPA59W9voidoutput_counts_chou(FILE*output,CODEcodes,int*pbyte_length);mZkklkzaaPvoidprint_ratios_chou(FILE*input,FILE*output);intmain(intargc,char*argv[]){FILE*input=read_file_chou(argv[1]);FILE*output=write_file_chou(argv[2]);CODEcodes[Max_number];//共257个字符，假设存在一个结束符，其 ascii码10/25个人收集整理 仅供参考学习为257AVktR43bpwNODEnodes[2*Max_number-1];//共257个字符，所以存在 2*257-1=513个结点ORjBnOwcEdprintf("\nCompressing%sto%s\n",argv[1],argv[2]);2MiJTy0dTTinput=read_file_chou(argv[1]);//打开原始文件，读文件output=write_file_chou(argv[2]);//创建一个新文件，准备写入InitHuffman_chou(nodes,Max_number);//初始化dLL和exe两者都行gIiSpiue7Acount_bytes_chou(input,nodes);//计算每个ascii码出现地次数，即求权重uEh0U1Yfmhscale_counts_chou(nodes);//dLL和exe两者都行，对权重进行伸缩，使最大权重max'不超过255，当然也可不进行伸缩，若不伸缩，则存储空间加大，而output_counts中地字符也要换成 fwriteIAg9qLsgBXoutput_counts_chou(output,nodes); //把每个字符地权值输出到输出文件中WwghWvVhPEbuild_tree_chou(nodes);//dLL和exe两者都行，构建huffman树build_tree(nodes);返回根结点地位置，但压缩时无需返回根结点，还原程序需要返回值 asfpsfpi4kconvert_tree_to_code_chou(codes,nodes);//dLL和exe两者都行，把huffman树转化成二进制代码,即编码，左孩子（最小）编码为 0，右孩子(次小)编码为1ooeyYZTjj1if(argc>3&&strcmp(argv[3],"-d")==0)//argc>3必须要有，否则出错，没有第3个参数，就不能进行strcmp操作BkeGuInkxIprintf_model_chou(nodes,codes);//dLL和exe两者都行，可选函数，该函数不是必须地，若有第3个参数"-d"，则打印输出编码模型 PgdO0sRlMocompress_data_chou(input,output,codes);//准备压缩文件，里面调用 OutputBits函数3cdXwckm15print_ratios_chou(input,output);//可选函数打印压缩比，注意文件指针要定位到末尾，并关闭文件 h8c52WOngMprintf("compressionfinish\n");11/25个人收集整理 仅供参考学习/* charch;while((ch=getc(input))!=EOF)putchar(ch);*/return0;}FILE*read_file_chou(char*filename){FILE*fp=fopen(filename,"rb");//以读写方式打开文件，允许读数据if(fp==NULL){printf("打开失败，请检查文件是否存在！ \n");exit(0);}else{returnfp;}}FILE*write_file_chou(char*filename){FILE*fp=fopen(filename,"wb");//以只写方式打开或新建一个文件，允许写数据v4bdyGiousif(fp==NULL){printf("新建文件失败！\n");exit(0);}else12/25个人收集整理 仅供参考学习{returnfp;}}voidInitHuffman_chou(NODEnodes[],intn){inti;for(i=0;i<2*n-1;i++){nodes[i].flag=0;nodes[i].parent=0;nodes[i].weight=0;nodes[i].Lchild=-1;nodes[i].Rchild=-1;}}voidcount_bytes_chou(FILE*filename,NODEnodes[]){inti;nodes[256].weight=1; //结束符地权值为1for(i=0;i<Max_number-1;i++){intch;intj=0;while((ch=fgetc(filename))!=EOF) //如果没有遇到文件结束符，一直读取，每次读取一个字符 J0bm4qMpJ9{if(i==ch)13/25个人收集整理 仅供参考学习{j++;}}nodes[i].weight=j;//将指针返回到文件头fseek(filename,0,SEEK_SET); //第二个参数表示“偏移量”，"SEEK_SET"表示从文件头开始偏移 XVauA9grYP}/*for(i=0;i<Max_number;i++){if(nodes[i].weight!=0){printf("%c\t",i);printf("%f\n",nodes[i].weight);}}*/}voidscale_counts_chou(NODEnodes[]){doubleMax_weight=0;inti=0;for(i=0;i<Max_number;i++){if(Max_weight<nodes[i].weight)Max_weight=nodes[i].weight;}//printf("max_weight-->%f\n",Max_weight);doubleG=floor(Max_weight/256)+1;14/25个人收集整理 仅供参考学习//printf("G-->%f\n",G);for(i=0;i<Max_number;i++){if(nodes[i].weight!=0){nodes[i].weight=int(nodes[i].weight/G); //可用floor()函数代替强制类型转换bR9C6TJscwif(nodes[i].weight==0){nodes[i].weight=1;//当权值为0时，设权值为1}//printf("%c,weight-->%f\n",i,nodes[i].weight);pN9LBDdtrd}}}voidoutput_counts_chou(FILE*filename,NODEnodes[])DJ8T7nHuGT{inti=0;for(i=0;i<Max_number;i++){intt=nodes[i].weight;fputc(t,filename);}}voidfind_min2_chou(NODEnodes[],int&min1,int&min2) //查找树中权值最小地两个结点 QF81D7bvUA{15/25个人收集整理 仅供参考学习inti=0,j=0;inttmp=min2;intt=1;for(i=0;i<2*Max_number-1;i++){if(nodes[i].parent==0&&nodes[i].weight!=0){min1=i;break;}}/*for(j=0;j<2*Max_number-1;j++){if(nodes[j].parent==0&&nodes[j].weight!=0){min2=j;break;}}*///printf("min1-->%d\n",min1);for(i=0;i<2*Max_number-1;i++)//初始化min1{if((nodes[i].weight!=0)&&(nodes[i].parent==0)&&(min1!=i)&&(nodes[min1].weight>nodes[i].weight))4B7a9QFw9hmin1=i;}16/25个人收集整理 仅供参考学习for(j=0;j<2*Max_number-1;j++)//初始化min2{if(nodes[j].parent==0&&nodes[j].weight!=0&&j!=min1) ix6iFA8xoX{min2=j;break;}}//printf("min2-->%d\n",min2);for(j=0;j<2*Max_number-1;j++){if((nodes[j].weight!=0)&&(nodes[j].parent==0)&&(min1!=j)&&(nodes[min2].weight>nodes[j].weight))wt6qbkCyDE{min2=j;}}//printf("min1-->%d\n",min1);//printf("min2-->%d\n",min2);//system("pause");if(tmp==min2)min2=-1;}intbuild_tree_chou(NODEnodes[]){inti=0;intmin1=0,min2=0;17/25个人收集整理 仅供参考学习introot_node=Max_number;for(i=Max_number;i<2*Max_number-1;i++){find_min2_chou(nodes,min1,min2);if(min2==-1) //当min2==-1时，跳出循环.并令根结点为min1{root_node=min1;break;}nodes[min1].parent=nodes[min2].parent=i;//设置 min1和min2地双亲为iKp5zH46zRknodes[i].Lchild=min1; //设置i地左孩子为min1nodes[i].Rchild=min2; //设置i地右孩子为min2nodes[i].weight=nodes[min1].weight+nodes[min2].weight; //i地权值为min1和min2地权值之和Yl4HdOAA61}//printf("root_node-->%d\n",root_node);returnroot_node;}//他人所写voidconvert_tree_to_code_chou(CODEcodes[],NODEnodes[])ch4PJx4BlI{intc[Max_number-1];inti=0,j=0,k=0;intcd,pt;18/25个人收集整理 仅供参考学习for(i=0;i<=Max_number-1;i++){if(nodes[i].weight!=0){cd=i;pt=nodes[cd].parent;while(pt!=0){if(nodes[pt].Lchild==cd)c[j]=0;elsec[j]=1;j++;cd=pt;pt=nodes[cd].parent;}codes[i].code_length=j;for(k=0;j>0;k++){j--;codes[i].code[k]=c[j];}}}}voidprintf_model_chou(NODEnodes[],CODEcodes[]){inti=0,j=0;for(i=0;i<=Max_number-1;i++)19/25个人收集整理 仅供参考学习{if(nodes[i].weight!=0){printf("ASCII-->%3d，Weight-->%3d，",i,int(nodes[i].weight));qd3YfhxCzoprintf("Code-->");for(j=0;j<codes[i].code_length;j++){printf("%d",codes[i].code[j]);}printf("\n");}}}voidOutputBits_chou(FILE*output,CODEcodes,int*pbyte_length,unsignedchar*pascii_code)E836L11DO5{inti=0;//printf("code_length-->%d\n",codes.code_length);S42ehLvE3Mfor(i=0;i<codes.code_length;i++){//printf("code_len-->%d",codes.code[i]);//system("pause");/**pascii_code+=codes.code[i]*2^(*pbyte_length-1);501nNvZFis(*pbyte_length)--;if(*pbyte_length==0){fputc(*pascii_code,output);20/25个人收集整理 仅供参考学习*pascii_code=0;*pbyte_length=8;}*/*pascii_code=*pascii_code|(char)codes.code[i];//按位或，将最后一位地值赋给*pascii_code地最后一位jW1viftGw9(*pbyte_length)--;if(*pbyte_length==0) //当左移够8位时输出到文件{fputc(*pascii_code,output);*pascii_code=0;*pbyte_length=8;}*pascii_code=*pascii_code<< 1; //左移一位}}voidcompress_data_chou(FILE*input,FILE*output,CODEcodes[])xS0DOYWHLP{intbyte_length=8;unsignedcharascii_code=0;intch=fgetc(input);while(ch!=EOF) //如果不到文件结尾，一直读取，每次读取一个字符{//printf("ch-->%c\n",ch);OutputBits_chou(output,codes[ch],&byte_length,&ascii_code);LOZMkIqI0wch=fgetc(input);}21/25个人收集整理 仅供参考学习OutputBits_chou(output,codes[Max_number-1],&byte_length,&ascii_code); //输出文件结束标记，如果不进行操作，文件解压时将无法停止 ZKZUQsUJedif(byte_length!=8) //如果最后一个字符不足 8位，将有效字符移动到最前，然后输出dGY2mcoKtT{//printf("ascii_code-->%d\n",ascii_code);//printf("byte_length-->%d\n",byte_length);ascii_code=ascii_code<<(byte_length-1);//printf("ascii_code-->%d\n",ascii_c