文件压缩程序设计报告

课程设计报告课程名称：操作系统实验题目：文件压缩程序院系：计算机科学与工程学院班级：姓名：学号：二○一一年七月一日一、需求分析：有两种形式的重复存在于计算机数据中，文件压缩程序就是对这两种重复进行了压缩。一种是短语形式的重复，即三个字节以上的重复，对于这种重复，压缩程序用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩。第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。给256种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越大。编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。本程序设计只做了编码式压缩，采用Huffman编码进行压缩和解压缩。Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。根据ascii码文件中各ascii字符出现的频率情况创建Huffman树，再将各字符对应的哈夫曼编码写入文件中。同时，亦可根据对应的哈夫曼树，将哈夫曼编码文件解压成字符文件.二、概要设计：主程序流程图：压缩过程的实现:压缩过程的流程是清晰而简单的:1.创建Huffman树2.打开需压缩文件3.将需压缩文件中的每个ascii码对应的huffman编码按bit单位输出生成压缩文件压缩结束。主函数统计字符，得出统计出的字符的权值n编码解码退出根据权值进行建立Huffman树输出Huffman树输出编码压缩编码生成压缩文件解压生成新的文本文档扫描压缩文件，载入字符信息根据权值进行建立Huffman树输出Huffman树测试输入测试字符串统计字符信息，建立Huffman曼树根据Huffman树，求得对应字符的Huffman编码输入Huffman编码，求得解码其中，步骤1和步骤3是压缩过程的关键。步骤1:这里所要做工作是得到Huffman数中各叶子结点字符出现的频率并进行创建.统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实时”的生成各字符的出现频率;或者是创建前即做好统计.这里采用的是前一种方法。步骤3:将需压缩文件中的每个ascii码对应的huffman编码按bit单位输出.这是本压缩程序中最关键的部分:这里涉及“转换”和“输出”两个关键步骤：“转换”部分大可不必去通过遍历Huffman树来找到每个字符对应的哈夫曼编码，可以将每个Huffman码值及其对应的ascii码存放于如下所示的结构体中：解压缩过程的实现:如果说,压缩的过程可以通过查找codeList来加速实现的话，而解压缩则必须通过查找huffman树才能加以实现.查找的过程是简单的，可以根据huffman树的性质来做，当haffCode的当前bit位为0时，则向左枝展开搜索;当前bit位为1时，则向右枝展开搜索，当遇到叶子结点时，则输出haffCode对应的asciiCode。三、详细设计：核心算法源程序：Huffman树建立源程序：//-------------------------------------------------------------//huffmantree.h//霍夫曼树#ifndefHUFFMANTREE#defineHUFFMANTREE#defineDefaultsize300#includeiostream.h#includebintree.h#includeheap.hclassCode{public:intcode;Code*link;Code(intc=0,Code*l=NULL):code(c),link(l){};};classCharNameNode{public:unsignedcharcharname;//要这样才行Code*link;CharNameNode(unsignedcharc=0,Code*l=NULL):charname(c),link(l){};};templateclassTypeclassHuffmanTree:publicBinaryTreeType{public:intkey;HuffmanTree(){};HuffmanTree(HuffmanTreeType&ht1,HuffmanTreeType&ht2){Typetemp=0;//可能有变key=ht1.key+ht2.key;root=newBinTreeNodeType(0,Copy(ht1.root),Copy(ht2.root));}voidBuild(int*fr,Type*value,intn,HuffmanTreeType&newtree);voidPath(BinTreeNodeType*start,Code*first,Code*last,CharNameNode*Node,int&i);//一个数组};templateclassTypevoidHuffmanTreeType::Build(int*fr,Type*value,intn,HuffmanTreeType&newtree){//fr为value(值)对应的权inti;HuffmanTreeTypefirst,second;HuffmanTreeTypeNode[Defaultsize];MinHeapHuffmanTreeTypehp;assert(n=0&&n=Defaultsize);for(i=0;in;i++){Node[i].root=newBinTreeNodeType(value[i],NULL,NULL);Node[i].key=fr[i];}hp=MinHeapHuffmanTreeType(Node,n);for(i=0;in-1;i++){hp.RemoveMin(first);hp.RemoveMin(second);HuffmanTreeType*temp=newHuffmanTreeType(first,second);hp.Insert(*temp);}hp.RemoveMin(newtree);}templateclassTypevoidHuffmanTreeType::Path(BinTreeNodeType*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=newCode(first-code);Code*p=first-link,*q=Node[i].link;while(p!=NULL){q-link=newCode(p-code);q=q-link;p=p-link;}q-link=NULL;i++;return;}Code*temp=newCode;//进入左子树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){deletelast;first=last=NULL;return;}while(temp-link!=last)temp=temp-link;temp-link=NULL;deletelast;last=temp;}#endif实现二叉树的算法源程序：//---------------------------------------------------------------------//bintree.h//用指针实现的二叉树//Type类型必须有重载与及＝运算#ifndefBINTREE#defineBINTREE#includeassert.h#includeiostream.hintMax(inta,intb){returnab?a:b;}templateclassTypeclassBinaryTree;templateclassTypeclassBinTreeNode{friendclassBinaryTreeType;public:BinTreeNode():leftchild(NULL),rightchild(NULL){};BinTreeNode(Typeitem,BinTreeNodeType*left=NULL,BinTreeNodeType*right=NULL):data(item),leftchild(left),rightchild(right){};TypeGetData()const{returndata;}BinTreeNodeType*GetLeft()const{returnleftchild;}BinTreeNodeType*GetRight()const{returnrightchild;}voidSetData(constType&item){data=item;}voidSetLeft(BinTreeNodeType*L){leftchild=L;}voidSetRight(BinTreeNodeType*R){rightchild=R;}private:BinTreeNodeType*leftchild,*rightchild;Typedata;};templateclassTypeclassBinaryTree{public:BinaryTree():root(NULL){};BinaryTree(constBinaryTreeType&bt){root=Copy(bt.root);}BinaryTree(constType&temp,constBinaryTreeType&bt1,constBinaryTreeType&bt2);BinaryTree(Typevalue):RefValue(value),root(NULL){};voidoperator=(constBinaryTreeType&bt);virtual~BinaryTree(){Destroy(root);}voidDestroy(){Destroy(root);root=NULL;}virtualintIsEmpty(){returnroot==NULL?1:0;}virtualBinTreeNodeType*Parent(BinTreeNodeType*current){returnroot==NULL||root==current?NULL:Parent(root,current);}virtualBinTreeNodeType*