第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
Huffman编码的c和matlab实现.pdf
实验二 Huffman 编码
一．实验的目的和要求
熟练掌握应用 Huffman 编码算法进行文件的压缩和还原，在标准测试文集上检查其
压缩效率
二．实验重点与难点
1．重点：Huffman 编码算法。
2．难点：对文件进行操作。
三．实验学时
本次实验 4 学时。
四．实验内容
根据信源压缩编码——Huffman 编码的原理，制作对英文文本进行压缩和解压缩的软
件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计
报告、编码报告、压缩程度信息报告、码表存储空间报告。
五、实验原理介绍
1）Huffman 算法简介
Huffman 算法是一种用于数据压缩的算法，由D.A.Huffman 最先提出。该算法的核心
部分为Huffman 编码树（Huffman coding tree），一棵满二叉树。所有可能的输入符号（通
常对应为字节）在Huffman 编码树上对应为一个叶节点，叶节点的位置就是该符号的
Huffman编码。具体来说，一个符号对应的Huffman 编码就是从根节点开始，沿左子节点（0）
或右子节点（1）前进，一直找到该符号叶节点为止的路径对应的二进制编码。在Huffman 编
码树的基础上，该算法的编码部分输入一系列的符号，根据Huffman 树对符号进行翻译，
以符号在Huffman 树上的位置作为编码结果。解码部分反之，根据输入的Huffman 编码，
通过查询Huffman 树翻译回原始符号。
通过对出现几率高的符号赋以较短的编码、对出现几率低的符号赋以较长的编码，可以
有效的对输入数据进行压缩，这也就是Huffman 编码提出的目的。而如何构造出编码树，
便成为一个重要的问题。
建立静态Huffman 编码树的过程相对简单。首先，按照权重值的大小将符号集合排序。
接着，取出权重值最小的两个集合元素作为叶节点组成一棵子树，子树的父节点的权重值为
两个叶节点的权重值之和。然后从符号集合中删除上述权重值最小的两个集合元素,并将新
产生的父节点放回原来的集合中，并保持集合有序。重复上述步骤，直至集合中只剩下一个
元素，则Huffman 编码树构造完成。
在实际应用中,Huffman 编码树是用一个结构数组来存储的,该结构一般为
struct{
}
unsigned long count;//权重值
int parent, lchild, rchild;//左、右子树及父节点在数组中的序号
如果我们要对n个字符进行Huffman编码，则该结构数组含2n-1个元素,其中前n个元素为叶子
节点，保存了该n个字符的权重等数据，后n-1个元素为父节点，第2n-1个元素为根节点。
2）Huffman 算法用于文件压缩与解压缩
如果我们要对一个文本文件进行压缩与解压缩，其基本流程如下
压缩流程：
读取扫描文本文件——〉统计字符频率——〉生成码字——〉保存压缩文件
解压缩流程：
读取扫描压缩文件——〉提取字符频率——〉生成码树——〉保存文本文件
在此过程中我们要解决如何读取文件和保存文件问题，特别要解决的问题是如何将编码
一位一位保存至文件中，又如何一位一位地从编码文件中读出，并利用 Huffman 树译码出来。
六、需用的仪器等
硬件：计算机。
软件：VC 或 VB 或 Matlab 等语言开发环境及卡乐加里文集或坎特伯雷文集。
七．实验步骤
1） 选择用来检验无失真压缩算法的测试文集；
2） 采用 Huffman 算法编写压缩程序，对以上文件进行压缩，形成新的压缩文件；
3） 编写解码程序，检验压缩程序的正确性；
4） 统计各文件在压缩前后的大小，并计算各自的数据压缩率；
5） 用其它压缩程序，对你选用的文集进行压缩，比较各自的压缩效率。
八．考核要求
程序是否正确运行。
九．实验报告要求
实验报告要求填写所用标准文集、压缩率，与其它压缩程序的比较，并附程序。
十．思考题
1）Huffman 树是怎样生成的？
2）如何进行位操作，以确保能够一位一位地将编码保存至文件中及从编码文件中读出？
3）生成的编码文件中除了保存每个字符的编码外，还要保存一些什么数据？
十一．附录
1）．用 C 实现 Huffman 编码
//huffman.c
#include
#include
#include "bitio.h"
typedef struct{
unsigned long count;
int parent, lchild, rchild;
} HNODE;
HNODE hTree[512];
typedef struct{
unsigned long code;
int codelength;
} HCODE;
HCODE hCode[256];
unsigned long counts[256];//保存所有 256 个 ASCII 码字符的出现次数
void BuildCounts( FILE *fp);
int BuildTree( void);
void BuildCode( void);
void HuffmanEncode( FILE *fp, BITFILE *bf);
void HuffmanDecode( BITFILE *bf, FILE *fp);
//统计文件中字符出现的次数,存在数组 counts 中
void BuildCounts( FILE *fp){
int c;
for( c=0; c<256; c++) counts[c] = 0;
while( EOF!=(c=fgetc(fp))) counts[c]++;
}
/*构造 Huffman 树,它实际上是一个结构数组,每一个元素是一个 HNODE 结构.
该数组中前 256 个元素(hTree[0]-hTree[255])作为树的叶子,但生成树时,
只有那些 hTree[i].count>0 的节点才被作为 Huffman 树的叶子,设这样的节
点有 r 个.
该数组中后 255 个元素(hTree[256]-hTree[510])作为树的父节点,
但生成树时,只有 hTree[256]-hTree[254+r]的节点才被作为 Huffman 树的父
节点,它可以通过 hTree[i].lchild>0 来识别它.
该数组中第 512 个元素(hTree[511])作为比较用.
从根至叶子 hTree[i](i<256)的路径按左 0 右 1 的方式可以给出
ASCII 码为 i 的字符的 Huffman 码.或者说叶子 hTree[i]对应的字符是 ASCII 码为 i 的字
符*/
hTree[i].count = counts[i];
hTree[i].parent = 0;
hTree[i].lchild = 0;
hTree[i].rchild = 0;
int BuildTree( void){
int i;
int min1, min2, nextfree;
//初始化叶子节点,如果 counts[i]>0,该节点作为 huffman 树中的叶子节点
for( i=0; i<256; i++){
}
//初始化内部节点,将可能成为父节点
for( i=256; i<512; i++){
hTree[i].count = 0;
hTree[i].parent = 0;
hTree[i].lchild = 0;
hTree[i].rchild = 0;
}
hTree[511].count = 0xFFFFFFFFL;//它用作比较,保存一个最大数
nextfree = 256;//父节点从第 256 个元素开始
for( ;;nextfree++){
//先求 counts 最小的两个节点,min1 是最小节点的下标,min2 是次最小节点的下标
min1=min2=511;
for( i=0; i
parentNode=hTree[currentNode].parent;//当前节点的父节点
for( ; 0!=parentNode;){
if( currentNode == hTree[parentNode].rchild)
mask <<= 1;//左移一位,因为是从叶子到根节点,所以产生的编码应该是从低位
code |= mask;//与 mask 按位或
至高位
codelength++;//码长加 1
currentNode=parentNode;//下面继续考虑当前节点的父节点,将当前节点置为它
的父节点
}
hCode[n].code = code;
hCode[n].codelength = codelength;
parentNode=hTree[parentNode].parent;//新的当前节点的父节点
}
}
//对一个文件*fp 中进行编码,结果保存在另一个文件*bf 中
void HuffmanEncode( FILE *fp, BITFILE *bf){
unsigned long filelength;
int i;
BuildCounts( fp);//统计文件中各字符出现的次数
fseek( fp, 0, SEEK_END);//文件指针移动到文件末,目的是为了下面用 ftell 计算文件长度
/*获取文件长度,当文件指针移动到文件末后,用 ftell 就可读出此刻的文件指针位置相对
于
位
文件开始的差，这样就得到了文件的长度*/
filelength = ftell( fp);
BitsOutput( bf, filelength, 4*8);//存入文件长度,占 32 位
for( i=0; i<256; i++) BitsOutput( bf, counts[i], 4*8);//存入字符出现的次数,每字符数占 32
BitsOutput( bf, hCode[i].code, hCode[i].codelength);//根据编码长度,存入字符对应的
BuildTree( );
BuildCode( );
fseek( fp, 0, SEEK_SET);
while( EOF!=(i=fgetc(fp))){
编码
}
}
//对一个文件*bf 中进行译码,结果保存在另一个文件*fp 中
void HuffmanDecode( BITFILE *bf, FILE *fp){
unsigned long filelength;
int i;
int rootNode;
int node;
/*从根开始,每从文件 bf 中读取一位,根据它是 0 还是 1,
fputc( node, fp);//将 ASCII 码为 node 的字符写入文件 fp
filelength --;//继续翻译下一个字符
fprintf( stdout, "使用说明: %s \n", argv[0]);
fprintf( stdout, "\t: E 或 D 表示 编码或译码\n");
fprintf( stdout, "\t: 输入文件名\n");
fprintf( stdout, "\t: 输出文件名\n");
return -1;
node = rootNode;
do{
}while( 255argc){
}
if( 'E' == argv[1][0]){ // 进行编码
}else if( 'D' == argv[1][0]){
fp = fopen( argv[2], "rb");
bf = OpenBitFileOutput( argv[3]);
if( NULL!=fp && NULL!=bf){
}
HuffmanEncode( fp, bf);
fclose( fp);
CloseBitFileOutput( bf);
fprintf( stdout, "编码结束\n");
bf = OpenBitFileInput( argv[2]);
//进行译码
// 其它
fprintf( stderr, "其它操作不能运行!\n");
HuffmanDecode( bf, fp);
fclose( fp);
CloseBitFileInput( bf);
fprintf( stdout, "译码结束\n");
fp = fopen( argv[3], "wb");
if( NULL!=fp && NULL!=bf){
}
}else{
}
return 0;
}
//有关文件操作的 c 文件,主要实现对文件的位操作
#include
#include
#include "bitio.h"
BITFILE *OpenBitFileInput( char *filename){
BITFILE *bf;
bf = (BITFILE *)malloc( sizeof(BITFILE));
if( NULL == bf) return NULL;
if( NULL == filename) bf->fp = stdin;
else bf->fp = fopen( filename, "rb");
if( NULL == bf->fp) return NULL;
bf->mask = 0x80;
bf->rack = 0;
return bf;
}
BITFILE *OpenBitFileOutput( char *filename){
BITFILE *bf;
bf = (BITFILE *)malloc( sizeof(BITFILE));
if( NULL == bf) return NULL;
if( NULL == filename) bf->fp = stdout;
else bf->fp = fopen( filename, "wb");
if( NULL == bf->fp) return NULL;
bf->mask = 0x80;//10000000 或 128
bf->rack = 0;
return bf;
}
void CloseBitFileInput( BITFILE *bf){
fclose( bf->fp);
free( bf);
}
fprintf(stderr, "Read after the end of file reached\n");
exit( -1);
bf->rack = fgetc( bf->fp);//读取一个字符
if( EOF == bf->rack){
}
void CloseBitFileOutput( BITFILE *bf){
// Output the remaining bits
if( 0x80 != bf->mask) fputc( bf->rack, bf->fp);
fclose( bf->fp);
free( bf);
}
//从 bf 中读取一位,返回 0 或 1
int BitInput( BITFILE *bf){
int value;
if( 0x80 == bf->mask){//可以读取下一个字节内容
}
/*当前字符 bf->rack 通过和某位为 1 的数据 bf->mask
执行位与运算,得字符 bf->rack 的该位的值(0 或 1)*/
value = bf->mask & bf->rack;
bf->mask >>= 1;//右移一位,准备获取从左至右的下一位的数据
/*当 bf->mask 为 0 时,说明一个字节内容已经一位一位读完,需要
重新读取下一字节的内容,所以再次设置 bf->mask = 0x80*/
if( 0==bf->mask) bf->mask = 0x80;
return( (0==value)?0:1);//返回 0 或 1
}
//从 bf 中读取 count 位,以一个无符号长整型数据返回它
unsigned long BitsInput( BITFILE *bf, int count){
unsigned long mask;
unsigned long value;
//将 1 移到(从右至左)第 count 位,以便控制读取 count 个字符
mask = 1L << (count-1);
value = 0L;
while( 0!=mask){
}
return value;
}
if( 1 == BitInput( bf))
mask >>= 1;
value |= mask;//进行位或运算,将当前读到的 1 放到 value 的相关位
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
