英文文件的压缩和解压缩

合肥学院

计算机科学与技术系

课程设计报告

2009~2010学年第二学期

课学学专指

业导

班教生

程 数据结构与算法

英文文件的压缩和解压缩

名 号 级

课程设计名称

师 李红 沈亦军

2010 年 6 月

题目:(采用哈夫曼编码思想实现文件的压缩和解压缩功能,并提供压缩前后的占用空间之比)(1)压缩原文件的规模应不小于5K。(2)提供解压缩后文件与原文件的相同性比较功能。

一、问题分析和任务定义。

1.1问题分析

本实验是利用哈夫曼编码思想,设计对一个文本文件中的字符进行哈夫曼编码,生成编码文件(压缩文件);反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。要解决以上问题,需从以下几个方面着手:

(1)如何读入待压缩的文本文件,统计文本文件中各字符的频数及出现的字符个数; (2)如何构造huffman树,进行huffman编码,生成压缩文件(后缀名.txt

(3)如何读入待解压的压缩文件名,并利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码,对文件进行解压,生成解压文件(后缀名为.txt); (4)如何提供压缩前后的占用空间之比

1.2输入、输出数据的形式、值的范围,算法(程序)所能达到的功能 本实验的数据主要是以字符型为主,还有一些自定义的整形和浮点型变量,该实验室对文件进行压缩和解压(被压缩文件容量要求大于>5KB),通过该算法程序可以大致上满足实验所要求的功能,即压缩原文件的规模不小于5KB,提供了压缩后的文件与原文件的压缩比例,也即提供了性能比较功能

1.3 测试用的数据

本实验的数据是通过读入一个名为huffman.txt的文本文档,文档中内容为字符型数据。

所测试的部分数据:

图1.原文档

二、数据结构的选择和概要设计

为了完成实验所要求的任务,解决的问题及方法如下: 1.文件的读取及统计字符出现的个数和频率 (1)文件的读取

void read_file_count() {char c;

ifstream infile;

infile.open(\打开huffman.txt文件 if(!infile)//检查文件是否打开。

{cout<<\不能打开 huffman.txt文件\输出文件未打开的标志 exit(0);}

cout<<\读入的文件中的内容为:\

while((c=infile.get())!=EOF)//EOF是文件结束的标志 cout<

(2)计所出现的字符个数

void char_add(char c) {huff[count].data=c;

huff[count++].count++;//个数增加} (3)计每个字符出现的频率:

bool char_judge(char c) {for(int i=1;i<=count;i++)

if(huff[i].data==c){huff[i].count++;return true;} //如果出现过,出现的频数加1 return false;} 2.构造 huffman树

解决了上述问题,接下来要考虑的是怎样去构造huffman树的问题,进行huffman编码,对文件进行压缩。为了构造huffman树,我将每个字符出现的频率赋予huffman树中叶子结点的权值,从而构造huffman树,也即先查找两个权值最小的结点,合并为新的结点,并将新的结点存入数组中,继续比较合并,最后形成huffman树。 3.huffman编码

利用构造好的huffman树,进行编码:设需要编码的字符集合为{d1,d2,……,dn},各个字符在电文中出现的次数集合为{w1,w2,……,wn},以d1,d2,……,dn作为叶结点,以w1,w2,……,wn作为各叶子结点的权值构造一棵二叉树,规定HUFFMAN树中的左孩子结点为0,右孩子结点为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码就为HUFFMAN编码。 4.文件压缩问题

采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样就能对文件进行压缩。

在计算机存储中,是以二进制来存储的,本来每个字符将占据8位,而通过huffman编码后,一个字符在计算机存储中,将占据的位数少于8位,这样将大大减少存储空间,从而实现对文件的压缩。

5.读入压缩文件,并对其解压。

对如何读取压缩文件,采用的方法大致和开始相同,在此不赘述。为解压,利用构造好

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4