Shannon fano in matlab

function  shannon_fano(keyword)

probabilities_calculation = zeros(size(keyword));

for i = 1:length(keyword)  %find the probabilities of the symbols/occurence of each letter

probabilities_calculation(i) = sum(keyword==keyword(i))/length(keyword);

end

p = sort(probabilities_calculation(:),'descend');

      shannon_encoder(1,length(p),p);

%-------------------------------------------------------------------%
function shannon_encoder(begin_point,end_point,p)

high_point = begin_point;
low_point = end_point;
high_sum = p(begin_point);
low_sum = p(end_point);

while(high_point ~= low_point-1)
    if (high_sum > low_sum)
        low_point = low_point - 1;
        low_sum = low_sum + p(low_point);
    else
        high_point = high_point + 1;
        high_sum = high_sum + p(high_point);
    end
end

for i = begin_point:high_point
    p(i) = 0;
end

for j = low_point:end_point
    p(j) = 1;
end

if(high_point-begin_point+1 > 1)

      shannon_encoder(begin_point,high_point,p);
  end

if(end_point-low_point+1 > 1)

      shannon_encoder(low_point,end_point,p);

end

[Maheen]

What is the problem in it....can any one help ?

Answer 1

[Geoff Hayes]

Maheen - one problem is with the way that you are computing the probabilities. I think that you need to determine the unique characters in your keyword and then compute the probability for each. The way that your code seems to be working is that it will calculate a probability for each character regardless as to whether this probability has already been calculated already or not. The probabilities_calculation array should sum to one, so what you need to do is something more like

symbols = unique(keyword);
probabilities_calculation = zeros(size(symbols));
for i = 1:length(symbols)  %find the probabilities of the symbols/occurence of each letter
    probabilities_calculation(i) = sum(keyword== symbols(i))/length(keyword);
end
p = sort(probabilities_calculation(:),'descend');

We create the list of symbols of unique characters from the keyword and compute the probability of each character. Be aware that at this point (because you have sorted the probabilities) you have lost the "connection" between the probability and the symbol it is "linked" to. So you will need to update your code in order to account for this.

The next problem seems to be with the recursive shannon_encoder function. It needs to return something so that you can build your bit string appropriately. Moreover, you don't want to be updating the probabilities p at each iteration, you will want to create a new cell array of strings to manage the (string) binary codes.

Your question seems much like a homework one, so you will have to complete the task. But your next steps (after the sort) should be something like this

 % create the cell array of codes
 codes = cell(size(symbols));

 % call the recursive encoder function
 codes = shannon_encoder(1,length(p),p,codes);

Note how codes is passed in as an input argument and is the output parameter as well. Your function, shannon_encoder, will have to update codes by concatenating the '0' or '1' string to the existing code (for each symbol).

Try implementing the above and see what happens!

Answer 2

[Amina NABTI]

can you please explain the use of the while loop.

Answer 3

[Manu t]

function shannon_fano(keyword)

probabilities_calculation = zeros(size(keyword));

for i = 1:length(keyword) %find the probabilities of the symbols/occurence of each letter

probabilities_calculation(i) = sum(keyword==keyword(i))/length(keyword);

end

p = sort(probabilities_calculation(:),'descend');

      shannon_encoder(1,length(p),p);

%-------------------------------------------------------------------% function shannon_encoder(begin_point,end_point,p)

high_point = begin_point; low_point = end_point; high_sum = p(begin_point); low_sum = p(end_point);

while(high_point ~= low_point-1) if (high_sum > low_sum) low_point = low_point - 1; low_sum = low_sum + p(low_point); else high_point = high_point + 1; high_sum = high_sum + p(high_point); end end

for i = begin_point:high_point p(i) = 0; end

for j = low_point:end_point p(j) = 1; end

if(high_point-begin_point+1 > 1)

      shannon_encoder(begin_point,high_point,p);
  end

if(end_point-low_point+1 > 1)

      shannon_encoder(low_point,end_point,p);

end

Answer 4

[Nithish]

function shannon_fano(keyword)

probabilities_calculation = zeros(size(keyword));

for i = 1:length(keyword) %find the probabilities of the symbols/occurence of each letter

probabilities_calculation(i) = sum(keyword==keyword(i))/length(keyword);

end

p = sort(probabilities_calculation(:),'descend');

      shannon_encoder(1,length(p),p);

%-------------------------------------------------------------------% function shannon_encoder(begin_point,end_point,p)

high_point = begin_point; low_point = end_point; high_sum = p(begin_point); low_sum = p(end_point);

while(high_point ~= low_point-1) if (high_sum > low_sum) low_point = low_point - 1; low_sum = low_sum + p(low_point); else high_point = high_point + 1; high_sum = high_sum + p(high_point); end end

for i = begin_point:high_point p(i) = 0; end

for j = low_point:end_point p(j) = 1; end

if(high_point-begin_point+1 > 1)

      shannon_encoder(begin_point,high_point,p);
  end

if(end_point-low_point+1 > 1)

      shannon_encoder(low_point,end_point,p);

end