数据压缩与信源编码Huffman编码压缩.docxVIP

数据压缩与信源编码大作业一----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）默认码表法 / 两遍扫描的基本方法 / 自适应压缩方法 任选其一。算法流程两遍扫描法进行Huffman压缩编码算法流程编码开始概率统计建立码树/码表传送码表编码-传送压缩码流编码结束Huffman解码算法流程解码开始接收码表恢复码树/码表接收压缩码流解码-恢复原码解码结束程序设计说明两遍扫描法进行Huffman压缩编码算法程序说明首先，决定程序好坏优劣以及算法实现难易程度的重要因素便是程序的数据结构。本程序使用了两个数据结构：typedef struct{ char elem; unsigned int m_weight; unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree; typedef struct weight{ char elem; unsigned int m_weight;}Weight;第一个数据结构是为了建立Huffman树而用结构体构造的结构体。其中的成员包括ASCII码的名字elem,权重m_weight（有第一次扫描得到的频数决定），以及用来建立二叉树的父节点，左右孩子节点。第二个数据结构是第一扫描统计各个ASCII码得到的频数而建立的结构体。其次是实现算法的函数。第一步，我们要对文本的内容进行扫描，统计，并且记录下来，在这里使用了方法是：对扫描得到的ASCII码进行从开始进行匹配，有两种情况：第一，改码已经出现则，直接让对应的权值W_weight增加1；第二，如果扫描遍历后发现没有，则码字总类k增加1，将该新的码字赋给新的结构体，权值设为1。重复值文件扫描结束。第二步，需要对其进行Huffman树的创立，并且要对其进行编码，生成Huffman压缩码。首先，根据Huffman二叉树的算法，我们需要先得到权值最小的两个码字。这里程序中使用了void Select(HuffmanTree HT,int n,int *s1,int *s2)函数，用最简单的比较方法就开变了得出，并通过指针参数s1,s2传递。得到最小的两个后，我们通过函数void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)进行Huffman编码实现。算法思想即为普通的二次扫描编码的方法，详细见程序的该函数部分的内容和注释。第三步，将编好的Huffman码写入到压缩文件中，再一次对文件正文进行扫描，没扫描到一个就用编号的Huffman码代替相关的ASCII码。在这之前，考虑到和解码的相对应，在写入到压缩文档之前。需要提供一些信息给解压缩程序，其中包括，文本的大小，用size表示，文本总的总类数目，用k表示，每种ASCII码对应的Huffman码，按照Huffman树的顺序。第四部，输出产生相应的文件即可，同时打印出压缩前后的文件的大小，为计算压缩比提供依据。Huffman解码算法程序说明第一步，读出文件的前部分内容，包括对应的文本的大小，用size表示，文本总的总类数目，用k表示，每种ASCII码对应的Huffman码。然后就可以恢复出Huffman数。这里用到unsigned int Read()函数和unsigned int Readk(unsigned int k)，这两个函数可以配合着实现Huffman码的读取，详细见程序及其对应的注释。第二部，扫描全文，将之与Huffman码进行匹配，每次匹配均从根节点开始，知道左右节点没有，这样不会出现重复。扫描至文档结束即可。程序压缩性能评价经过压缩，abc.txt的大小 20,370Byte,压缩后的abc_code的大小= 12,165Byte。则：压缩率：r===0。597可见，其压缩率并不是特比高。分析：因为文件大小仅为20K左右，经过程序对文件的分析，文件中所含有的ASCII码值得种类为77中，Huffman编码最大码长l=8（注意，因为存储方法按字节，所以这里8bit就可以），在存储Huffman编码时浪费B