LZ77压缩算法实验报告一、实验内容使用C++编程实现LZ77压缩算法的实现。
二、实验目的用LZ77实现文件的压缩。
三、实验环境1、软件环境：Visual C++ 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。
六、源程序/*********************************************************************** Project description:* Lz77 compression/decompression algorithm.**********************************************************************/#include <windows.h>#include <conio.h>#include <stdio.h>#include <assert.h>#define OFFSET_CODING_LENGTH (10)#define MAX_WND_SIZE 1024//#define MAX_WND_SIZE (1<<OFFSET_CODING_LENGTH)#define OFFSET_MASK_CODE (MAX_WND_SIZE-1)const ULONG m=3;UCHAR __buffer1__[0x200000];UCHAR __buffer2__[0x200000];////////////////////////////////////////////////////////////////////////////////voidWrite1ToBitStream(PUCHAR pBuffer,ULONG ulBitOffset){ULONG ulByteBoundary;ULONG ulOffsetInByte;ulByteBoundary = ulBitOffset>>3 ;ulOffsetInByte = ulBitOffset&7;*(pBuffer+ulByteBoundary) |= (1<<ulOffsetInByte);}voidWrite0ToBitStream(PUCHAR pBuffer,ULONG ulBitOffset){ULONG ulByteBoundary;ULONG ulOffsetInByte;ulByteBoundary = ulBitOffset>>3 ;ulOffsetInByte = ulBitOffset&7;*(pBuffer+ulByteBoundary) &= (~(1<<ulOffsetInByte));}ULONGReadBitFromBitStream(PUCHAR pBuffer,ULONG ulBitOffset){ULONG ulByteBoundary;ULONG ulOffsetInByte;ulByteBoundary = ulBitOffset>>3 ;ulOffsetInByte = ulBitOffset&7;return ((*(PULONG)(pBuffer+ulByteBoundary))>>ulOffsetInByte)&1 ; }ULONG WINAPIWriteGolombCode(ULONG x,PUCHAR pBuffer,ULONG ulBitOffset){ULONG q, r;int i;q = (x-1)>>m;r = x-(q<<m)-1;for(i=0; (ULONG)i<q; i++, ulBitOffset++){Write1ToBitStream(pBuffer, ulBitOffset); }Write0ToBitStream(pBuffer, ulBitOffset);ulBitOffset++;for(i=0; i<m; i++, ulBitOffset++){if( (r>>i)&1 ){Write1ToBitStream(pBuffer, ulBitOffset);}else{Write0ToBitStream(pBuffer, ulBitOffset);}}return m+q+1;}ULONGReadGolombCode(PULONG pulCodingLength,PUCHAR pBuffer,ULONG ulBitOffset){ULONG q, r;ULONG bit;int i;for(q=0; ;q++){bit = (ULONG)ReadBitFromBitStream(pBuffer, ulBitOffset);ulBitOffset++;if( !bit ){break;}}for(i=0, r=0; (ULONG)i<m; i++, ulBitOffset++){bit = (ULONG)ReadBitFromBitStream(pBuffer, ulBitOffset);bit <<= i;r |= bit;}*pulCodingLength = m + q + 1;return r+(q<<m)+1;}ULONGCompareStrings(PUCHAR string1,PUCHAR string2,ULONG length){ULONG i;PUCHAR p1, p2;p1 = string1;p2 = string2;for(i=0; i<length; i++){if( *p1==*p2 ){p1++;p2++;}else{break;}}return p1-string1;}void WINAPIFindLongestSubstring(PUCHAR pSourceString,PUCHAR pString,ULONG ulSourceStringLength,PULONG pulSubstringOffset,PULONG pulSubstringLength){PUCHAR pSrc;ULONG offset, length;ULONG ulMaxLength;*pulSubstringOffset = offset = 0;*pulSubstringLength = 0;if( NULL==pSourceString || NULL==pString ){return;}ulMaxLength = ulSourceStringLength;pSrc = pSourceString;while( ulMaxLength>0 ){length = CompareStrings(pSrc, pString, ulMaxLength);if( length>*pulSubstringLength ){*pulSubstringLength = length;*pulSubstringOffset = offset;}pSrc++;offset++;ulMaxLength--;}}/*voidFindLongestSubstring(PUCHAR pSourceString,PUCHAR pString,ULONG ulSourceStringLength,PULONG pulSubstringOffset,PULONG pulSubstringLength){PUCHAR pCurrentOffset;PUCHAR p1, p2;ULONG offset, length;pCurrentOffset = pSourceString;*pulSubstringOffset = offset = 0;*pulSubstringLength = length = 0;while( pCurrentOffset<pSourceString+ulSourceStringLength ){p1 = pCurrentOffset;p2 = pString;if( *p1==*p2 ){while( p1<pSourceString+ulSourceStringLength && *p1==*p2 ){p1++;p2++;}length = p1 - pCurrentOffset;}else{length = 0;}if( length>*pulSubstringLength ){*pulSubstringLength = length;*pulSubstringOffset = (ULONG)pCurrentOffset - (ULONG)pSourceString;}pCurrentOffset++;}}*/voidWriteBits(PUCHAR pDataBuffer,ULONG ulOffsetToWrite,ULONG ulBits,ULONG ulBitLength){ULONG ulDwordsOffset;ULONG ulBitsOffset, ulBitsRemained;ulDwordsOffset = ulOffsetToWrite>>5;ulBitsOffset = ulOffsetToWrite&31;ulBitsRemained = 32 - ulBitsOffset;if( 0==ulBitsOffset ){*((PULONG)pDataBuffer+ulDwordsOffset) = ulBits;}else if( ulBitsRemained>=ulBitLength ){*((PULONG)pDataBuffer+ulDwordsOffset) |= (ulBits<<ulBitsOffset);}else{*((PULONG)pDataBuffer+ulDwordsOffset) |= (ulBits<<ulBitsOffset);*((PULONG)pDataBuffer+ulDwordsOffset+1) = ulBits>>ulBitsRemained; }}voidReadBits(PUCHAR pDataBuffer,ULONG ulOffsetToRead,PULONG pulBits){ULONG ulDwordsOffset;ULONG ulBitsOffset, ulBitsLength;ulDwordsOffset = ulOffsetToRead>>5;ulBitsOffset = ulOffsetToRead&31;ulBitsLength = 32 - ulBitsOffset;*pulBits = *((PULONG)pDataBuffer+ulDwordsOffset);if( 0!=ulBitsOffset ){(*pulBits) >>= ulBitsOffset;(*pulBits) |= (*((PULONG)pDataBuffer+ulDwordsOffset+1))<<ulBitsLength; }}voidlz77compress(PUCHAR pDataBuffer,ULONG ulDataLength,PUCHAR pOutputBuffer,PULONG pulNumberOfBits){LONG iSlideWindowPtr;ULONG ulBytesCoded;ULONG ulMaxlength;PUCHAR pSlideWindowPtr;PUCHAR pUnprocessedDataPtr;ULONG offset;ULONG length;ULONG ulCodingLength;ULONG ulBitOffset;UCHAR cc;int i;iSlideWindowPtr = -MAX_WND_SIZE;pSlideWindowPtr = NULL;ulBitOffset = 0;ulBytesCoded = 0;while( ulBytesCoded<ulDataLength ){if( iSlideWindowPtr>=0 ){pSlideWindowPtr = pDataBuffer+iSlideWindowPtr;ulMaxlength = MAX_WND_SIZE;}else if( iSlideWindowPtr>=-MAX_WND_SIZE ){pSlideWindowPtr = pDataBuffer;ulMaxlength = MAX_WND_SIZE + iSlideWindowPtr;}else{pSlideWindowPtr = NULL;ulMaxlength = 0;}pUnprocessedDataPtr = pDataBuffer + ulBytesCoded;if( ulMaxlength>ulDataLength-ulBytesCoded ){ulMaxlength = ulDataLength-ulBytesCoded;}FindLongestSubstring(pSlideWindowPtr,pUnprocessedDataPtr,ulMaxlength,&offset,&length);assert( length<=MAX_WND_SIZE );assert( offset<MAX_WND_SIZE );if(length>1){Write1ToBitStream(pOutputBuffer, ulBitOffset);ulBitOffset++;for(i=0; i<OFFSET_CODING_LENGTH; i++, ulBitOffset++){if( (offset>>i)&1 ){Write1ToBitStream(pOutputBuffer, ulBitOffset);}else{Write0ToBitStream(pOutputBuffer, ulBitOffset);}}ulCodingLength = WriteGolombCode(length, pOutputBuffer, ulBitOffset);ulBitOffset += ulCodingLength;iSlideWindowPtr += length;ulBytesCoded += length;}else{Write0ToBitStream(pOutputBuffer, ulBitOffset);ulBitOffset++;cc = (*pUnprocessedDataPtr);for(i=0; i<8; i++, ulBitOffset++){if( (cc>>i)&1 ){Write1ToBitStream(pOutputBuffer, ulBitOffset);}else{Write0ToBitStream(pOutputBuffer, ulBitOffset);}}iSlideWindowPtr++;ulBytesCoded++;}}if( ulBytesCoded!=ulDataLength ){assert(ulBytesCoded==ulDataLength);}*pulNumberOfBits = ulBitOffset;}void lz77decompress(PUCHAR pDataBuffer,ULONG ulNumberOfBits,PUCHAR pOutputBuffer,PULONG pulNumberOfBytes){LONG iSlideWindowPtr;PUCHAR pSlideWindowPtr;ULONG length, offset;ULONG bit;UCHAR cc;int i;ULONG ulBytesDecoded;ULONG ulBitOffset;ULONG ulCodingLength;PUCHAR pWrite;iSlideWindowPtr = -MAX_WND_SIZE;pWrite = (PUCHAR)pOutputBuffer;ulBitOffset = 0;ulBytesDecoded = 0;while( ulBitOffset<ulNumberOfBits ){bit = ReadBitFromBitStream(pDataBuffer, ulBitOffset);ulBitOffset++;if( bit ){if( iSlideWindowPtr>=0 ){pSlideWindowPtr = pOutputBuffer + iSlideWindowPtr;}else if( iSlideWindowPtr>=-MAX_WND_SIZE ){pSlideWindowPtr = pOutputBuffer;}else{pSlideWindowPtr = NULL;}for(i=0, offset=0; i<OFFSET_CODING_LENGTH; i++, ulBitOffset++){bit = ReadBitFromBitStream(pDataBuffer, ulBitOffset);offset |= (bit<<i);}length= ReadGolombCode(&ulCodingLength, pDataBuffer, ulBitOffset);assert(offset<MAX_WND_SIZE);if( length>MAX_WND_SIZE ){assert(length<=MAX_WND_SIZE);}ulBitOffset += ulCodingLength;RtlMoveMemory(pWrite, pSlideWindowPtr+offset, length);pWrite+=length;iSlideWindowPtr+=length;ulBytesDecoded+=length;}else{for(i=0, cc=0; i<8 ; i++, ulBitOffset++){bit = ReadBitFromBitStream(pDataBuffer, ulBitOffset);cc |= ((UCHAR)bit<<i);}*pWrite++ = cc;iSlideWindowPtr++;ulBytesDecoded++;}}*pulNumberOfBytes = ulBytesDecoded;}extern "C"void WINAPILZ77Compress(PUCHAR __pDataBuffer,ULONG __ulDataLength,PUCHAR __pOutputBuffer,PULONG __pulNumberOfBits);extern "C"void WINAPILZ77Decompress(PUCHAR __pDataBuffer,ULONG __ulNumberOfBits,PUCHAR __pOutputBuffer,PULONG __pulNumberOfBytes);intmain(int argc,char *argv[]){FILE *fp=NULL;FILE *fp1;ULONG fsize;ULONG ulNumberOfBits;ULONG ulFileCompressedSize;ULONG ulFileDecompressedSize;SYSTEMTIME t1, t2;if( 3!=argc ){printf("Usage: lz77 [/c | /d] filename\n");return -1;}// char s1[]="abcdabcdefgabcdefaffasda";// ULONG a, b;// FindLongestSubstring((PUCHAR)s1, (PUCHAR)s1+11, 11,&a, &b ); // return 0;fp = fopen(argv[2], "rb");if( !fp ){return -1;}fseek(fp, 0, SEEK_END);fsize = ftell(fp);fseek(fp, 0, SEEK_SET);fread(__buffer1__, 1, fsize, fp);GetSystemTime(&t1);lz77compress(__buffer1__, fsize, __buffer2__, &ulNumberOfBits);//LZ77Compress(__buffer1__, fsize, __buffer2__, &ulNumberOfBits); GetSystemTime(&t2);ulFileCompressedSize = ((ulNumberOfBits+7)>>3);fp1=fopen("peinfo.c_", "wb+");if( !fp1 ){goto l1;}fwrite(__buffer2__, 1, ulFileCompressedSize, fp1);fclose(fp1);RtlZeroMemory(__buffer1__, sizeof(__buffer1__));lz77decompress(__buffer2__, ulNumberOfBits, __buffer1__, &ulFileDecompressedSize);//LZ77Decompress(__buffer2__, ulNumberOfBits, __buffer1__, &ulFileDecompressedSize); fp1=fopen("peinfo.d_", "wb+");if( !fp1 ){goto l1;}fwrite(__buffer1__, 1, ulFileDecompressedSize, fp1);fclose(fp1);l1:if( fp ){fclose(fp);}ULONG milliS;milliS = ((t2.wHour - t1.wHour)*3600 + (t2.wMinute-t1.wMinute)*60 + (t2.wSecond-t1.wSecond)) * 1000 + (t2.wMilliseconds-t1.wMilliseconds);printf("Totally %ld milliseconds elapsed!\n\n", milliS);printf("Press any key to exit!\n");getch();return 0; }七、实验结果。