Huffman編碼用MTLAB的實現(xiàn)及編碼注釋

aixuexidewau1 2019-05-09

展開全文

一、實驗內(nèi)容

1、用Matlab實現(xiàn)Huffman編碼算法程序；

2、要求程序輸出顯示所有的碼字以及編碼效率；

3、設(shè)計簡單的輸入界面（可以是簡單的文字提示信息），程序運行時提示用戶輸入代表信源符號概率的向量；要對用戶輸入的概率向量進(jìn)行合法性檢查。

二、實驗原理

1、二進(jìn)制Huffman編碼的基本原理及算法

(1) 把信源符號集中的所有符號按概率從大到小排隊。

(2) 取概率最小的兩個符號作為兩片葉子合并（縮減）到一個節(jié)點。

(3) 視此節(jié)點為新符號，其概率等于被合并（縮減）的兩個概率之和，參與概率排隊。

(4) 重復(fù)(2)(3)兩步驟，直至全部符號都被合并（縮減）到根。

(5) 從根出發(fā)，對各分枝標(biāo)記0和1。從根到葉的路徑就給出了各個碼字的編碼和碼長。

2、程序設(shè)計的原理

(1)程序的輸入：以一維數(shù)組的形式輸入要進(jìn)行huffman編碼的信源符號的概率，在運行該程序前，顯示文字提示信息，提示所要輸入的概率矢量；然后對輸入的概率矢量進(jìn)行合法性判斷，原則為：如果概率矢量中存在小于0的項，則輸入不合法，提示重新輸入；如果概率矢量的求和大于1，則輸入也不合法，提示重新輸入。

（2）huffman編碼具體實現(xiàn)原理：

1>在輸入的概率矩陣p正確的前提條件下,對p進(jìn)行排序，并用矩陣L記錄p排序之前各元素的順序，然后將排序后的概率數(shù)組p的前兩項，即概率最小的兩個數(shù)加和，得到新的一組概率序列，重復(fù)以上過程，最后得到一個記錄概率加和過程的矩陣p以及每次排序之前概率順序的矩陣a。

2>新生成一個n-1行n列，并且每個元素含有n個字符的空白矩陣，然后進(jìn)行huffman編碼：

將c矩陣的第n-1行的第一和第二個元素分別令為0和1（表示在編碼時，根節(jié)點之下的概率較小的元素后補(bǔ)0，概率較大的元素后補(bǔ)1，后面的編碼都遵守這個原則）

然后對n-i-1的第一、二個元素進(jìn)行編碼，首先在矩陣a中第n-i行找到值為1所在的位置，然后在c矩陣中第n-i行中找到對應(yīng)位置的編碼（該編碼即為第n-i-1行第一、二個元素的根節(jié)點），則矩陣c的第n-i行的第一、二個元素的n-1的字符為以上求得的編碼值，根據(jù)之前的規(guī)則，第一個元素最后補(bǔ)0，第二個元素最后補(bǔ)1，則完成該行的第一二個元素的編碼，

最后將該行的其他元素按照“矩陣c中第n-i行第j+1列的值等于對應(yīng)于a矩陣中第n-i+1行中值為j+1的前面一個元素的位置在c矩陣中的編碼值”的原則進(jìn)行賦值，重復(fù)以上過程即可完成huffman編碼。

3>計算信源熵和平均碼長，其比值即為編碼密碼效率。

n-i行的第一、二個元素的n-1的字符為以上求得的編碼值，根據(jù)之前的規(guī)則，第一個元素最后補(bǔ)0，第二個元素最后補(bǔ)1，則完成該行的第一二個元素的編碼，

P=input('please input a nuber:'); %提示輸入界面
  if(find(P<0))
        disp('The probabilities in huffman can not less than 0!');  
        P=input('please input a number:') 
  end 
  if  abs(sum(P))>1
      disp('The sum of the probabilities in huffman can more than 1!');
      P=input('please input a number:') 
  end 
 [w,k]=Huffman(P);
 disp('碼字');
 disp(w)
 disp('碼長');
 disp(k)

調(diào)用函數(shù)：

function [a,b]=Huffman(P)
P=sort(P)
A=P;
B=[];
i=1;
LL=length(P);
L=LL;
B(1,:)=P;
while(L>2)
      i=i+1;
      B(i,1)=A(1)+A(2);
      C(i-1)=B(i,1);
  for j=2:(L-1)
     B(i,j)=A(j+1);
  end
 L=L-1;
 B(i,1:L)=sort(B(i,1:L));
 A=B(i,1:L);
end
K=zeros(i,LL);
K(i,1:2)=1;
for ll=1:i
    for n=1:LL
W(ll,n)={'0'};
    end
end
W(i,1)={'1'};
 
for m=(i-1):-1:1
    BB=B(m,1)+B(m,2);
     BBB=find(B(m+1,:)==BB);
     BBB=BBB(1);
     
        W(m,1:2)=W(m+1,BBB);
        K(m,1:2)=K(m+1,BBB);  
        W(m,1)=strcat(W(m,1),'1');
        W(m,2)=strcat(W(m,2),'0');
        K(m,1:2)=K(m,1:2)+1;
        uu=zeros(1,LL);
        uu(1)=BBB;
        y=1;
         for n=3:(LL+1-m)
              fd3=find(B(m,n)==B(m+1,:));
              for pp=1:length(fd3)
                  kk=isempty(find(uu==fd3(pp)));
                 if(kk==1)
                     y=y+1;                   
                     fd3=fd3(pp);
                     uu(y)=fd3;
                     break;
                 end
              end
                  W(m,n)=W(m+1,fd3);
                  K(m,n)=K(m+1,fd3);  
         end
end
a=W(1,:);
b=K(1,:);

結(jié)果顯示：

please input a nuber:[0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.04]

P =
    0.0400    0.0500    0.0600    0.0700    0.1000    0.1000    0.1800    0.4000
碼字
    '00011'    '00010'    '0101'    '0100'    '0000'    '011'    '001'    '1'
碼長
     5     5     4     4     4     3     3     1