lempel_ziv.m

读入一段数据

% Source Coding -- Problem 3.2 Lempel-Ziv coding

function Lempel_Ziv

clear

out=fileread('lz_problem.txt');

bit(1)=out(1);                          % the first bit 
sub(1,1)=bit(1);                        % also the first substring
n=2;                                    % then start from the second bit of the text
sn=2;                                   % also for s(n)

while n<length(out)             
    pointer_length=ceil(log2(sn));      % calculate the ceiling value of log2(s(n))
    pointer(sn)=bin2dec(out(n:n+pointer_length-1)); % get the 'pointer' of s(n), converting from binary to decimal
    bit(sn)=out(n+pointer_length);      % get the 'bit' of s(n)
    
    if pointer(sn)~=0
        sub(sn,:)=sub(pointer(sn),:);   % substring has two parts: pointer and bit
        sub(sn,length(sub(sn,:))+1)=bit(sn);
    else                                % the situation that pointer of s(n) is zero
        sub(sn,1)=bit(sn);              % substring is just the 'bit'
    end
   
    sn=sn+1;
    n=n+pointer_length+1;               % go to the next substring
    
end


[a,b]=size(sub);
count=0;                                % used to calculate the length of the whole source code

% to reshape the substrings into a vector
for p=1:a
    for q=1:b
        if sub(p,q)=='0' | sub(p,q)=='1'
            count=count+1;
            code(count)=sub(p,q);
            
        end
    end
end

ch=0;
pos=1;
while pos<length(code)
    ch=ch+1;
    text(ch)=char(bin2dec(code(pos:pos+5))+32); % to read in every 6 bits and convert them into the symbols
    pos=pos+6;
end
text