logo资料库

huffman编码完整实验报告.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.07M 资料格式：doc 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    文本文件的二进制预统计 Huffman 编解码 一、实验目的 (1) 熟悉 Huffman 编解码算法； (2) 理解 Huffman 编码的最佳性。 二、实验内容 1、编程思想 霍夫曼（Huffman）编码是 1952 年为文本文件而建立，是一种统计编码。属于无损 压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而 对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信 息的符号长度。 计算机编程实现时，首先统计带编码的文本文件中各个字符出现的概率，然后将概 率作为节点的权值构建 huffman 树。编码时从叶子节点出发，如果这个节点在左子树上， 则编码 0，否则编码 1，直到根节点为止，所得到的 01 序列即为该叶子节点的编码。所 有叶子节点的编码构成一个码本。 有两种译码方法：(1)按位读入码字，从已建好的 Huffman 树的根节点开始，若码 字为“0”，则跳到左子树，若为“1”则跳到右子树，直到叶子结点为止，输出叶子接 点所表示的符号。（2）由于 Huffman 编码是唯一码，还有另一种译码方法，每读入一位 编码就去码本中去匹配相应的码字，若匹配不成功，则继续读入下一个编码，直到匹配 成功为止。显然前一种方法比较简便，本程序采用便是该方法。 2、程序流程图
    开始编码 读入文本文件 统计各符号概率 构建 Huffman 树 保存码本 开始译码 读入码本 定位到根节点 读入 1 位码字 N 码字为 1？ Y 编码 跳到左子树 跳到右子树 输出编码文件 编码结束 N N 叶子结点？ ？ Y 输出字符 码字读完？ Y 译码结束 3、编程实现 本实验采用用 C 语言程序语言，VC++ 6.0 编程环境。 (1)数据结构 构造存放符号及其权值的存储结构如下 typedef struct { unsigned char symbol; int sweight; //符号的 ASCII 码值 //权值 }syml_weit; syml_weit *sw;
    sw symbol sweight 构造 huffman 树存储结构如下： typedef struct { //权值 //左孩子地址 int weit; int lchd; int rchd; //右孩子地址 int part; //双亲地址 }hufmtree; hufmtree *htree; htree weit rchd part; lchd (2)函数 本程序共包含 5 个函数： 一个主函数： void main()， 4 个子函数： void CountWeight(unsigned char *DataBuf,int FileLen); void BuildTree(); void HufmCode(unsigned char *DataBuf,int FileLen); void HufmDCode(unsigned char *CDataBuf,int CDataLen); 其功能分别是： CountWeight----计算文本文件中各符号的权值； BuildTree-------构建 Huffman 树，形成码本； HufmCode---------对文本文件进行编码； HufmDCode-------进行译码。 (3)存储器 本程序共包含 4 个存储器： unsigned char *DataBuf; unsigned char *CodeBook; //存放码本 unsigned char *CodeBuf; //存放编好的码 //存放文本文件数据的内存空间
    unsigned char *DCodeBuf; //存放译码后数据 详细代码见附件。 三、实验结果 程序运行后会形成 3 个文件： codebook.txt-------码本文件； abc_code.txt-------编码文件； abc_dcode.txt------译码文件。 经比较译码后的文件与待编码文件相同，编译码成功实现 为了编写简单，编码文件输出时未采用的比特输出的方式，而采用了字 节输出方式，即每个字节代表一个码字。这样输出文件大小是理论值的 8 倍。 因此计算压缩率时应该除以 8 才是真正的压缩率。 压缩率 = 已编码文件大小/8 待编码文件大小 *100% = 42231/8/9433*100% = 55.96178%
    附件：完整程序代码 #include #include #define MaxNo 256 #define NULL 0 typedef struct { unsigned char symbol; int sweight; }syml_weit; syml_weit *sw; typedef struct { int weit; int lchd; int rchd; int part; }hufmtree; hufmtree *htree; //存放符号及其权值 //存放Huffman树 int leafnode,totalnode; //叶子节点个数 和 整棵树的所有节点 //存放文本文件数据的内存空间 unsigned char *DataBuf; unsigned char *CodeBook; //存放码本 unsigned char *CodeBuf; unsigned char *DCodeBuf; int CodeBookLen; int CodeLen; int DCodeLen; //码本长度 //码长度 //存放编好的码 void CountWeight(unsigned char *DataBuf,int FileLen); void BuildTree(); void HufmCode(unsigned char *DataBuf,int FileLen); void HufmDCode(unsigned char *CDataBuf,int CDataLen); void main() { FILE *fp1,*fp2,*fp3,*fp4; char filepath[]="abc.txt"; int FileLen; DataBuf = new unsigned char[1024*1024]; //文件读取指针 //读入的文件长度
    printf("=====Huffman Code and Decode by LiYingle@NDSC==== \n\n"); if ((fp1=fopen(filepath,"rb"))==NULL) //读入文本文件 { printf("abc open error!"); } FileLen = fread(DataBuf,1,1024*1024,fp1); CountWeight(DataBuf,FileLen); BuildTree(); HufmCode(DataBuf,FileLen); HufmDCode(CodeBuf,CodeLen); //计算权值 //建树 //编码 //译码 ///// 输出码本文件和压缩率 if ((fp2=fopen("codebook.txt","w"))==NULL) { printf("abc_codebook open error!"); } fprintf(fp2,"ASCII WEIGHT for (int i=0;i
    fwrite(DCodeBuf,1,DCodeLen,fp4); fclose(fp1); fclose(fp2); fclose(fp3); fclose(fp4); delete[] DataBuf; delete[] CodeBook; delete[] CodeBuf; delete[] DCodeBuf; } void CountWeight(unsigned char *DataBuf,int FileLen) { int i=0,sum=0; int counter[MaxNo]={0x0}; for (i=0;i
    htree[j].rchd = 0; htree[j++].part = 0; } } } void BuildTree() { int i=0; int j=leafnode;//非叶子节点的开始 int w1,w2;//两个最小的权值 int p1=-1,p2=-1; for (int leaf=0;leaf=w1) { p2 = i; w2 = htree[i].weit; } else { p2 = p1; w2 = w1; p1 = i; w1 = htree[i].weit; } break; } } }
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料