LZW-编码算法的实现

……装………订…………线……………装………订…………线………专业班级信息09-1学号姓名成绩一、实验目的1、学习Matlab软件的使用和编程2、进一步深入理解LZW编码算法的原理二、实验内容1、使用MATLAB软件编写程序将“/WED/WE/WEE/WEB/WET”进行编译码。三、实验原理LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如"print"字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将"print"字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串"print"，在解压缩时，串表可以根据压缩数据重新生成。四、LZW编码的Matlab源程序及运行结果%FromthearticlereferencedbytheoriginalauthorsP='/WED/WE/WEE/WEB/WET';%lzwInput=uint8('/WED/WE/WEE/WEB/WET');lzwInput=uint8(P);[lzwOutput,lzwTable]=norm2lzw(lzwInput);fprintf('\n');fprintf('Input:');%disp(P);fprintf('%02x',lzwInput);fprintf('\n');fprintf('Output:');fprintf('%02x',lzwOutput);fprintf('\n');forii=257:length(lzwTable.codes) fprintf('Code:%02x,LastCode%02x+%02xLength%3d\n',ii,lzwTable.codes(ii).lastCode,...lzwTable.codes(ii).c,lzwTable.codes(ii).codeLength)end;%TeststhespecialdecodercaseP='Anotherproblemonlongfilesisthatfrequentlythecompressionratiobegins...';%'todegradeasmoreofthefileisreadin.Thereasonforthisissimple.Since...';%'thestringtableisoffinitesize,afteracertainnumberofstringshavebeen...';%'defined,nomorecanbeadded.Butthestringtableisonlygoodfortheportion...';%'ofthefilethatwasreadinwhileitwasbuilt.Latersectionsofthefilemay...';%'havedifferentcharacteristics,andreallyneedadifferentstringtable.The...';%'conventionalwaytosolvethisproblemistomonitorthecompressionratio.After...';%'thestringtableisfull,thecompressorwatchestoseeifthecompressionratio...';%'degrades.Afteracertainamountofdegradation,theentiretableisflushed,and...';%'getsrebuiltfromscratch.Theexpansioncodeisflaggedwhenthishappensbyseeing...';%'aspecialcodefromthecompressionroutine.Analternativemethodwouldbetokeep...';%'trackofhowfrequentlystringsareused,andtoperiodicallyflushvaluesthatare...';%'rarelyused.Anadaptivetechniquelikethismaybetoodifficulttoimplementina...';%'reasonablysizedprogram.Onefinaltechniqueforcompressingthedataistotakethe...';%'LZWcodesandrunthemthroughanadaptiveHuffmancodingfilter.Thiswillgenerally...';%'exploitafewmorepercentagepointsofcompression,butatthecostofconsiderable...';%'morecomplexityinthecode,aswellasquiteabitmoreruntime.';lzwInput=uint8(P);[lzwOutput,lzwTable]=norm2lzw(lzwInput);fprintf('\n');fprintf('Input:');fprintf('%02x',lzwInput);%disp(P);fprintf('\n');fprintf('Output:');fprintf('%02x',lzwOutput);fprintf('\n');forii=257:length(lzwTable.codes) fprintf('Code:%02x,LastCode%02x+%02xLength%3d\n',ii,lzwTable.codes(ii).lastCode,lzwTable.codes(ii).c,lzwTable.codes(ii).codeLength)end;[lzwOutputd,lzwTabled]=lzw2norm(lzwOutput);fprintf('\n');fprintf('Input:');fprintf('%02x',lzwOutput);fprintf('\n');fprintf('Output:');fprintf('%02x',lzwOutputd);P1=char(lzwOutputd);%disp(P1);fprintf('\n');forii=257:length(lzwTabled.codes) fprintf('Code:%02x,LastCode%02x+%02xLength%3d\n',ii,lzwTabled.codes(ii).lastCode,lzwTabled.codes(ii).c,lzwTabled.codes(ii).codeLength)end;function[output,table]=lzw2norm(vector,maxTableSize,restartTable)%LZW2NORMLZWDataCompression(decoder)%Forvectors,LZW2NORM(X)istheuncompressedvectorofXusingtheLZWalgorithm.%[...,T]=LZW2NORM(X)returnsalsothetablethatthealgorithmproduces.%%Formatrices,X(:)isusedasinput.%%maxTableSizecanbeusedtosetamaximumlengthofthetable.Default%is4096entries,useInfforunlimited.Usualsizesare12,14and16%bits.%% IfrestartTableisspecified,thenthetableisflushedwhenitreaches% itsmaximumsizeandanewtableisbuilt.%%Inputmustbeofuint16type,whiletheoutputisauint8.%Tableisacellarray,eachelementcontainigthecorrespondingcode.%%Thisisanimplementationofthealgorithmpresentedinthearticle%%SeealsoNORM2LZW%$Author:GiuseppeRidino'$%$Revision:1.0$$Date:10-May-200414:16:08$%Howitdecodes:%%ReadOLD_CODE%outputOLD_CODE%CHARACTER=OLD_CODE%WHILEtherearestillinputcharactersDO%ReadNEW_CODE%IFNEW_CODEisnotinthetranslationtableTHEN%STRING=gettranslationofOLD_CODE%STRING=STRING+CHARACTER%ELSE%STRING=gettranslationofNEW_CODE%ENDofIF%outputSTRING%CHARACTER=firstcharacterinSTRING%addtranslationofOLD_CODE+CHARACTERtothetranslationtable%OLD_CODE=NEW_CODE%ENDofWHILE%Ensuretohandleuint8inputvectorandconvert%toarowif~isa(vector,'uint16'), error('inputargumentmustbeauint16vector')Endvector=vector(:)';if(nargin<2) maxTableSize=4096; restartTable=0;end;if(nargin<3) restartTable=0;end; functioncode=findCode(lastCode,c) %Lookupcodevalue %if(isempty(lastCode)) % fprintf('findCode:----+%02x=',c); %else % fprintf('findCode:%04x+%02x=',lastCode,c); %end; if(isempty(lastCode)) code=c+1; %fprintf('%04x\n',code); return; Else ii=table.codes(lastCode).prefix; jj=find([table.codes(ii).c]==c); code=ii(jj); % if(isempty(code)) % fprintf('----\n'); % else % fprintf('%04x\n',code); % end; return; end; End function[]=addCode(lastCode,c) %Addanewcodetothetable e.c=c; %NBusingvariableinparenttoavoidallocationcost e.lastCode=lastCode; e.prefix=[]; e.codeLength=table.codes(lastCode).codeLength+1; table.codes(table.nextCode)=e; table.codes(lastCode).prefix=[table.codes(lastCode).prefixtable.nextCode]; table.nextCode=table.nextCode+1; %if(isempty(lastCode)) % fprintf('addCode:----+%02x=%04x\n',c,table.nextCode-1); %else % fprintf('addCode:%04x+%02x=%04x\n',lastCode,c,table.nextCode-1); %end; End functionstr=getCode(code) %Outputthestringforacode l=table.codes(code).codeLength; str=zeros(1,l); forii=l:-1:1 str(ii)=table.codes(code).c; code=table.codes(code).lastCode; end; End function[]=newTable %Buildtheinitialtableconsistingofallcodesoflength1.Thestrings %arestoredasprefixCode+character,sothattestingisveryquick.To %speedupsearching,westorealistofcodesthateachcodeistheprefix %for. e.c=0; e.lastCode=-1; e.prefix=[]; e.codeLength=1; table.nextCode=2; if(~isinf(maxTableSize)) table.codes(1:maxTableSize)=e;%Pre-allocateforspeed Else table.codes(1:65536)=e;%Pre-allocateforspeed end; forc=1:255 e.c=c; e.lastCode=-1; e.prefix=[]; e.codeLength=1; table.codes(table.nextCode)=e; table.nextCode=table.nextCode+1; end; End%%Mainloop%e.c=0;e.lastCode=-1;e.prefix=[];e.codeLength=1;newTable;output=zeros(1,3*length(vector),'uint8');%assumecompressionof33%outputIndex=1;lastCode=vector(1);output(outputIndex)=table.codes(vector(1)).c;outputIndex=outputIndex+1;character=table.codes(vector(1)).c;、、tic;forvectorIndex=2:length(vector), % ifmod(vectorIndex,1000)==0 % fprintf('Index:%5d,Time%.1fs,TableLength%4d,Complete%.1f%%\n',outputIndex,toc,table.nextCode-1,vectorIndex/length(vector)*100);%*ceil(log2(size(table,2)))/8); % tic; % end; element=vector(vectorIndex); if(element>=table.nextCode) %addcodesnotintable,aspecialcase. str=[getCode(lastCode)character]; else, str=getCode(element); End output(outputIndex+(0:length(str)-1))=str; outputIndex=outputIndex+length(str); if((length(output)-outputIndex)<1.5*(length(vector)-vectorIndex)) output=[outputzeros(1,3*(length(vector)-vectorIndex),'uint8')]; end; if(length(str)<1) keyboard; end; character=str(1); if(table.nextCode<=maxTableSize) addCode(lastCode,character); if(restartTable&&table.nextCode==maxTableSize+1) %fprintf('Newtable\n'); newTable; end; end; lastCode=element;end;output=output(1:outputIndex-1);table.codes=table.codes(1:table.nextCode-1);Endfunction[output,table]=norm2lzw(vector,maxTableSize,restartTable)%NORM2LZWLZWDataCompressionEncoder%Forvectors,NORM2LZW(X)isthecompressedvectorofXusingtheLZWalgorithm.%[...,T]=NORM2LZW(X)returnsalsothetablethatthealgorithmproduces.%Formatrices,X(:)isusedasinput.%maxTableSizecanbeusedtosetamaximumlengthofthetable.Default%is4096entries,useInfforunlimited.Usualsizesare12,14and16%bits.% IfrestartTableisspecified,thenthetableisflushedwhenitreaches% itsmaximumsizeandanewtableisbuilt.%Inputmustbeofuint8type,whiletheoutputisauint16.%Tableisacellarray,eachelementcontainingthecorrespondingcode.%Thisisanimplementationofthealgorithmpresentedinthearticle%SeealsoLZW2NORM%$Author:GiuseppeRidino'$%$Revision:1.0$$Date:10-May-200414:16:08$%Revision:%Changethecodetablestructuretoimprovetheperformance.%date:22-Apr-2007%by:HaiyongXu% Reworkthecodetablecompletelytogetreasonableperformance.% date:24-Jun-2007% by:DuncanBarclay%Howitencodes:%STRING=getinputcharacter%WHILEtherearestillinputcharactersDO%CHARACTER=getinputcharacter%IFSTRING+CHARACTERisinthestringtablethen%STRING=STRING+character%ELSE%outputthecodeforSTRING%addSTRING+CHARACTERtothestringtable%STRING=CHARACTER%ENDofIF%ENDofWHILE