下载此文档

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


文档分类:高等教育 | 页数:约28页 举报非法文档有奖
1/28
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/28 下载此文档
文档列表 文档介绍
数据压缩与信源编码大作业一
----Huffman编解码实现
实验目的
(1)通过本次实验,加深对Huffman编码算法思想的理解,掌握Huffman
编码的基本规则,熟悉并且理解Huffman编码的基本步骤。在此基础上,能够通过编写C语言代码实现Huffman编码的编写压缩工作。
(2)通过实现Huffman编码压缩工作,进一步进行解码工作,并且用C
语言实现,以此进一步加深理解。
实验内容
(1)编写Huffman压缩程序Huffman_Code ,压
;
(2)编写Huffman解压缩程序Huffman_Decode 对*,恢复结果存储在*;
(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码进行匹配,每次匹配均从根节点开始,知道左右节点没有,这样不会出现重复。扫描至文档结束即可。
程序压缩性能评价
经过压缩,= 20,370Byte,压缩后的abc_code的大小S2= 12,165Byte。则:
压缩率:r=S2S1=1216520370=0。597
可见,其压缩率并不是特比高。
分析:因为文件大小仅为20K左右,经过程序对文件的分析,文件中所含有的ASCII码值得种类为77中,Huffm

数据压缩与信源编码Huffman编码压缩 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数28
  • 收藏数0 收藏
  • 顶次数0
  • 上传人陈潇睡不醒
  • 文件大小40 KB
  • 时间2018-04-17