霍夫曼编码的matlab实现

霍夫曼编码的matlab实现一、程序代码：%取得信源概率矩阵,并进行合法性判断clear;P=input('请输入信源概率向量P=');N=length(P);forcomponent=1:1:Nif(P(component)0)error('信源概率不能小于0');endendif((sum(P)-1)0.0001)error('信源概率之和必须为1');end%建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯,从而得出对应的编码Q=PIndex=zeros(N-1,N);%初始化Indexfori=1:N-1[Q,L]=sort(Q);Index(i,:)=[L(1:N-i+1),zeros(1,i-1)];G(i,:)=Q;Q=[Q(1)+Q(2),Q(3:N),1];%将Q中概率最小的两个元素合并，元素不足的地方补1end%根据以上建立的Index矩阵，进行回溯，获取信源编码fori=1:N-1Char(i,:)=blanks(N*N);%初始化一个由空格符组成的字符矩阵N*N,用于存放编码end%从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一行进行编码Char(N-1,N)='0';%G中的N-1行即最后一行第一个元素赋为0，存到Char中N-1行的N列位置Char(N-1,2*N)='1';%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置%以下从G的倒数第二行开始向前编码fori=2:N-1Char(N-i,1:N-1)=Char(N-i+1,N*(find(Index(N-i+1,:)==1))-(N-2):N*(find(Index(N-i+1,:)==1)));%将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置Char(N-i,N)='0';%然后在当前行的第一个编码位置末尾填入'0'Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1);%将G后一行中索引为1的编码码字填入到当前行的第二个编码位置Char(N-i,2*N)='1';%然后在当前行的第二个编码位置末尾填入'1'forj=1:i-1%内循环作用：将Index后一行中索引不为1处的编码按照左右顺序填入当前行的第3个位置开始的地方,最后计算到Index的首行为止Char(N-i,(j+1)*N+1:(j+2)*N)=Char(N-i+1,N*(find(Index(N-i+1,:)==j+1)-1)+1:N*find(Index(N-i+1,:)==j+1));endend%Char中第一行的编码结果就是所需的Huffman编码输出，通过Index中第一行索引将编码对应到相应概率的信源符号上。fori=1:NResult(i,1:N)=Char(1,N*(find(Index(1,:)==i)-1)+1:find(Index(1,:)==i)*N);end%打印编码结果String='信源概率及其对应的Huffman编码如下';disp(String);disp(P);disp(Result);二、运行结果：以例题3-2信源[0.40.20.20.10.1]为例：运行：HuffmanEncode结果：信源概率及其对应的Huffman编码如下0.40000.20000.20000.10000.100001111011001101可知，程序已完成了Huffman编码的功能，但与书中的结果不一致，验证了霍夫曼编码是不唯一的.因为：信源符号合并中遇到最小概率相同的情况时可任意选择来做合并；在码树分配编码码字的时候1和0的位置可以是任意的。