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。代码如下：#include<windows.h>#include<stdio.h>#include<memory.h>#include"lz77.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;WORDflagl,flag2;*/inttemp;printf("compress(0)ordecompress(l)?:");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(last>0){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(last>0){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);///////////////////////////////////////////////解压缩一段字节流//src-接收原始数据的内存区，srclen<=65536//srclen-源数据区字节长度//dest-压缩数据区//返回值-成功与否BOOLDecompress(BYTE*src,intsrclen,BYTE*dest);protected:BYTE*pWnd;//窗口大小最大为64k，并且不做滑动//每次最多只压缩64k数据，这样可以方便从文件中间开始解压//当前窗口的长度intnWndSize;//对滑动窗口中每一个字节串排序//排序是为了进行快速术语匹配//排序的方法是用一个k大小的指针数组//数组下标依次对应每一个字节串：(0000)(0001)...(0100)(0101)...//每一个指针指向一个链表，链表中的节点为该字节串的每一个出现位置structSTIDXNODE{WORDoff;//在src中的偏移WORDoff2;//用于对应的字节串为重复字节的节点//指从off至到off2都对应了该字节串WORDnext;//在SortHeap中的指针);WORDSortTable[65536];//256*256指向SortHeap中下标的指针//因为窗口不滑动，没有删除节点的操作，所以//节点可以在SortHeap中连续分配structSTIDXNODE*SortHeap;intHeapPos;//当前分配位置//当前输出位置(字节偏移及位偏移)intCurByte,CurBit;protected://////////////////////////////////////////输出压缩码//code-要输出的数//bits-要输出的位数(对isGamma=TRUE时无效)//isGamma-是否输出为y编码void_OutCode(BYTE*dest,DWORDcode,intbits,BOOLisGamma);/////////////////////////////////////////////////////////////在滑动窗口中查找术语//nSeekStart-从何处开始匹配//offset,len-用于接收结果，表示在滑动窗口内的偏移和长度//返回值-是否查到长度为或以上的匹配字节串BOOL_SeekPhase(BYTE*src,intsrclen,intnSeekStart,int*offset,int*len);/////////////////////////////////////////////////////////////得到已经匹配了个字节的窗口位置offset//共能匹配多少个字节inlineint_GetSameLen(BYTE*src,intsrclen,intnSeekStart,intoffset);////////////////////////////////////////////将窗口向右滑动n个字节inlinevoid_ScrollWindow(intn);//向索引中添加一个字节串inlinevoid_InsertIndexItem(intoff);//初始化索引表，释放上次压缩用的空间void_InitSortTable(););#endif//_WIX_LZW_COMPRESS_HEADER_001_////////////////////////////////LZ77.CPP//////////////////////////////#include<windows.h>#include<stdio.h>#include<memory.h>#include<crtdbg.h>#include"lz77.h"///////////////////////////////////////////////////////////取log2(n)的upper_boundintCCompress::UpperLog2(intn){inti=0;if(n>0){intm=1;while(1){if(m>=n)returni;m<<=1;i++;}}elsereturn-1;}//UpperLog2////////////////////////////////////////////////////////////////////////////////////////////////////////////////////取log2(n)的lower_boundintCCompress::LowerLog2(intn){inti=0;if(n>0){intm=1;while(1)if(m==n)returni;if(m>n)returni-1;m<<=1;i++；}}elsereturn-1;}//LowerLog2///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////将位指针*piByte(字节偏移)，*piBit(字节内位偏移)后移num位voidCCompress::MovePos(int*piByte,int*piBit,intnum){num+=(*piBit);(*piByte)+=num/8;(*piBit)=num%8;}//MovePos//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////得到字节byte第pos位的值//pos顺序为高位起从记数(左起)BYTECCompress::GetBit(BYTEbyte,intpos){intj=1;j<<=7-pos;if(byte&j)return1;elsereturn0;}//GetBit////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////设置byte的第iBit位为aBit//iBit顺序为高位起从记数(左起)voidCCompress::SetBit(BYTE*byte,intiBit,BYTEaBit){if(aBit)(*byte)|=(1<<(7-iBit));else(*byte)&=~(1<<(7-iBit));}//SetBit//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////将DWORD值从高位字节到低位字节排列voidCCompress::InvertDWord(DWORD*pDW){unionUDWORD{DWORDdw;BYTEb[4];);UDWORD*pUDW=(UDWORD*)pDW;BYTEb;b=pUDW->b[0];pUDW->b[0]=pUDW->b[3];pUDW->b[3]=b;b=pUDW->b[1];pUDW->b[1]=pUDW->b[2];pUDW->b[2]=b;}//InvertDWord////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////CopyBits:复制内存中的位流//memDest-目标数据区//nDestPos-目标数据区第一个字节中的起始位//memSrc-源数据区//nSrcPos-源数据区第一个字节的中起始位//nBits-要复制的位数//说明：//起始位的表示约定为从字节的高位至低位(由左至右)//依次为0，，...,7//要复制的两块数据区不能有重合voidCCompress::CopyBits(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits){intiByteDest=0,iBitDest;intiByteSrc=0,iBitSrc=nSrcPos;intnBitsToFill,nBitsCanFill;while(nBits>0){//计算要在目标区当前字节填充的位数nBitsToFill=min(nBits,iByteDest?8:8-nDestPos);//目标区当前字节要填充的起始位iBitDest=iByteDest?0:nDestPos;//计算可以一次从源数据区中复制的位数nBitsCanFill=min(nBitsToFill,8-iBitSrc);//字节内复制CopyBitsInAByte(memDest+旧yteDest,iBitDest,memSrc+iByteSrc,iBitSrc,nBitsCanFill);//如果还没有复制完nBitsToFill个if(nBitsToFill>nBitsCanFill){iByteSrc++;iBitSrc=0;iBitDest+=nBitsCanFill;CopyBitsInAByte(memDest+iByteDest,iBitDest,memSrc+iByteSrc,iBitSrc,nBitsToFill-nBitsCanFill);iBitSrc+=nBitsToFill-nBitsCanFill;}else{iBitSrc+=nBitsCanFill;if(iBitSrc>=8){iByteSrc++;iBitSrc=0;}}nBits-=nBitsToFill;//已经填充了nBitsToFill位iByteDest++;}}//CopyBits////////////////////////////////////////////////////////////////////////////////////////////////////////////////////CopyBitsInAByte:在一个字节范围内复制位流//参数含义同CopyBits的参数//说明：//此函数由CopyBits调用，不做错误检查，即//假定要复制的位都在一个字节范围内voidCCompress::CopyBitsInAByte(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits)BYTEb1,b2;bl=*memSrc;bl<<=nSrcPos;bl>>=8-nBits;//将不用复制的位清bl<<=8-nBits-nDestPos;//将源和目的字节对齐*memDest|=bl;//复制值为的位b2=0xff;b2<<=8-nDestPos;//将不用复制的位置bl|=b2;b2=0xff;b2>>=nDestPos+nBits;bl|=b2;*memDest&=bl;//复制值为的位}//CopyBitsInAByte///////////////////////////////////////////////////////////CCompressLZ77::CCompressLZ77(){SortHeap=newstructSTIDXNODE[_MAX_WINDOW_SIZE];}CCompressLZ77::~CCompressLZ77(){delete[]SortHeap;}//初始化索引表，释放上次压缩用的空间voidCCompressLZ77::_InitSortTable(){memset(SortTable,0,sizeof(WORD)*65536);nWndSize=0;HeapPos=l;}//向索引中添加一个字节串voidCCompressLZ77::_InsertIndexItem(intoff){WORDq;BYTEchl,ch2;chl=pWnd[off];ch2=pWnd[off+1];if(chl!=ch2){//新建节点q=HeapPos;HeapPos++;SortHeap[q].off=off;SortHeap[q].next=SortTable[ch1*256+ch2];SortTable[ch1*256+ch2]=q;}else{//对重复字节串//因为没有虚拟偏移也没有删除操作，只要比较第一个节点//是否和off相连接即可q=SortTable[ch1*256+ch2];if(q!=0&&off==SortHeap[q].off2+1){//节点合并SortHeap[q].off2=off;}else{//新建节点q=HeapPos;HeapPos++;SortHeap[q].off=off;SortHeap[q].off2=off;SortHeap[q].next=SortTable[ch1*256+ch2];SortTable[ch1*256+ch2]=q;}}}////////////////////////////////////////////将窗口向右滑动n个字节voidCCompressLZ77::_ScrollWindow(intn){for(inti=0;i<n;i++){nWndSize++;if(nWndSize>1)_InsertIndexItem(nWndSize-2);}}/////////////////////////////////////////////////////////////得到已经匹配了个字节的窗口位置offset//共能匹配多少个字节intCCompressLZ77::_GetSameLen(BYTE*src,intsrclen,intnSeekStart,intoffset){inti=2;//已经匹配了个字节intmaxsame=min(srclen-nSeekStart,nWndSize-offset);while(i<maxsame&&src[nSeekStart+i]==pWnd[offset+i])i++；_ASSERT(nSeekStart+i<=srclen&&offset+i<=nWndSize);returni;}/////////////////////////////////////////////////////////////在滑动窗口中查找术语//nSeekStart-从何处开始匹配//offset,len-用于接收结果，表示在滑动窗口内的偏移和长度//返回值-是否查到长度为或以上的匹配字节串BOOLCCompressLZ77::_SeekPhase(BYTE*src,intsrclen,intnSeekStart,int*offset,int*len){intj,m,n;if(nSeekStart<srclen-1){BYTEch1,ch2;ch1=src[nSeekStart];ch2=src[nSeekStart+1];WORDp;p=SortTable[ch1*256+ch2];if(p!=0){m=2;n=SortHeap[p].off;while(p!=0){j=_GetSameLen(src,srclen,nSeekStart,SortHeap[p].off);if(j>m){m=j;n=SortHeap[p].off;}p=SortHeap[p].next;}(*offset)=n;(*len)=m;returnTRUE;}returnFALSE;}//////////////////////////////////////////输出压缩码//code-要输出的数//bits-要输出的位数(对isGamma=TRUE时无效)//isGamma-是否输出为y编码voidCCompressLZ77::_OutCode(BYTE*dest,DWORDcode,intbits,BOOLisGamma){if(isGamma){BYTE*pb;DWORDout;//计算输出位数intGammaCode=(int)code-1;intq=LowerLog2(GammaCode);if(q>0){out=0xffff;pb=(BYTE*)&out;//输出q个CopyBits(dest+CurByte,CurBit,pb,0,q);MovePos(&CurByte,&CurBit,q);}//输出一个out=0;pb=(BYTE*)&out;CopyBits(dest+CurByte,CurBit,pb+3,7,1);MovePos(&CurByte,&CurBit,1);if(q>0){//输出余数，q位intsh=1;sh<<=q;out=GammaCode-sh;pb=(BYTE*)&out;InvertDWord(&out);CopyBits(dest+CurByte,CurBit,pb+(32-q)/8,(32-q)%8,q)；MovePos(&CurByte,&CurBit,q);}}else{DWORDdw=(DWORD)code;BYTE*pb=(BYTE*)&dw;InvertDWord(&dw);CopyBits(dest+CurByte,CurBit,pb+(32-bits)/8,(32-bits)%8,bits);MovePos(&CurByte,&CurBit,bits);}}///////////////////////////////////////////////压缩一段字节流//src-源数据区//srclen-源数据区字节长度//dest-压缩数据区，调用前分配srclen+5字节内存//返回值〉0压缩数据长度//返回值=0数据无法压缩//返回值<0压缩中异常错误intCCompressLZ77::Compress(BYTE*src,intsrclen,BYTE*dest){inti;CurByte=0;CurBit=0;intoff,len;if(srclen>65536)return-1;pWnd=src;_InitSortTable();for(i=0;i<srclen;i++){if(CurByte>=srclen)return0;if(_SeekPhase(src,srclen,i,&off,&len)){//输出匹配术语flag(lbit)+len(y编码)+offset(最大bit)_OutCode(dest,1,1,FALSE);_OutCode(dest,l