lempel_ziv.m

Compression using lempel-ziv -for a dictionary size of 2k -provide dictionary

seq=[1 0 0 1 1 0 0 0 1 0 1 1 1 0] %input binary sequence
dict_contents=[];                 %dictionary content
lctn=[];                          %dictionary locations
packs=[];                         %storing packets
cwords=[];                        %storing codewords
i=1                               %initializing the count  'i'
while(i<length(seq))
if(i==1)
dict_contents=[seq(i)];
packs=[(i-1), seq(i)];
i=i+1;                             %increment the count
else
%Initialize variables
x=0;          % number of previous occurances of a symbol
index=1;      %indicates recurrence of symbols
buffer=[];    %vector for temporary storage
while(index~=-1)
buffer=[buffer seq(i+x)]
% forming a new current symbol by concatenating symbols
current_symbol=0;
m=1;
for k=x :-1:0
current_symbol=current_symbol +  buffer(m)*(10^(k))
m=m+1;
end
% checking recurring symbols
for j=length(dict_contents):-1:1
if(dict_contents(j)==current_symbol)
index=1;           %if current symbol recurrent
break                  %then break from the 'for' loop
end
index=-1;           
end
x=x+1;                         %increment the recurrence count
end
%store last part of current sym. in 'lp'
lp=buffer(length(buffer));        %lp->last part of current symbol
%eliminate last element of buffer vector
buffer=buffer(1:1:(length(buffer)-1));
fp=0;                                      %initialize fp->first part of current symbol
%Concatenate elements of new buffer to form 'fp'
if (size(buffer)~=[0,0])       
for t=1:1:length(buffer)
fp=fp + buffer(t)*(10^(length(buffer)-t));
end
end
p_ad=0;        %initialize prev. address of 'fp' to 0
%Check if 'fp' occurs in previously added contents
for q=length(dict_contents):-1:1
if (dict_contents(q)==fp)          %if found
p_ad=q;                %save fp's prev address in p_ad
break                  %and break from 'for' loop
end
end
packs=[packs; p_ad, lp];       %update packets'
dict_contents=[dict_contents current_symbol]   %update dictionary contents'
i=i+x
end
end
packs  %Displaying packets
dict_contents=dict_contents'     %displaying the dictionary contents
lctn=[1:1:length(dict_contents)]'%Dictionary locations in decimal format
% representing dict. locs in binary format
no_bits=0;
while( (2^(no_bits)) < length(lctn) )
no_bits=no_bits+1;
end
binary=dec2bin( (1:length(dict_contents)), no_bits)
cwords=[dec2bin([packs(:,1)]) dec2bin(packs(:,2))]   %Determining codewords