huffman.m

m&#227 huffman in mathlab

function [code, weight, entropy,] = huffman(p)
% function [code, weight, entropy] = huffman(p)
% input:
%     p : vecto xac suat voi tap cac ki tu cho truoc
% output: 
%     code : bo tu ma tuong ung voi ki tu p
%     weight : do dai trung binh cua cay Huffman
%     entropy : entropy cua vecto p
    if(length(find(p<0))~=0) error('error, ton tai xac xuat am');
    end;
    if(sum(p)~=1) error('Tong cac xac xuat khong bang 1');
    end;
    n = length(p);
    for i = 1:2*n-1 
        if(i~=2*n-1) huff(i) = i;
        else huff(i) = 0;
        end;
    end;
    
%     tao cay Huffman
    W1 = p;
    for j = n+1:2*n-1 
        [xmin1,l1] = min(W1);
        W1(l1) = 2;
        [xmin2,l2] = min(W1);
        W1(l2) = 2;
        W1(j) = xmin1+xmin2;
        if(xmin1<xmin2) 
            huff(l1) = -j;
            huff(l2) = j;
        else huff(l1) = j;
            huff(l2)= -j;
        end;
    end;
    
%     xac dinh bo tu ma
    for i = 1:n
        j = i;
        code(1,i) = {''};
        while(1)
            if(huff(j)<0) code(1,i) = strcat('0',code(1,i));
            else code(1,i) = strcat('1',code(1,i));
            end;
            j = abs(huff(j));
            if(j==2*n-1) break;
            end;
        end;
    end;
    l = 0;
    for i=1:n 
        l(i) = length(code{1,i});
    end;
    weight = sum(l.*p);
    entropy = -sum(p.*log2(p));
    
    return;