clear
clc
% use the command load and data path
load('message.mat')
% have a look at this data. Only two symbols in this vector.
%% Q1 Construct a probability model for the source and compute the corresponding entropy.
N = length(x);
freq = hist(double(x),2); % There are only two symbols in this source, which are Y and N. So we only count the two symbols' frequency.
prob = freq/N;
entropy = sum(-prob .* log2(prob));

%% Q2 Build an instantaneously parsable code for the given source.
%  Q3 Encode the data by using the code proved and calculate compression ratio.

% Firstly, use for-loop to split the string into 2-symbol combination.
for i = 1:2:N-1 
    y{(i+1)/2} = x(i:i+1);
    % y is a cell array which we create to store all the 2-symbol combination strings we split.
    % You can read this webpage to know more about cell array.
    % https://uk.mathworks.com/help/matlab/cell-arrays.html
end

% Then, use for-loop and switch-case to count the frequency of the four kinds of 2-symbol combination in the string.
count1 = 0;
count2 = 0;
count3 = 0;
count4 = 0;
for i = 1:length(y)
 switch y{i}  
     case ['Y';'Y']
         count1 = count1+1;
     case ['Y';'N']
         count2 = count2+1;
     case ['N';'Y']
         count3 = count3+1;
     case ['N';'N']
         count4 = count4+1;
 end    
end
freq1 = count1/length(y);
freq2 = count2/length(y);
freq3 = count3/length(y);
freq4 = count4/length(y);

%========================= contrust a Huffman code tree =========================

encoded = []; % create an empty vector to store the encoded data.
i = 1;
while i<N   % use while-loop to write the encoded data.      
    % extract the next two symbols 
    sequence = x(i:(i+1));
    % use switch case structure to write the encoded string via the Huffman codeword we calculated just now
    switch sequence        
        case ['Y'; 'Y']   
            encoded = cat(1,encoded,[1]);
            % The command 'cat' is used to concatenate arrays. 
            % Here, we use it to concatenate the encoded message
            % Then, we can turn the original "YN" string into '01' string.
        case ['Y'; 'N']            
            encoded = cat(1,encoded,[0; 0]);            
        case ['N'; 'Y']            
            encoded = cat(1,encoded,[0; 1; 1]);            
        case ['N'; 'N']            
            encoded = cat(1,encoded,[0; 1; 0]);
    end         
    i = i + 2;  
end
% Now, we can get the encoded message with shorter string length
% We can calculate how much we compressed the original message data.
compression_ratio = 100*(1-length(encoded)/N);


%%======================================================================================
% Likewise, we can also use for-loop to split the string into 3-symbol combination.
for i = 1:3:N-1
    y1{(i+2)/3} = x(i:i+2);
end
% Then, use switch-case to count the frequency of the eight kinds of 3-symbol combination.
count1 = 0;
count2 = 0;
count3 = 0;
count4 = 0;
count5 = 0;
count6 = 0;
count7 = 0;
count8 = 0;
for i = 1:length(y1)
 switch y1{i}  
     case ['Y';'Y';'Y']
         count1 = count1+1;
     case ['N';'Y';'Y']
         count2 = count2+1;
     case ['Y';'N';'Y']
         count3 = count3+1;
     case ['Y';'Y';'N']
         count4 = count4+1;
     case ['N';'N';'Y']
         count5 = count5+1;
     case ['N';'Y';'N']
         count6 = count6+1;
     case ['Y';'N';'N']
         count7 = count7+1;
     case ['N';'N';'N']
         count8 = count8+1;         
 end    
end
freq1 = count1/length(y);
freq2 = count2/length(y);
freq3 = count3/length(y);
freq4 = count4/length(y);
freq5 = count5/length(y);
freq6 = count6/length(y);
freq7 = count7/length(y);
freq8 = count8/length(y);

%========================= contrust a Huffman code tree =========================

encoded1 = []; % create an empty vector to store the encoded data.
i = 1;
while i < N-1  % use while-loop to write the encoded data.       
    % extract the next two symbols 
    sequence = x(i:(i+2));
    % use switch case structure to write the encoded string via the Huffman codeword we calculated just now
    switch sequence        
        case ['Y';'Y';'Y']
            encoded1 = cat(1,encoded1,[1]);
        case ['N';'Y';'Y']
            encoded1 = cat(1,encoded1,[0;0;1]);
        case ['Y';'N';'Y']
            encoded1 = cat(1,encoded1,[0;1;1]);
        case ['Y';'Y';'N']
            encoded1 = cat(1,encoded1,[0;1;0]);
        case ['N';'N';'Y']
            encoded1 = cat(1,encoded1,[0;0;0;1;1]);
        case ['N';'Y';'N']
            encoded1 = cat(1,encoded1,[0;0;0;1;0]);
        case ['Y';'N';'N']
            encoded1 = cat(1,encoded1,[0;0;0;0;1]);
        case ['N';'N';'N']
            encoded1 = cat(1,encoded1,[0;0;0;0;0]);
    end         
    i = i + 3;  
end
% Now, we can get the encoded message with shorter string length
% We can calculate how much we compressed the original message data.
compression_ratio1 = 100*(1-length(encoded)/N);