LZ77 压缩算法实验报告 一

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

LZ77压缩算法实验报告一、实验内容:使用C++编程实现LZ77压缩算法的实现。二、实验目的:用LZ77实现文件的压缩。三、实验环境:1、软件环境:VisualC++6.02、编程语言:C++四、实验原理:LZ77算法在某种意义上又可以称为“滑动窗口压缩”,这是由于该算法将一个虚拟的,可以跟随压缩进程滑动的窗口作为术语字典,要压缩的字符串如果在该窗口中出现,则输出其出现位置和长度。使用固定大小窗口进行术语匹配,而不是在所有已经编码的信息中匹配,是因为匹配算法的时间消耗往往很多,必须限制字典的大小才能保证算法的效率;随着压缩的进程滑动字典窗口,使其中总包含最近编码过的信息,是因为对大多数信息而言,要编码的字符串往往在最近的上下文中更容易找到匹配串。五、LZ77算法的基本流程:1、从当前压缩位置开始,考察未编码的数据,并试图在滑动窗口中找出最长的匹配字符串,如果找到,则进行步骤2,否则进行步骤3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移,len为可匹配的长度,c为下一个字符。然后将窗口向后滑动len+1个字符,继续步骤1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符,继续步骤1。代码如下:#includewindows.h#includestdio.h#includememory.h#includelz77.h////////////////////////////////////////////////////////////////////outfileformat://0;flag2;buffer;0;flag2;buffer;...flag1;flag2;bufferlast//flag1-2bytes,sourcebufferblocklength//ifblocksizeis65536,bezero//flag2-2bytes,compressedbufferlength//ifcannotcompress,besamewithflag1//////////////////////////////////////////////////////////////////voidmain(intargc,char*argv[]){/*if(argc!=4){puts(Usage:);printf(Compress:%scsourcefiledestfile\n,argv[0]);printf(Decompress:%sdsourcefiledestfile\n,argv[0]);return;}*/BYTEsoubuf[65536];BYTEdestbuf[65536+16];FILE*in;FILE*out;/*in=fopen(input.txt,rb);if(in==NULL){puts(Can'topensourcefile);return;}out=fopen(compress.txt,wb);if(out==NULL){puts(Can'topendestfile);fclose(in);return;}fseek(in,0,SEEK_END);longsoulen=ftell(in);fseek(in,0,SEEK_SET);CCompressLZ77cc;WORDflag1,flag2;*/inttemp;printf(compress(0)ordecompress(1)?:);scanf(%d,&temp);if(temp==0)//compress{in=fopen(input.txt,rb);if(in==NULL){puts(Can'topensourcefile);return;}out=fopen(compress.txt,wb);if(out==NULL){puts(Can'topendestfile);fclose(in);return;}fseek(in,0,SEEK_END);longsoulen=ftell(in);fseek(in,0,SEEK_SET);CCompressLZ77cc;WORDflag1,flag2;intlast=soulen,act;while(last0){act=min(65536,last);fread(soubuf,act,1,in);last-=act;if(act==65536)//out65536bytesflag1=0;else//outlastblocksflag1=act;fwrite(&flag1,sizeof(WORD),1,out);intdestlen=cc.Compress((BYTE*)soubuf,act,(BYTE*)destbuf);if(destlen==0)//can'tcompresstheblock{flag2=flag1;fwrite(&flag2,sizeof(WORD),1,out);fwrite(soubuf,act,1,out);}else{flag2=(WORD)destlen;fwrite(&flag2,sizeof(WORD),1,out);fwrite(destbuf,destlen,1,out);}}}elseif(temp==1)//decompress{in=fopen(compress.txt,rb);if(in==NULL){puts(Can'topensourcefile);return;}out=fopen(decompress.txt,wb);if(out==NULL){puts(Can'topendestfile);fclose(in);return;}fseek(in,0,SEEK_END);longsoulen=ftell(in);fseek(in,0,SEEK_SET);CCompressLZ77cc;WORDflag1,flag2;intlast=soulen,act;while(last0){fread(&flag1,sizeof(WORD),1,in);fread(&flag2,sizeof(WORD),1,in);last-=2*sizeof(WORD);if(flag1==0)act=65536;elseact=flag1;last-=flag2?(flag2):act;if(flag2==flag1){fread(soubuf,act,1,in);}else{fread(destbuf,flag2,1,in);if(!cc.Decompress((BYTE*)soubuf,act,(BYTE*)destbuf)){puts(Decompresserror);fclose(in);fclose(out);return;}}fwrite((BYTE*)soubuf,act,1,out);}}else{puts(Usage:);printf(Compress:%scsourcefiledestfile\n,argv[0]);printf(Decompress:%sdsourcefiledestfile\n,argv[0]);}fclose(in);fclose(out);}////////////////////////////////LZ77.h////////////////////////////////使用在自己的堆中分配索引节点,不滑动窗口//每次最多压缩65536字节数据//的优化版本#ifndef_WIX_LZ77_COMPRESS_HEADER_001_#define_WIX_LZ77_COMPRESS_HEADER_001_//滑动窗口的字节大小#define_MAX_WINDOW_SIZE65536classCCompress{public:CCompress(){};virtual~CCompress(){};public:virtualintCompress(BYTE*src,intsrclen,BYTE*dest)=0;virtualBOOLDecompress(BYTE*src,intsrclen,BYTE*dest)=0;protected://tools///////////////////////////////////////////////////////////CopyBitsInAByte:在一个字节范围内复制位流//参数含义同CopyBits的参数//说明://此函数由CopyBits调用,不做错误检查,即//假定要复制的位都在一个字节范围内voidCopyBitsInAByte(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits);//////////////////////////////////////////////////////////CopyBits:复制内存中的位流//memDest-目标数据区//nDestPos-目标数据区第一个字节中的起始位//memSrc-源数据区//nSrcPos-源数据区第一个字节的中起始位//nBits-要复制的位数//说明://起始位的表示约定为从字节的高位至低位(由左至右)//依次为0,,...,7//要复制的两块数据区不能有重合voidCopyBits(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits);////////////////////////////////////////////////////////////////将DWORD值从高位字节到低位字节排列voidInvertDWord(DWORD*pDW);///////////////////////////////////////////////////////////////设置byte的第iBit位为aBit//iBit顺序为高位起从记数(左起)voidSetBit(BYTE*byte,intiBit,BYTEaBit);//////////////////////////////////////////////////////////////得到字节byte第pos位的值//pos顺序为高位起从记数(左起)BYTEGetBit(BYTEbyte,intpos);//////////////////////////////////////////////////////////////将位指针*piByte(字节偏移),*piBit(字节内位偏移)后移num位voidMovePos(int*piByte,int*piBit,intnum);///////////////////////////////////////////////////////////取log2(n)的upper_boundintUpperLog2(intn);///////////////////////////////////////////////////////////取log2(n)的lower_boundintLowerLog2(intn);};classCCompressLZ77:publicCCompress{public:CCompressLZ77();virtual~CCompressLZ77();public:///////////////////////////////////////////////压缩一段字节流//src-源数据区//srclen-源数据区字节长度,srclen=65536//dest-压缩数据区,调用前分配srclen字节内存//返回值0压缩数据长度//返回值=0数据无法压缩//返回值0压缩中异常错误intCompress(BYTE*src,intsrclen,BYTE*dest);///////////////////////////

1 / 20
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功