Huffman编解码实验报告

文本文件的二进制预统计 Huffman编解码 一、实验目的 (1) 熟悉 Huffman编解码算法； (2) 理解 Huffman编码的最佳性。 二、实验内容 1、编程思想 霍夫曼（Huffman）编码是 1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。 计算机编程实现时，首先统计带编码的文本文件中各个字符出现的概率，然后将概率作为节点的权值构建 huffman树。编码时从叶子节点出发，如果这个节点在左子树上，则编码 0，否则编码 1，直到根节点为止，所得到的 01序列即为该叶子节点的编码。所有叶子节点的编码构成一个码本。 有两种译码方法：(1)按位读入码字，从已建好的 Huffman树的根节点开始，若码字为“0”，则跳到左子树，若为“1”则跳到右子树，直到叶子结点为止，输出叶子接点所表示的符号。（2）由于 Huffman编码是唯一码，还有另一种译码方法，每读入一位编码就去码本中去匹配相应的码字，若匹配不成功，则继续读入下一个编码，直到匹配成功为止。显然前一种方法比较简便，本程序采用便是该方法。 2、程序流程图 3、编程实现 本实验采用用 C语言程序语言，VC++ 6.0编程环境。 (1)数据结构 构造存放符号及其权值的存储结构如下 typedef struct { unsigned char symbol; //符号的 ASCII码值 int sweight; //权值 }syml_weit; syml_weit *sw; N NYYN 开始编码 读入文本文件 统计各符号概率 构建 Huffman树 保存码本 读入 1 位码字 编码 输出编码文件 编码结束 开始译码 读入码本 定位到根节点 码字为 1？ 跳到右子树 译码结束 叶子结点？ ？ 跳到左子树 输出字符 Y码字读完？ 构造huffman树存储结构如下： typedef struct { int weit; //权值 int lchd; //左孩子地址 int rchd; //右孩子地址 int part; //双亲地址 }hufmtree; hufmtree *htree; (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----计算文本文件中各符号的...