huffman.m

基于matlab的图像或者序列的哈夫曼编码及解码程序-Matlab-based image or sequence of Huffman coding and decoding procedures

%-------------------------------------------------
%函数名称：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;