Huffman编解码实验报告

文本文件的二进制预统计Huffman编解码

一、实验目的

(1) 熟悉Huffman编解码算法； (2) 理解Huffman编码的最佳性。 二、实验内容

1、编程思想

霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。

计算机编程实现时，首先统计带编码的文本文件中各个字符出现的概率，然后将概率作为节点的权值构建huffman树。编码时从叶子节点出发，如果这个节点在左子树上，则编码0，否则编码1，直到根节点为止，所得到的01序列即为该叶子节点的编码。所有叶子节点的编码构成一个码本。

有两种译码方法：(1)按位读入码字，从已建好的Huffman树的根节点开始，若码字为“0”，则跳到左子树，若为“1”则跳到右子树，直到叶子结点为止，输出叶子接点所表示的符号。（2）由于Huffman编码是唯一码，还有另一种译码方法，每读入一位编码就去码本中去匹配相应的码字，若匹配不成功，则继续读入下一个编码，直到匹配成功为止。显然前一种方法比较简便，本程序采用便是该方法。

2、程序流程图

开始编码 开始译码 读入文本文件 读入码本 统计各符号概率 定位到根节点 构建Huffman树 N 读入1位码字 保存码本 码字为1？ Y编码 跳到左子树 跳到右子树 输出编码文件 叶子结点？ ？ Y输出字符 NN 编码结束 码字读完？ Y译码结束

3、编程实现

本实验采用用C语言程序语言，VC++ 6.0编程环境。 (1)数据结构

构造存放符号及其权值的存储结构如下 typedef struct {

unsigned char symbol; //符号的ASCII码值 int sweight; //权值

}syml_weit;

syml_weit *sw;

sw

symbol sweight

构造huffman树存储结构如下：

typedef struct {

int weit; //权值

int lchd; //左孩子地址 int rchd; //右孩子地址 int part; //双亲地址 }hufmtree;

hufmtree *htree;

htree

weit lchd rchd part;

(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[]=\

int FileLen; //读入的文件长度 DataBuf = new unsigned char[1024*1024];

{ }

FILE *lp; int i=0;

DCodeBuf = new unsigned char[1024*1024]; while (i

int p=totalnode-1; while (p>=leafnode) {

if (*(CDataBuf+i)==1) p=htree[p].rchd; else

p=htree[p].lchd; i++; }

*(DCodeBuf+DCodeLen) = sw[p].symbol; DCodeLen++; }

本文来源：https://www.bwwdw.com/article/3dex.html