lz77.m

data compression, lossless methods, LZ family

function [CR,timeC,timeDC]=LZ77(str)
fprintf('LZ77 is started.');

str=strrep(str,' ','_');
str=strcat(str,'$');

searchWindowLen=31;
lookAheadWindowLen=31;

fprintf('Compression');
tic
coded=encode(str,searchWindowLen,lookAheadWindowLen)
timeC=toc;

fprintf('Decompression');
tic
decoded=decode(coded,searchWindowLen,lookAheadWindowLen);
timeDC=toc;

ok=isequal(str,decoded)
CR=(length(str)*8)/(length(coded));
fprintf('LZ77 is finished.');
end
%---------------------------------------------------------
function result=returnPartOfString(str,startindex,endindex)
result='';
for i=startindex:endindex
    result=strcat(result,str(i));
end
end
%---------------------------------------------------------
function decompressed=decode(binaryStr,searchWindowLen,lookAheadWindowLen)
decompressed='';
bytenumSW=length(dec2bin(searchWindowLen));
bytenumLA=length(dec2bin(lookAheadWindowLen));
i=1;
while i<length(binaryStr)
    SW=returnPartOfString(binaryStr,i,i-1+bytenumSW);
    SWdec=bin2dec(SW);
    i=i+bytenumSW;    
    if(SWdec~=0)
        LA=returnPartOfString(binaryStr,i,i-1+bytenumLA);
        LAdec=bin2dec(LA);
        i=i+bytenumLA;
    else
        LAdec=0;
    end
    
    Chr=returnPartOfString(binaryStr,i,i-1+8);
    Chrch=char(bin2dec(Chr));
    i=i+8;
    if(SWdec==0)
        decompressed=strcat(decompressed,Chrch);
    else
        location=length(decompressed)-SWdec;
        for j=1:LAdec
        decompressed=strcat(decompressed,decompressed(location+j));
        
        
        end
        decompressed=strcat(decompressed,Chrch);
        
    end    
end
end
%---------------------------------------------------------
function compressed=encode(str,searchWindowLen,lookAheadWindowLen)
compressed='';
i=1; 
while i<=length(str) 
    startindex=i-searchWindowLen;
    if(startindex)<1
        startindex=1;
    end
        
    
    if(i==1)
        searchBuffer='';
    else
    searchBuffer= returnPartOfString(str,startindex,i-1)
    end   
     
    endindex=i+lookAheadWindowLen-1;
    if(endindex)>length(str)
        endindex=length(str);
    end
    lookAheadBuffer=returnPartOfString(str,i,endindex)
   
    j=1;
    tobesearched=returnPartOfString(lookAheadBuffer,1,j);
    searchresult=strfind(searchBuffer,tobesearched);
    
    if(numel(lookAheadBuffer) > j)
        while (size(searchresult)~=0)
            j=j+1;
            if(j<=numel(lookAheadBuffer))
     
            tobesearched=returnPartOfString(lookAheadBuffer,1,j);
            searchresult=strfind(searchBuffer,tobesearched);
            else
                break;
            end
        end
    end
    if (j>1)
    tobesearched=returnPartOfString(lookAheadBuffer,1,j-1);
    searchresult=strfind(searchBuffer,tobesearched);
    end

    dim=size(searchresult);
    if(dim>0)
        occur=length(searchBuffer)-searchresult(dim(2))+1;
    else
        occur=0;
    end
   
    bytenum=length(dec2bin(searchWindowLen));
    if(occur~=0)
        compressed=strcat(compressed,addZeros(dec2bin(occur),bytenum));
        compressed=strcat(compressed,addZeros(dec2bin(j-1),bytenum));
        occur
        j-1
        if(j>searchWindowLen)
            compressed=strcat(compressed,addZeros(dec2bin(str(i+j)-0),8));
            str(i+j)
        else
            compressed=strcat(compressed,addZeros(dec2bin(lookAheadBuffer(j)-0),8));
            lookAheadBuffer(j)
        end
        
    else
        compressed=strcat(compressed,addZeros(dec2bin(occur),bytenum));
        occur
        if(j>searchWindowLen)
            compressed=strcat(compressed,addZeros(dec2bin(str(i+j)-0),8));
            str(i+j)
        else
            compressed=strcat(compressed,addZeros(dec2bin(lookAheadBuffer(j)-0),8));
            lookAheadBuffer(j)
        end
        
    end

    i=i+j;
    
end
end
%------------------------------------------------------
function str=addZeros(str,num)
for i=1:(num-length(str))
    str=strcat('0',str);
end
end