数据结构LZW的压缩与解压实验报告

数据结构课程设计报告-------LZW压缩与解压学院：计算机学院专业：计算机科学与技术班级：2013级1班姓名：傅娴雅学号：201300130014目录一、问题描述二、设计三、测试结果四、分析与探究五、总结六、附录一、问题描述（1）系统功能1.在一个文本文件上实现LZW压缩和解压缩，其中每个字符就是该文本的8位ASCII码2.在实现LZW过程中需要仔细考虑在编译表中找到匹配或找不到匹配，需要注意匹配算法的时间、空间开销3.*应用LZW算法实现256色灰度BMP图像文件的压缩和解压缩（2）输入要求用MFC做出了图形化界面，不再需要命令行输入，故输入只需在编辑框输入正确的地址或者直接选择。（3）输出要求消息框提示操作成功，能生成压缩或者解压缩之后的文件。（4）界面设计用MFC生成相应界面，能对压缩或者解压缩操作进行选择，减少界面的冗余度。（5）测试设计找一篇3000字的文章放于txt文件中，测试程序能否压缩成功及压缩的速率。同时利用压缩的文件进行解压缩。照一张256色灰度BMP图像，进行相应的压缩与解压缩过程二、设计（1）系统设计LZW压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch三人共同创造，用他们的名字命名。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃。词典编码主要利用数据本身包含许多重复的字符串的特性，用一些简单的代号代替那些重复出现的字符串，从而实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。在本次实验中所用到的LZW(Lempel-ZivWalch)压缩编码方法。LZW的核心思想是用短的编码代替字符串。它不对输入的字符串做任何分析，只是将收到的每一个新字符串添加到一张字符串表中。当已经出现的字符串再次出现，即用一个短的编码代替该字符串，这就实现了压缩。（2）数据结构预算法设计此次实验中采用链表散列的存储方式，牺牲空间以换取时间。采用二进制形式输入，除数设为4096，对前256位初始化，空间用完时丢弃，在后面进行解压过程中重建。A．压缩算法：•1.从输入流中读入一个字符，作为当前串的后缀。•2.如果当前串在字典中，就用当前串的编码作前缀，转到第1步。•3.如果当前串不在字典中，就把当前串放到字典中，并把前缀放到输出流，后缀变前缀，转到第1步。•4.当输入流读完了后，串中应该还剩一个前缀，把它放到输出流，结束。解压缩算法与压缩算法类似三、测试结果（1）测试过程（2）测试问题能够实现文本的压缩与解压缩，且压缩过程速度较快，bmp图像的压缩过程也能实现，但是解压缩过程并不能实现。四．分析与探究（1）测试结果分析借助MFC使得程序可视化程度较高，程序运行速度较快，然而最终没能完成所要求的图形的压缩与解压缩过程，程序面向的对象相对来说较为狭窄。（2）思考在网上有查到可以利用树结构来存储，可能会进一步减小程序的时间复杂度。然而没有能够很明白这种结构，最终还是采用了课本上提供的算法思想五．总结在课本上找得到这个问题的解决方法，然而按照课本上的程序，在进行压缩和解压缩的步骤分开，使得整个方法变得特别的冗余，利用MFC进行第一次修改之后在一定程度上有所改善，在最后一次进行修改之后终于达到了想要的效果。总而言之，这是一次特别好的开发经历，其中各种波折让我对于数据结构的选择，等等一些列问题有了新的认知。五．附录以下是MFC中自己建的类1．对字符进行操作#includestdafx.h#includestdio.h#includememory.h#includeassert.h#includelzwtable.h#includelzwcode.h/*CDecodeBitArray*/CDecodeBitArray::CDecodeBitArray(DWORDdwInitWidth)//widthinbit{m_pbBits=NULL;m_dwWidthInByte=0;m_dwTail=m_dwHead=0;if(dwInitWidth)InitBits(dwInitWidth);}CDecodeBitArray::~CDecodeBitArray(){ClearBits();}voidCDecodeBitArray::ClearBits(void){if(m_pbBits)deletem_pbBits;m_dwTail=m_dwHead=0;m_dwWidthInByte=0;}voidCDecodeBitArray::InitBits(DWORDdwInitWidth){//newClearBits();DWORDdwLength=dwInitWidth/8;dwLength+=(dwInitWidth%8)?1:0;m_pbBits=newBYTE[dwLength];m_dwHead=m_dwTail=0;m_dwWidthInByte=dwLength;}voidCDecodeBitArray::InitBytes(DWORDdwInitWidth){//newInitBits(dwInitWidth*8);}DWORDCDecodeBitArray::GetLeftBytes(void){DWORDdwLeftBytes;DWORDdwLeftBits=GetLeftBits();dwLeftBytes=dwLeftBits/8;dwLeftBytes+=(dwLeftBits%8)?1:0;returndwLeftBytes;}WORDCDecodeBitArray::RemoveBits(intiWidth){WORDwGet=0;for(inti=iWidth-1;i=0;i--){if(RemoveFirstBit())SET_BIT_1(wGet,i);}returnwGet;}WORDCDecodeBitArray::RemoveFirstBit(void){BYTE*pbFirstByte=m_pbBits+m_dwHead/8;BYTEbFirstByte=*pbFirstByte;WORDwGet=(CHECK_BIT_1(bFirstByte,7-m_dwHead%8))?1:0;m_dwHead++;returnwGet;}BOOLCDecodeBitArray::AddBytes(BYTE*pbAdd,intiLength){if(m_pbBits==NULL)returnFALSE;Resort();memcpy(m_pbBits+m_dwTail/8,pbAdd,iLength);m_dwTail+=8*(DWORD)iLength;returnTRUE;}voidCDecodeBitArray::Resort(void){//becausem_dwTail%8alwaysequal0if(m_dwHead8)return;if(m_dwTail==m_dwHead){m_dwTail=m_dwHead=0;return;}DWORDdwLength=GetLeftBytes();DWORDdwHead=m_dwHead%8;DWORDdwMove=m_dwHead-dwHead;memcpy(m_pbBits,m_pbBits+(m_dwHead/8),(int)dwLength);m_dwHead=dwHead;m_dwTail-=dwMove;}/*classCEncodeBitArray*/CEncodeBitArray::CEncodeBitArray(DWORDdwInitWidth){if(dwInitWidth==0)m_pbBits=NULL;elseInitBits(dwInitWidth);}CEncodeBitArray::~CEncodeBitArray(){ClearBits();}BOOLCEncodeBitArray::InitBits(DWORDdwInitWidth){ClearBits();assert(dwInitWidth);m_dwWidthInByte=dwInitWidth/8;m_dwWidthInByte+=(dwInitWidth%8)?1:0;m_pbBits=newBYTE[m_dwWidthInByte];m_dwTail=0;returnTRUE;}voidCEncodeBitArray::ClearBits(void){if(m_pbBits)deletem_pbBits;m_pbBits=NULL;}BOOLCEncodeBitArray::AddBits(WORDwAdd,intiWidth){if(m_pbBits==NULL)returnFALSE;for(inti=iWidth-1;i=0;i--){BYTE*pbByte=m_pbBits+m_dwTail/8;if(CHECK_BIT_1(wAdd,i))SET_BIT_1(*pbByte,7-m_dwTail%8);elseSET_BIT_0(*pbByte,7-m_dwTail%8);m_dwTail++;}returnTRUE;}DWORDCEncodeBitArray::GetBytesWidth(void){DWORDdwBytes=m_dwTail/8;dwBytes+=(m_dwTail%8)?1:0;returndwBytes;}intCEncodeBitArray::RemoveBytes(BYTE*pbGet,intiWant){if(m_pbBits==NULL)return-1;intiTotal=(int)GetBytesWidth();if(iWantiTotal)iWant=iTotal;if(pbGet!=NULL)memcpy(pbGet,m_pbBits,iWant);memcpy(m_pbBits,m_pbBits+iWant,iTotal-iWant);intiTail=(int)m_dwTail;iTail-=iWant*8;if(iTail0)iTail=0;m_dwTail=iTail;returniWant;}BOOLCLZWDecode::BeginLZWDecode(constDWORDdwLength,//thecompressedlengthFUN_LZWDECODEGETNEXTBYTESpfunLZWGetNextBytes,FUN_LZWDECODEPUTNEXTBYTEpfunLZWPutNextByte,WORDwBuffer,FUN_LZWDECODEDBYTESpfunLZWDecodedBytes,DWORDdwBytesOnce){m_dwDecodedByte=0;//printf(enterdecodepressakey\n);BYTE*pbNewData=newBYTE[4000],*pbOutData=newBYTE[4000];BYTE*pbBuffer=newBYTE[wBuffer];BYTEbFirst;m_LZWTable.InitLZWTable();intiBitWidth=9;m_iTotalEntry=LZW_BEGIN_ENTRY;BYTE*pbDecodedData;WORDwOld,wLastLen;m_baContain.InitBits((wBuffer+20)*8);intiR=0;DWORDdwRead=0;while(1){if(m_baContain.GetLeftBytes()5){WORDwGetBytes=wBuffer;if((DWORD)wGetBytes+dwReaddwLength)