文件压缩程序设计报告

课程设计报告

课程名称：操作系统 实验题目：文件压缩程序

院 系：计算机科学与工程学院 班 级：

姓 名： 学 号：

二○一一年七月一日

一、 需求分析：

有两种形式的重复存在于计算机数据中，文件压缩程序就是对这两种重复进行了压

缩。

一种是短语形式的重复，即三个字节以上的重复，对于这种重复，压缩程序用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩。

第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。给 256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越大。

编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。

本程序设计只做了编码式压缩，采用Huffman编码进行压缩和解压缩。Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。根据 ascii 码文件中各 ascii 字符出现的频率情况创建 Huffman 树，再将各字符对应的哈夫曼编码写入文件中。同时，亦可根据对应的哈夫曼树，将哈夫曼编码文件解压成字符文件.

二、 概要设计：

主程序流程图：

主函数 测试 统计字符，得出统计出的字符的权值n 退出 扫描压缩文件，载入字符信息 输入测试字符串 根据权值进行建立Huffman树 统计字符信息，建立Huffman曼树 输出Huffman树 根据权值进行建立Huffman树 输出Huffman树 编码 根据Huffman树，求得对应字符的Huffman编码 解码 输入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 &ht1,HuffmanTree &ht2) {

Type temp=0; //可能有变 key=ht1.key+ht2.key;

root= new BinTreeNode(0,Copy(ht1.root),Copy(ht2.root)); }

void Build(int *fr,Type *value,int n,HuffmanTree &newtree); void Path(BinTreeNode *start,Code *first,Code *last,CharNameNode *Node,int &i); //一个数组 };

template

void HuffmanTree::Build(int *fr,Type *value,int n,HuffmanTree &newtree) { //fr 为 value(值) 对应的权 int i;

HuffmanTree first,second;

HuffmanTree Node[Defaultsize]; MinHeap< HuffmanTree > hp; assert(n>=0&&n<=Defaultsize); for(i=0;iNode[i].root=new BinTreeNode(value[i],NULL,NULL); Node[i].key=fr[i]; }

hp=MinHeap< HuffmanTree >(Node,n); for(i=0;ihp.RemoveMin(first); hp.RemoveMin(second);

HuffmanTree* temp=new HuffmanTree(first,second); hp.Insert(*temp); }

hp.RemoveMin(newtree); }

template void HuffmanTree::Path(BinTreeNode *start,Code *first,Code *last,CharNameNode *Node,int &i) //一个数组 {

if(start==NULL) return;

// if(start->GetData()!=0) //是叶结点 严重错误，可能叶结点也是0！！ if(start->GetLeft()==NULL&&start->GetRight()==NULL) {

Node[i].charname=start->GetData(); Node[i].link=NULL; if(first==NULL) return;

Node[i].link=new Code(first->code); Code *p=first->link,*q=Node[i].link; while(p!=NULL) {

q->link=new Code(p->code); q=q->link; p=p->link; }

q->link=NULL; i++; return; }

Code *temp=new Code; //进入左子树 assert(temp); if(first==NULL)

first=last=temp; else {

last->link=temp; last=last->link; }

Path(start->GetLeft(),first,last,Node,i); last->code=1;

Path(start->GetRight(),first,last,Node,i); temp=first; if(first==last) {

delete last; first=last=NULL; return; }

while(temp->link!=last) temp=temp->link;

temp->link=NULL; delete last; last=temp; }

#endif

实现二叉树的算法源程序：

//--------------------------------------------------------------------- //bintree.h

//用指针实现的二叉树

//Type 类型必须有重载<<与>>及＝运算

#ifndef BINTREE #define BINTREE

#include #include

int Max(int a,int b) {

return a>b?a:b; }

template class BinaryTree;

template class BinTreeNode {

friend class BinaryTree; public:

BinTreeNode():leftchild(NULL),rightchild(NULL){};

BinTreeNode(Type item,BinTreeNode *left = NULL,BinTreeNode *right=NULL) :data(item),leftchild(left),rightchild(right){}; Type GetData()const { return data; }

BinTreeNode *GetLeft()const { return leftchild; } BinTreeNode *GetRight()const { return rightchild; } void SetData(const Type &item){ data=item; }

void SetLeft(BinTreeNode *L){ leftchild = L; } void SetRight(BinTreeNode *R){ rightchild = R; } private:

BinTreeNode *leftchild, *rightchild; Type data; };

template class BinaryTree { public:

BinaryTree():root(NULL){};

BinaryTree(const BinaryTree &bt){ root=Copy(bt.root);} BinaryTree(const Type &temp,const BinaryTree &bt1,const BinaryTree &bt2); BinaryTree(Type value):RefValue(value),root(NULL){}; void operator =(const BinaryTree &bt); virtual ~BinaryTree(){ Destroy(root); } void Destroy(){Destroy(root);root=NULL; }

virtual int IsEmpty(){ return root==NULL?1:0; }

virtual BinTreeNode *Parent(BinTreeNode *current) {

return root==NULL||root==current? NULL : Parent(root,current); }

virtual BinTreeNode *LeftChild(BinTreeNode *current) {

return root!=NULL? current->leftchild : NULL; }

virtual BinTreeNode *RightChild(BinTreeNode *current) {

return root!=NULL? current->rightchild : NULL; }

virtual int Insert(const Type &item); virtual int Find(const Type &item)const;

BinTreeNode *GetRoot()const{ return root; }

friend int Equal(BinTreeNode *a,BinTreeNode *b);

friend int operator ==(const BinaryTree &bt1,const BinaryTree &bt2); friend istream& operator >>(istream &in, BinaryTree &Tree); friend ostream& operator <<(ostream &out,BinaryTree &Tree );

void InOrder(); //遍历 void PreOrder(); void PostOrder();

//****************************************** //一些应用 int Size(){ return Size(root);} //统计结点数

int Depth(){ return Depth(root);} //计算树的深度 int Leaves(){ return Leaves(root);} int Degrees1(){ return Degrees1(root);} int Degrees2(){ return Degrees2(root);} protected:

BinTreeNode *root; Type RefValue;

BinTreeNode *Parent(BinTreeNode *start,BinTreeNode *current); int Insert (BinTreeNode *current,const Type &item); int Find(BinTreeNode *current,const Type &item)const; BinTreeNode* Copy(BinTreeNode *originode); void Destroy(BinTreeNode *current);

//****************************************** void InOrder(BinTreeNode *current); void PreOrder(BinTreeNode *current); void PostOrder(BinTreeNode *current);

//****************************************** //一些应用 int Size(const BinTreeNode *t)const; int Depth(const BinTreeNode *t)const; int Leaves(const BinTreeNode *t)const; int Degrees1(const BinTreeNode *t)const; int Degrees2(const BinTreeNode *t)const; };

template

BinTreeNode* BinaryTree::Copy(BinTreeNode *orignode) {

if(orignode==NULL) return NULL;

BinTreeNode *temp=new BinTreeNode; temp->data=orignode->data;

temp->leftchild=Copy(orignode->leftchild); temp->rightchild=Copy(orignode->rightchild); return temp; }

template

BinaryTree::BinaryTree(const Type &temp,const BinaryTree BinaryTree &bt2) {

root=new BinTreeNode(temp,Copy(bt1.root),Copy(bt2.root)); }

template

void BinaryTree::operator =(const BinaryTree &bt1) {

Destroy();

// Destroy(root);root=NULL; //为什么要这样？？？ root=Copy(bt1.root); }

template

void BinaryTree::Destroy(BinTreeNode *current) {

if(current!=NULL) {

Destroy(current->leftchild);

&bt1,const

Destroy(current->rightchild); delete current; } }

template

BinTreeNode * BinaryTree::Parent(BinTreeNode *start,BinTreeNode *current) {

if(start==NULL) return NULL;

if(start->leftchild==current || start->rightchild==current) return start;

BinTreeNode *p=NULL;

if((p=Parent(start->leftchild, current))!=NULL) //在start的左子树中找 return p; else

return Parent(start->rightchild,current); }

template

int BinaryTree::Insert(BinTreeNode *current,const Type &item) {

if(current==NULL) return 0;

BinTreeNode *p=new BinTreeNode(item,NULL,NULL); if(current->leftchild==NULL) current->leftchild=p;

else if(current->rightchild==NULL) current->rightchild=p; else

Insert(current->leftchild,item); //这样插可是构不成树状的！估且一用吧 return 1; }

template

int BinaryTree::Insert(const Type &item) {

if(root==NULL) {

root=new BinTreeNode(item,NULL,NULL); return 1; }

return Insert(root,item); }

template

int BinaryTree::Find(BinTreeNode *current,const Type &item)const {

if(current==NULL) return 0;

if(current->data==item) return 1; int k;

if((k=Find(current->leftchild,item))!=0) return 1; else

return Find(current->rightchild,item); }

template

int BinaryTree::Find(const Type &item)const {

return Find(root,item); }

template

int Equal(BinTreeNode *a,BinTreeNode *b) {

if(a==NULL&&b==NULL) return 1;

if(a!=NULL&&b!=NULL&&a->GetData()==b->GetData()

&&Equal(a->GetLeft(),b->GetLeft())&&Equal(a->GetRight(),b->GetRight())) return 1; return 0; }

template

int operator ==(const BinaryTree &bt1,const BinaryTree &bt2) {

return Equal(bt1.root,bt2.root); }

template

istream& operator>>(istream &in,BinaryTree &Tree) {

Type item;

cout<<\"构造二叉树:\\n\";

cout<<\"输入数据(用\"<> item; while(item!=Tree.RefValue) {

Tree.Insert(item);

cout<<\"输入数据(用\"<>item; }

return in; }

template

ostream& operator<<(ostream &out,BinaryTree &Tree) {

out<<\"二叉树的前序遍历.\\n\"; Tree.PreOrder(); out<//*****************************************************************************

template

void BinaryTree ::InOrder() {

InOrder(root); }

template void BinaryTree::InOrder(BinTreeNode *current)

{

if(current!=NULL) {

InOrder(current->leftchild); cout << current->data<<' '; InOrder(current->rightchild); } }

template

void BinaryTree ::PreOrder() {

PreOrder(root); }

template

void BinaryTree::PreOrder(BinTreeNode *current) {

if(current!=NULL) {

cout<data<<' '; PreOrder(current->leftchild); PreOrder(current->rightchild); } }

template

void BinaryTree::PostOrder() {

PostOrder(root); }

template

void BinaryTree::PostOrder(BinTreeNode *current) {

if(current!=NULL) {

PostOrder(current->leftchild); PostOrder(current->rightchild); cout<data<<' '; } }

//*************************************************** //一些应用 template

int BinaryTree::Size(const BinTreeNode *t)const {

if(t==NULL) return 0; else

return 1+Size(t->leftchild)+Size(t->rightchild); }

template

int BinaryTree::Depth(const BinTreeNode *t)const {

if(t==NULL) return -1;

else

return 1+Max(Depth(t->leftchild),Depth(t->rightchild)); }

template

int BinaryTree::Leaves(const BinTreeNode *t)const {

if(t==NULL) return 0;

if(t->leftchild==NULL&&t->rightchild==NULL) //t是叶子结点 return 1;

return Leaves(t->leftchild)+Leaves(t->rightchild); }

template

int BinaryTree::Degrees1(const BinTreeNode *t)const {

if(t==NULL) return 0;

if((t->leftchild==NULL&&t->rightchild!=NULL)

||(t->leftchild!=NULL&&t->rightchild==NULL)) //t的度为1 return 1+Degrees1(t->leftchild)+Degrees1(t->rightchild); return Degrees1(t->leftchild)+Degrees1(t->rightchild); }

template

int BinaryTree::Degrees2(const BinTreeNode *t)const {

if(t==NULL) return 0;

if(t->leftchild!=NULL&&t->rightchild!=NULL) //t 的度为2

return 1+Degrees2(t->leftchild)+Degrees2(t->rightchild); return Degrees2(t->leftchild)+Degrees2(t->rightchild); }

#endif

堆程序：

//--------------------------------------------------------- //堆

#include #include #include

//Type 类型必须有key成员！及＜＜ ＞＞ ＝及拷贝构造运算！ template class MinPQ {

public:

virtual int Insert(const Type &)=0; virtual int RemoveMin(Type &)=0; };

template

class MinHeap:public MinPQ {

public:

MinHeap(int maxsize=DefaultSize);

MinHeap(Type arr[],int n);

MinHeap(const MinHeap &R); ~MinHeap(){delete []heap;}

void operator =(const MinHeap &R); int Insert(const Type &x); int RemoveMin(Type &x);

int IsEmpty() const {return currentsize==0;}

int IsFull() const {return currentsize==maxheapsize;} void MakeEmpty(){currentsize=0;} void Display();//调试时使用 private:

enum {DefaultSize=10}; Type *heap;

int currentsize; int maxheapsize;

void FilterDown(const int start,const int endofheap); //最小堆

void FilterUp(int start); //成为最小堆 };

template

MinHeap::MinHeap(int maxsize) {

maxheapsize=DefaultSizetemplate

MinHeap::MinHeap(Type arr[],int n) {

maxheapsize=DefaultSizefor(int i=0;iint currentpos=(currentsize-2)/2; while(currentpos>=0) {

FilterDown(currentpos,currentsize-1); currentpos--; } }

template

MinHeap::MinHeap(const MinHeap &R) {

heap=new Type[1]; *this=R; }

template

void MinHeap::operator =(const MinHeap &R) {

maxheapsize=R.maxheapsize;

从i到m向下进行调整成为从i到m自底向上进行调整

delete []heap;

heap=new Type[maxheapsize]; assert(heap);

currentsize=R.currentsize; for(int i=0;itemplate

void MinHeap::FilterDown(const int start,const int endofheap) {

int i=start,j=2*i+1; Type temp=heap[i]; while(j<=endofheap) {

if(jheap[j+1].key)

j++; // heap[].key 关键码 if(temp.key<=heap[j].key) break; else {

heap[i]=heap[j]; i=j; j=2*i+1; }

heap[i]=temp; } }

template

void MinHeap::FilterUp(int start) {

int j=start,i=(j-1)/2; Type temp=heap[j]; while(j>0) {

if(heap[i].keyheap[j]=heap[i]; j=i;

i=(j-1)/2; } }

heap[j]=temp; }

template

int MinHeap::Insert(const Type &x) {

if(currentsize==maxheapsize) {

cerr<<\"堆已满!\\n\"; return 0; }

heap[currentsize]=x; FilterUp(currentsize);

currentsize++; return 1; }

template

int MinHeap::RemoveMin(Type &x) {

if(!currentsize) {

cerr<<\"堆空!\\n\"; return 0; }

x=heap[0];

heap[0]=heap[currentsize-1]; currentsize--;

FilterDown(0,currentsize-1); return 1; }

template

void MinHeap::Display() {

for(int i=0;i四、 调试分析：

4.1、文件压缩测试： 测试文档test.txt

程序主界面：

进行文件压缩

压缩文件格式

为了区别我们压缩过的文件和一般文件，最好在压缩文件的头部写一些特殊的标志。另外，一般来说，压缩完一个文件后，程序要关掉，把压缩文件传给别人以后，再启动程序进行解压。这就意味着关掉程序以后，huffman树、词汇表和编码表都销毁了。因此为了能够解压缩，要把huffman树和词汇表作为额外的内容存到压缩文件里。并且要存到压缩文件的头部，否则就不知道怎么解压了。 压缩文件格式设计如下：

~~~~~~~~~~~~~~~~~~~~~~ 特殊的标志 huffman树 词汇表

压缩内容的比特数 实际的压缩文件内容 ~~~~~~~~~~~~~~~~~~~~~~

压缩文件compressTest.HFM内容：

用txt文档格式打开压缩文件，可看到文档有很多乱码，这是因为压缩文件是二进制文件，所以无法显示真实内容。

压缩文件解压：

解压压缩文件之前，先把test.txt文件删掉，因为解压压缩文件会保存为test.txt文件，删掉才能看到测试结果。

4.2、测试功能演示：

五、 结论和展望：

本次课程设计过程中，一开始对于文件压缩程序的设计无从着手，通过网上查找资料了解到文件压缩的原理和实现方法，知道可以通过Huffman编码来进行文件压缩。在设计构建Huffman树这一模块时，把它分成了三部分来设计，第一部分是构建二叉树的头文件，第二部分是建立堆得头文件，第三部分调用前两个部分的头文件，构建Huffman树。

本程序基本上可以做压缩和解压的功能，但它还存在很多的缺陷。例如：不能指定文件路径，需压缩文件和解压文件必须在程序运行目录下；压缩文件解压时不能自己为解压后文件命名，只能根据压缩文件里的信息自动生成文件名；无法同时压缩多个文件；无法根据被压缩文件的特性有针对性的进行统计，事先对多篇同类型源文件中出现的字符进行统计,创建出高度相对较“矮”的 Huffman 树，从而提高压缩效果；等等。

相对于xp系统的压缩软件还有很大的差距，由于时间有限，所以暂时只能做到这种程度。对于指定文件路径，可以通过I/O流库的文件类来设计；命名文件名可以通过添加变量来实现；压缩多个文件和事先扫描多个文件创建Huffman树，都要通过修改Huffman算法的结构来实现。

在程序的设计中，数据结构的选择是一个基本的设计考虑因素。系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示。本次课程设计中，主要用到了数据结构的线性表和二叉树，线性表用来保存Huffman编码，压缩和解压都要用到编码表。Huffman树就是文件压缩程序的最优数据结构，确定了数据结构，算法也就可以确定下来了。

六、 参考文献：

[1] 陈天华 编著.面向对向程序设计与Visual C++6.0教程.[M]北京:清华

大学出版,2006.

[2] 孙钟秀 费翔林 骆斌 编著 操作系统教程（第4版）高等教育出版社 [3]严蔚敏 吴伟民 编著 数据结构（C语言版） 清华大学出版社 [4] 《zip 的压缩原理与实现》来源