%-------------------------------------------------
%函數名稱：huffman
%函數功能：對概率向量進行二元Huffman編碼
%函數作者：韓  超
%完成時間：2008-01-19
%-------------------------------------------------

%%%%%%%%%%%%%%%%% 參 數 信 息 %%%%%%%%%%%%%%%%%%%%
%-------------------------------------------------
%input:  X->概率向量，
%output: Y->碼字數組，碼字的順序與概率的順序是一一對應的
%-------------------------------------------------

%%%%%%%%%%%%%%%%% 實 驗 數 據 %%%%%%%%%%%%%%%%%%%%
%-------------------------------------------------
%clear all;
%tic;
%X=[0.1 0.2 0.5 0.05 0.15];
%-------------------------------------------------


function Y=huffman(X)

%檢驗是否是概率向量
if ~( isvector(X) ) || ( any(X<0)||any(X>1)||(1==sum(X)) )%??????????
    disp('It is not a probability vector!');
    return;
end

%準備變量，并初始化
X_use=X;
nFrqs=length(X);
num_Frqs=ones(1,nFrqs);%看此概率是由幾個概率分量合并而成
%code_Frqs=zeros(1,nFrqs);
map=1:nFrqs;%腳標代表灰度，數組內容代表灰度對應概率在概率向量里面的腳標值。
for m=1:nFrqs
    code_Frqs{1,m}='';
end

%將概率向量排序
for m=1:(nFrqs-1)
    for n=1:(nFrqs-m)
        if X_use(n)>X_use(n+1)
            %將頻率交換
            tempfrqs=X_use(n);
            X_use(n)=X_use(n+1);
            X_use(n+1)=tempfrqs;
            %將映射表對應的部分交換
            for k=1:nFrqs
                if n==map(k)
                    map(k)=n+1;
                elseif n+1==map(k)
                    map(k)=n;
                end
            end
        end
    end
end

%編碼
for m=1:(nFrqs-1)
    %對最小的兩個概率分量添加碼元
    for n=1:nFrqs
        if map(n)==m
            code_Frqs{1,n}=strcat('1',code_Frqs{1,n});
        elseif map(n)==m+1
            code_Frqs{1,n}=strcat('0',code_Frqs{1,n});
        end
    end
    %將最小的兩個概率分量合并,并將已被合并分量設置為零
    X_use(m+1)=X_use(m+1)+X_use(m);
    X_use(m)=0;
    %改變映射表
    for k=1:nFrqs
        if m==map(k)
            map(k)=m+1;
        end
    end
    %將頻率對應的分量數目改變
    num_Frqs(1,m+1)=num_Frqs(1,m+1)+num_Frqs(1,m);
    num_Frqs(1,m)=-10;
    %對新生成的概率向量排序
    for n=m+1:nFrqs-1
        if ( X_use(n)>X_use(n+1) ) || ( (X_use(n)==X_use(n+1)) && (num_Frqs(1,n)>num_Frqs(1,n+1)) )
            %將頻率交換
            tempfrqs=X_use(n);
            X_use(n)=X_use(n+1);
            X_use(n+1)=tempfrqs;
            %將所包含的頻率分量數目作對應交換
            temp_num_Frqs=num_Frqs(1,n);
            num_Frqs(1,n)=num_Frqs(1,n+1);
            num_Frqs(1,n+1)=temp_num_Frqs;
            %將映射表對應的部分交換
            for k=1:nFrqs
                if n==map(k)
                    map(k)=n+1;
                elseif n+1==map(k)
                    map(k)=n;
                end
            end
        end
    end
end

Y=code_Frqs;
%將碼表的每個元素都翻轉
%toc;