文件压缩程序设计报告
- 格式:doc
- 大小:272.50 KB
- 文档页数:22
课程设计报告
课程名称:操作系统
实验题目:文件压缩程序
院系:计算机科学与工程学院
班级:
姓名:
学号:
二○一一年七月一日
一、需求分析:
有两种形式的重复存在于计算机数据中,文件压缩程序就是对这两种重复进行了压缩。
一种是短语形式的重复,即三个字节以上的重复,对于这种重复,压缩程序用两个数字:1.重复位置距当前压缩位置的距离;2.重复的长度,来表示这个重复,假设这两个数字各占一个字节,于是数据便得到了压缩。
第二种重复为单字节的重复,一个字节只有256种可能的取值,所以这种重复是必然的。给256 种字节取值重新编码,使出现较多的字节使用较短的编码,出现较少的字节使用较长的编码,这样一来,变短的字节相对于变长的字节更多,文件的总长度就会减少,并且,字节使用比例越不均匀,压缩比例就越大。
编码式压缩必须在短语式压缩之后进行,因为编码式压缩后,原先八位二进制值的字节就被破坏了,这样文件中短语式重复的倾向也会被破坏(除非先进行解码)。另外,短语式压缩后的结果:那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性,因此,两种压缩方式的顺序不能变。
本程序设计只做了编码式压缩,采用Huffman编码进行压缩和解压缩。Huffman 编码是一种可变长编码方式,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。根据ascii 码文件中各ascii 字符出现的频率情况创建Huffman 树,再将各字符对应的哈夫曼编码写入文件中。同时,亦可根据对应的哈夫曼树,将哈夫曼编码文件解压成字符文件.
二、概要设计:主程序流程图:
压缩过程的实现:
压缩过程的流程是清晰而简单的:
1. 创建Huffman 树
2. 打开需压缩文件
3. 将需压缩文件中的每个ascii 码对应的huffman 编码按bit 单位输出生成压缩文件压缩结束。
其中,步骤1和步骤3是压缩过程的关键。
步骤1:这里所要做工作是得到Huffman数中各叶子结点字符出现的频率并进行创建.统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件,“实时”的生成各字符的出现频率;或者是创建前即做好统计.这里采用的是前一种方法。
步骤3: 将需压缩文件中的每个ascii 码对应的huffman 编码按bit 单位输出. 这是本压缩程序中最关键的部分:
这里涉及“转换”和“输出”两个关键步骤:“转换”部分大可不必去通过遍历Huffman 树来找到每个字符对应的哈夫曼编码,可以将每个Huffman 码值及其对应的ascii 码存放于如下所示的结
构体中:
解压缩过程的实现:
如果说,压缩的过程可以通过查找codeList 来加速实现的话,而解压缩则必须通过查找huffman 树才能加以实现.查找的过程是简单的,可以根据
huffman 树的性质来做,当haffCode的当前bit 位为0 时,则向左枝展开搜索;当前bit 位为1时,则向右枝展开搜索,当遇到叶子结点时,则输出haffCode对应的asciiCode。
三、详细设计:
核心算法源程序:
Huffman树建立源程序:
//-------------------------------------------------------------
//huffmantree.h
//霍夫曼树
#ifndef HUFFMANTREE
#define HUFFMANTREE
#define Defaultsize 300
#include
#include "bintree.h"
#include "heap.h"
class Code
{
public:
int code;
Code *link;
Code(int c=0,Code *l=NULL):code(c),link(l){};
};
class CharNameNode
{
public:
unsigned char charname; //要这样才行
Code *link;
CharNameNode(unsigned char c=0,Code *l=NULL):charname(c),link(l){};
};
template
class HuffmanTree:public BinaryTree
{
public:
int key;
HuffmanTree(){};
HuffmanTree(HuffmanTree
{
Type temp=0; //可能有变
key=ht1.key+ht2.key;
root= new BinTreeNode
}
void Build(int *fr,Type *value,int n,HuffmanTree
void Path(BinTreeNode
};
template
void HuffmanTree
int i;