数据结构LZW的压缩与解压实验报告Word文档下载推荐.docx
《数据结构LZW的压缩与解压实验报告Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构LZW的压缩与解压实验报告Word文档下载推荐.docx（50页珍藏版）》请在冰点文库上搜索。
（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．对字符进行操作
#include"
stdafx.h"
stdio.h"
memory.h"
assert.h"
lzwtable.h"
lzwcode.h"
/*
CDecodeBitArray
*/
CDecodeBitArray:
:
CDecodeBitArray（DWORDdwInitWidth）//widthinbit
{
m_pbBits=NULL;
m_dwWidthInByte=0;
m_dwTail=m_dwHead=0;
if（dwInitWidth）
InitBits（dwInitWidth）;
}
~CDecodeBitArray（）
ClearBits（）;
voidCDecodeBitArray:
ClearBits（void）
if（m_pbBits）
deletem_pbBits;
InitBits（DWORDdwInitWidth）
{//new
DWORDdwLength=dwInitWidth/8;
dwLength+=（dwInitWidth%8）?
1:
0;
m_pbBits=newBYTE[dwLength];
m_dwHead=m_dwTail=0;
m_dwWidthInByte=dwLength;
InitBytes（DWORDdwInitWidth）
InitBits（dwInitWidth*8）;
DWORDCDecodeBitArray:
GetLeftBytes（void）
DWORDdwLeftBytes;
DWORDdwLeftBits=GetLeftBits（）;
dwLeftBytes=dwLeftBits/8;
dwLeftBytes+=（dwLeftBits%8）?
returndwLeftBytes;
WORDCDecodeBitArray:
RemoveBits（intiWidth）
WORDwGet=0;
for（inti=iWidth-1;
i>
=0;
i--）
{
if（RemoveFirstBit（））
SET_BIT_1（wGet,i）;
}
returnwGet;
RemoveFirstBit（void）
BYTE*pbFirstByte=m_pbBits+m_dwHead/8;
BYTEbFirstByte=*pbFirstByte;
WORDwGet=（CHECK_BIT_1（bFirstByte,7-m_dwHead%8））?
m_dwHead++;
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;
Resort（void）
{//becausem_dwTail%8alwaysequal0
if（m_dwHead<
8）
return;
if（m_dwTail==m_dwHead）
m_dwTail=m_dwHead=0;
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;
else
~CEncodeBitArray（）
BOOLCEncodeBitArray:
assert（dwInitWidth）;
m_dwWidthInByte=dwInitWidth/8;
m_dwWidthInByte+=（dwInitWidth%8）?
m_pbBits=newBYTE[m_dwWidthInByte];
m_dwTail=0;
voidCEncodeBitArray:
AddBits（WORDwAdd,intiWidth）
BYTE*pbByte=m_pbBits+m_dwTail/8;
if（CHECK_BIT_1（wAdd,i））
SET_BIT_1（*pbByte,7-m_dwTail%8）;
else
SET_BIT_0（*pbByte,7-m_dwTail%8）;
m_dwTail++;
DWORDCEncodeBitArray:
GetBytesWidth（void）
DWORDdwBytes=m_dwTail/8;
dwBytes+=（m_dwTail%8）?
returndwBytes;
intCEncodeBitArray:
RemoveBytes（BYTE*pbGet,intiWant）
return-1;
intiTotal=（int）GetBytesWidth（）;
if（iWant>
iTotal）
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（iTail<
0）
iTail=0;
m_dwTail=iTail;
returniWant;
BOOLCLZWDecode:
BeginLZWDecode（constDWORDdwLength,//thecompressedlength
FUN_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+dwRead>
dwLength）
wGetBytes=（WORD）（dwLength-dwRead）;
if（wGetBytes!
=0）
{
pfunLZWGetNextBytes（pbBuffer,wGetBytes）;
m_baContain.AddBytes（pbBuffer,wBuffer）;
dwRead+=wGetBytes;
}
}
intiT=m_iTotalEntry+1;
iT>
>
=9;
iBitWidth=9;
while（iT>
iT>
=1;
iBitWidth++;
WORDwGet=m_baContain.RemoveBits（iBitWidth）;
if（wGet==LZW_END_CODE）
break;
if（wGet==LZW_CLEAR_CODE）
m_LZWTable.InitLZWTable（）;
wGet=m_baContain.RemoveBits（9）;
if（wGet==LZW_END_CODE）
break;
pbDecodedData=m_LZWTable.GetMatchData（wGet）;
WriteDecode（pbDecodedData,
pfunLZWPutNextByte,
pfunLZWDecodedBytes,
dwBytesOnce）;
wOld=wGet;
m_iTotalEntry=258;
{//notclear
if（NULL!
=pbDecodedData）
{//intable
bFirst=pbDecodedData[2];
WriteDecode（pbDecodedData,
pfunLZWPutNextByte,
pfunLZWDecodedBytes,
dwBytesOnce）;
if（wOld!
=LZW_CLEAR_CODE）
{//notthefirstcodebereadin
pbDecodedData=m_LZWTable.GetMatchData（wOld）;
wLastLen=*（（WORD*）pbDecodedData）;
memcpy（pbNewData,pbDecodedData+2,wLastLen）;
pbNewData[wLastLen]=bFirst;
m_LZWTable.AddToChild（（WORD）m_iTotalEntry,pbNewData,wLastLen+1）;
m_iTotalEntry+=1;
}
wOld=wGet;
else
pbDecodedData=m_LZWTable.GetMatchData（wOld）;
wLastLen=*（（WORD*）pbDecodedData）;
memcpy（pbOutData+2,pbDecodedData+2,wLastLen）;
pbOutData[wLastLen+2]=bFirst;
*（（WORD*）pbOutData）=wLastLen+1;
WriteDecode（pbOutData,
if（m_iTotalEntry>
=4096）
{
int_j=0;
m_LZWTable.AddToChild（（WORD）m_iTotalEntry,pbOutData+2,wLastLen+1）;
m_iTotalEntry+=1;
//pbDecodedData=table.GetMatchData（wGet）;
//WORDwLen=*（（WORD*）pbDecodedData）;
//pbDecodedData+=2;
deletepbNewData;
deletepbOutData;
deletepbBuffer;
returndwRead==dwLength;
}
voidCLZWDecode:
WriteDecode（BYTE*pbWrite,
FUN_LZWDECODEPUTNEXTBYTEpfunLZWPutNextByte,
FUN_LZWDECODEDBYTESpfunLZWDecodedBytes,
DWORDdwBytesOnce）
if（pbWrite==NULL）
WORDwLength=*（（WORD*）pbWrite）;
pbWrite+=2;
for（DWORDi=0;
i<
wLength;
i++）
pfunLZWPutNextByte（*pbWrite）;
pbWrite++;
if（（pfunLZWDecodedBytes!
&
&
（dwBytesOnce）
（m_dwDecodedByte%dwBytesOnce==0））
pfunLZWDecodedBytes（）;
m_dwDecodedByte+=wLength;
EndLZWDecode（FUN_LZWDECODEPUTNEXTBYTEpfunLZWPutNextByte）
CLZWEncode
BOOLCLZWEncode:
BeginLZWEncode（constDWORDdwLength,
FUN_LZWENCODEGETNEXTBYTEpfunLZWGetNextByte,
FUN_LZWENCODEPUTNEXTBYTESpfunLZWPutNextBytes,
WORDwBufferLen,
FUN_LZWENCODEDBYTESpfunLZWEncodedBytes,
m_dwCompressedLength=0;
intiBufferLen=wBufferLen;
BYTEbGet;
//inittheentrytable
m_baContain.InitBits（（iBufferLen+8）*8）;
//initthebitarray
m_baContain.AddBits（LZW_CLEAR_CODE,9）;
//addthefirstclearcode
///below:
beginthealgorithm
PLZWENCODEENTRYpCurrent=m_LZWTable.GetHead（）;
intiBitWidth;
DWORDdwEncoded=0;
dwLength;
{//foreachbyte
if（!
pfunLZWGetNextByte（bGet））
returnFALSE;
PLZWENCODEENTRYpChild=m_LZWTable.FindMatchChild（bGet,pCurrent）;
if（pChild）
{//hasfoundthecontinue
pCurrent=pChild;
{//notfindwritelastcode&
addnewentry
iBitWidth=GetBitWidth（）;
WORDwW=pCurrent->
wCode;
m_baContain.AddBits（wW,iBitWidth）;
//addlastcodetobuffer
m_LZWTable.AddToChild（bGet,pCurrent）;
//addlastcodetotable
if（m_baContain.GetBytesWidth（）>
（DWORD）iBufferLen）
m_dwCompressedLength+=（DWORD）iBufferLen;
pfunLZWPutNextBytes（m_baContain.GetBits（）,iBufferLen）;
m_baContain.RemoveBytes（NULL,iBufferLen）;
if（m_LZWTable.GetTableEntryNumber（）>
=（m_wMaxEntry-3））
iBitWidt
升级会员 