LZ77 壓縮算法實(shí)驗(yàn)報(bào)告 一

LZ77壓縮算法實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)內(nèi)容：使用C++編程實(shí)現(xiàn)LZ77壓縮算法的實(shí)現(xiàn)。二、實(shí)驗(yàn)?zāi)康模河肔Z77實(shí)現(xiàn)文件的壓縮。三、實(shí)驗(yàn)環(huán)境：1、軟件環(huán)境：VisualC++6.02、編程語言：C++四、實(shí)驗(yàn)原理：LZ77算法在某種意義上又可以稱為“滑動(dòng)窗口壓縮”，這是由于該算法將一個(gè)虛擬的，可以跟隨壓縮進(jìn)程滑動(dòng)的窗口作為術(shù)語字典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長度。使用固定大小窗口進(jìn)行術(shù)語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因?yàn)槠ヅ渌惴ǖ臅r(shí)間消耗往往很多，必須限制字典的大小才能保證算法的效率；隨著壓縮的進(jìn)程滑動(dòng)字典窗口，使其中總包含最近編碼過的信息，是因?yàn)閷?duì)大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。五、LZ77算法的基本流程：1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動(dòng)窗口中找出最長的匹配字符串，如果找到，則進(jìn)行步驟2，否則進(jìn)行步驟3。2、輸出三元符號(hào)組（off,len,c。其中off為窗口中匹配字符串相對(duì)窗口邊界的偏移，len為可匹配的長度，c為下一個(gè)字符。然后將窗口向后滑動(dòng)len+1個(gè)字符，繼續(xù)步驟1。3、輸出三元符號(hào)組（0,0,c。其中c為下一個(gè)字符。然后將窗口向后滑動(dòng)len+1個(gè)字符，繼續(xù)步驟1。代碼如下：#include<windows.h>#include<stdio.h>#include<memory.h>#include"lz77.h"http:////////////////////////////////////////////////////////////////////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////////////////////////////////使用在自己的堆中分配索引節(jié)點(diǎn)，不滑動(dòng)窗口//每次最多壓縮65536字節(jié)數(shù)據(jù)//的優(yōu)化版本#ifndef_WIX_LZ77_COMPRESS_HEADER_001_#define_WIX_LZ77_COMPRESS_HEADER_001_//滑動(dòng)窗口的字節(jié)大小#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:在一個(gè)字節(jié)范圍內(nèi)復(fù)制位流//參數(shù)含義同CopyBits的參數(shù)//說明：//此函數(shù)由CopyBits調(diào)用，不做錯(cuò)誤檢查，即//假定要復(fù)制的位都在一個(gè)字節(jié)范圍內(nèi)voidCopyBitsInAByte(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits);//////////////////////////////////////////////////////////CopyBits:復(fù)制內(nèi)存中的位流//memDest-目標(biāo)數(shù)據(jù)區(qū)//nDestPos-目標(biāo)數(shù)據(jù)區(qū)第一個(gè)字節(jié)中的起始位//memSrc-源數(shù)據(jù)區(qū)//nSrcPos-源數(shù)據(jù)區(qū)第一個(gè)字節(jié)的中起始位//nBits-要復(fù)制的位數(shù)//說明：//起始位的表示約定為從字節(jié)的高位至低位(由左至右)//依次為0，，...,7//要復(fù)制的兩塊數(shù)據(jù)區(qū)不能有重合voidCopyBits(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits);////////////////////////////////////////////////////////////////將DWORD值從高位字節(jié)到低位字節(jié)排列voidInvertDWord(DWORD*pDW);///////////////////////////////////////////////////////////////設(shè)置byte的第iBit位為aBit//iBit順序?yàn)楦呶黄饛挠洈?shù)(左起)voidSetBit(BYTE*byte,intiBit,BYTEaBit);//////////////////////////////////////////////////////////////得到字節(jié)byte第pos位的值//pos順序?yàn)楦呶黄饛挠洈?shù)(左起)BYTEGetBit(BYTEbyte,intpos);//////////////////////////////////////////////////////////////將位指針*piByte(字節(jié)偏移)，*piBit(字節(jié)內(nèi)位偏移)后移num位voidMovePos(int*piByte,int*piBit,intnum);///////////////////////////////////////////////////////////取log2(n)的upper_boundintUpperLog2(intn);///////////////////////////////////////////////////////////取log2(n)的lower_boundintLowerLog2(intn););classCCompressLZ77:publicCCompress{public:CCompressLZ77();virtual~CCompressLZ77();public:///////////////////////////////////////////////壓縮一段字節(jié)流//src-源數(shù)據(jù)區(qū)//srclen-源數(shù)據(jù)區(qū)字節(jié)長度，srclen<=65536//dest-壓縮數(shù)據(jù)區(qū)，調(diào)用前分配srclen字節(jié)內(nèi)存//返回值〉0壓縮數(shù)據(jù)長度//返回值=0數(shù)據(jù)無法壓縮//返回值<0壓縮中異常錯(cuò)誤intCompress(BYTE*src,intsrclen,BYTE*dest);///////////////////////////////////////////////解壓縮一段字節(jié)流//src-接收原始數(shù)據(jù)的內(nèi)存區(qū)，srclen<=65536//srclen-源數(shù)據(jù)區(qū)字節(jié)長度//dest-壓縮數(shù)據(jù)區(qū)//返回值-成功與否BOOLDecompress(BYTE*src,intsrclen,BYTE*dest);protected:BYTE*pWnd;//窗口大小最大為64k，并且不做滑動(dòng)//每次最多只壓縮64k數(shù)據(jù)，這樣可以方便從文件中間開始解壓//當(dāng)前窗口的長度intnWndSize;//對(duì)滑動(dòng)窗口中每一個(gè)字節(jié)串排序//排序是為了進(jìn)行快速術(shù)語匹配//排序的方法是用一個(gè)k大小的指針數(shù)組//數(shù)組下標(biāo)依次對(duì)應(yīng)每一個(gè)字節(jié)串：(0000)(0001)...(0100)(0101)...//每一個(gè)指針指向一個(gè)鏈表，鏈表中的節(jié)點(diǎn)為該字節(jié)串的每一個(gè)出現(xiàn)位置structSTIDXNODE{WORDoff;//在src中的偏移WORDoff2;//用于對(duì)應(yīng)的字節(jié)串為重復(fù)字節(jié)的節(jié)點(diǎn)//指從off至到off2都對(duì)應(yīng)了該字節(jié)串WORDnext;//在SortHeap中的指針);WORDSortTable[65536];//256*256指向SortHeap中下標(biāo)的指針//因?yàn)榇翱诓换瑒?dòng)，沒有刪除節(jié)點(diǎn)的操作，所以//節(jié)點(diǎn)可以在SortHeap中連續(xù)分配structSTIDXNODE*SortHeap;intHeapPos;//當(dāng)前分配位置//當(dāng)前輸出位置(字節(jié)偏移及位偏移)intCurByte,CurBit;protected://////////////////////////////////////////輸出壓縮碼//code-要輸出的數(shù)//bits-要輸出的位數(shù)(對(duì)isGamma=TRUE時(shí)無效)//isGamma-是否輸出為y編碼void_OutCode(BYTE*dest,DWORDcode,intbits,BOOLisGamma);/////////////////////////////////////////////////////////////在滑動(dòng)窗口中查找術(shù)語//nSeekStart-從何處開始匹配//offset,len-用于接收結(jié)果，表示在滑動(dòng)窗口內(nèi)的偏移和長度//返回值-是否查到長度為或以上的匹配字節(jié)串BOOL_SeekPhase(BYTE*src,intsrclen,intnSeekStart,int*offset,int*len);/////////////////////////////////////////////////////////////得到已經(jīng)匹配了個(gè)字節(jié)的窗口位置offset//共能匹配多少個(gè)字節(jié)inlineint_GetSameLen(BYTE*src,intsrclen,intnSeekStart,intoffset);////////////////////////////////////////////將窗口向右滑動(dòng)n個(gè)字節(jié)inlinevoid_ScrollWindow(intn);//向索引中添加一個(gè)字節(jié)串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"http:///////////////////////////////////////////////////////////取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(字節(jié)偏移)，*piBit(字節(jié)內(nèi)位偏移)后移num位voidCCompress::MovePos(int*piByte,int*piBit,intnum){num+=(*piBit);(*piByte)+=num/8;(*piBit)=num%8;}//MovePos//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////得到字節(jié)byte第pos位的值//pos順序?yàn)楦呶黄饛挠洈?shù)(左起)BYTECCompress::GetBit(BYTEbyte,intpos){intj=1;j<<=7-pos;if(byte&j)return1;elsereturn0;}//GetBit////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////設(shè)置byte的第iBit位為aBit//iBit順序?yàn)楦呶黄饛挠洈?shù)(左起)voidCCompress::SetBit(BYTE*byte,intiBit,BYTEaBit){if(aBit)(*byte)|=(1<<(7-iBit));else(*byte)&=~(1<<(7-iBit));}//SetBit//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////將DWORD值從高位字節(jié)到低位字節(jié)排列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:復(fù)制內(nèi)存中的位流//memDest-目標(biāo)數(shù)據(jù)區(qū)//nDestPos-目標(biāo)數(shù)據(jù)區(qū)第一個(gè)字節(jié)中的起始位//memSrc-源數(shù)據(jù)區(qū)//nSrcPos-源數(shù)據(jù)區(qū)第一個(gè)字節(jié)的中起始位//nBits-要復(fù)制的位數(shù)//說明：//起始位的表示約定為從字節(jié)的高位至低位(由左至右)//依次為0，，...,7//要復(fù)制的兩塊數(shù)據(jù)區(qū)不能有重合voidCCompress::CopyBits(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits){intiByteDest=0,iBitDest;intiByteSrc=0,iBitSrc=nSrcPos;intnBitsToFill,nBitsCanFill;while(nBits>0){//計(jì)算要在目標(biāo)區(qū)當(dāng)前字節(jié)填充的位數(shù)nBitsToFill=min(nBits,iByteDest?8:8-nDestPos);//目標(biāo)區(qū)當(dāng)前字節(jié)要填充的起始位iBitDest=iByteDest?0:nDestPos;//計(jì)算可以一次從源數(shù)據(jù)區(qū)中復(fù)制的位數(shù)nBitsCanFill=min(nBitsToFill,8-iBitSrc);//字節(jié)內(nèi)復(fù)制CopyBitsInAByte(memDest+舊yteDest,iBitDest,memSrc+iByteSrc,iBitSrc,nBitsCanFill);//如果還沒有復(fù)制完nBitsToFill個(gè)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;//已經(jīng)填充了nBitsToFill位iByteDest++;}}//CopyBits////////////////////////////////////////////////////////////////////////////////////////////////////////////////////CopyBitsInAByte:在一個(gè)字節(jié)范圍內(nèi)復(fù)制位流//參數(shù)含義同CopyBits的參數(shù)//說明：//此函數(shù)由CopyBits調(diào)用，不做錯(cuò)誤檢查，即//假定要復(fù)制的位都在一個(gè)字節(jié)范圍內(nèi)voidCCompress::CopyBitsInAByte(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits)BYTEb1,b2;bl=*memSrc;bl<<=nSrcPos;bl>>=8-nBits;//將不用復(fù)制的位清bl<<=8-nBits-nDestPos;//將源和目的字節(jié)對(duì)齊*memDest|=bl;//復(fù)制值為的位b2=0xff;b2<<=8-nDestPos;//將不用復(fù)制的位置bl|=b2;b2=0xff;b2>>=nDestPos+nBits;bl|=b2;*memDest&=bl;//復(fù)制值為的位}//CopyBitsInAByte///////////////////////////////////////////////////////////CCompressLZ77::CCompressLZ77(){SortHeap=newstructSTIDXNODE[_MAX_WINDOW_SIZE];}CCompressLZ77::~CCompressLZ77(){delete[]SortHeap;}//初始化索引表，釋放上次壓縮用的空間voidCCompressLZ77::_InitSortTable(){memset(SortTable,0,sizeof(WORD)*65536);nWndSize=0;HeapPos=l;}//向索引中添加一個(gè)字節(jié)串voidCCompressLZ77::_InsertIndexItem(intoff){WORDq;BYTEchl,ch2;chl=pWnd[off];ch2=pWnd[off+1];if(chl!=ch2){//新建節(jié)點(diǎn)q=HeapPos;HeapPos++;SortHeap[q].off=off;SortHeap[q].next=SortTable[ch1*256+ch2];SortTable[ch1*256+ch2]=q;}else{//對(duì)重復(fù)字節(jié)串//因?yàn)闆]有虛擬偏移也沒有刪除操作，只要比較第一個(gè)節(jié)點(diǎn)//是否和off相連接即可q=SortTable[ch1*256+ch2];if(q!=0&&off==SortHeap[q].off2+1){//節(jié)點(diǎn)合并SortHeap[q].off2=off;}else{//新建節(jié)點(diǎn)q=HeapPos;HeapPos++;SortHeap[q].off=off;SortHeap[q].off2=off;SortHeap[q].next=SortTable[ch1*256+ch2];SortTable[ch1*256+ch2]=q;}}}////////////////////////////////////////////將窗口向右滑動(dòng)n個(gè)字節(jié)voidCCompressLZ77::_ScrollWindow(intn){for(inti=0;i<n;i++){nWndSize++;if(nWndSize>1)_InsertIndexItem(nWndSize-2);}}/////////////////////////////////////////////////////////////得到已經(jīng)匹配了個(gè)字節(jié)的窗口位置offset//共能匹配多少個(gè)字節(jié)intCCompressLZ77::_GetSameLen(BYTE*src,intsrclen,intnSeekStart,intoffset){inti=2;//已經(jīng)匹配了個(gè)字節(jié)intmaxsame=min(srclen-nSeekStart,nWndSize-offset);while(i<maxsame&&src[nSeekStart+i]==pWnd[offset+i])i++；_ASSERT(nSeekStart+i<=srclen&&offset+i<=nWndSize);returni;}/////////////////////////////////////////////////////////////在滑動(dòng)窗口中查找術(shù)語//nSeekStart-從何處開始匹配//offset,len-用于接收結(jié)果，表示在滑動(dòng)窗口內(nèi)的偏移和長度//返回值-是否查到長度為或以上的匹配字節(jié)串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-要輸出的數(shù)//bits-要輸出的位數(shù)(對(duì)isGamma=TRUE時(shí)無效)//isGamma-是否輸出為y編碼voidCCompressLZ77::_OutCode(BYTE*dest,DWORDcode,intbits,BOOLisGamma){if(isGamma){BYTE*pb;DWORDout;//計(jì)算輸出位數(shù)intGammaCode=(int)code-1;intq=LowerLog2(GammaCode);if(q>0){out=0xffff;pb=(BYTE*)&out;//輸出q個(gè)CopyBits(dest+CurByte,CurBit,pb,0,q);MovePos(&CurByte,&CurBit,q);}//輸出一個(gè)out=0;pb=(BYTE*)&out;CopyBits(dest+CurByte,CurBit,pb+3,7,1);MovePos(&CurByte,&CurBit,1);if(q>0){//輸出余數(shù)，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);}}///////////////////////////////////////////////壓縮一段字節(jié)流//src-源數(shù)據(jù)區(qū)//srclen-源數(shù)據(jù)區(qū)字節(jié)長度//dest-壓縮數(shù)據(jù)區(qū)，調(diào)用前分配srclen+5字節(jié)內(nèi)存//返回值〉0壓縮數(shù)據(jù)長度//返回值=0數(shù)據(jù)無法壓縮//返回值<0壓縮中異常錯(cuò)誤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)){//輸出匹配術(shù)語flag(lbit)+len(y編碼)+offset(最大bit)_OutCode(dest,1,1,FALSE);_OutCode(dest,l