霍夫曼編碼(含源程序)

1、NAhfJG UNIVERSITY OF SCIENCE & TECHNOLOGY多媒體技術(shù)基礎(chǔ)實驗報告霍夫曼編碼學(xué)院：電子工程與光電技術(shù)學(xué)院專業(yè)：電子信息工程姓名：學(xué)號：任課老師：康其桔實驗時間：、實驗內(nèi)容及要求1、使用Matlab編程實現(xiàn)霍夫曼編碼2、通過鍵盤輸入字符串3、在屏幕上顯示編碼結(jié)果、實驗原理霍夫曼編碼是霍夫曼在1952年提出和描述的“從下到上”的嫡編碼方法。根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計壓縮編碼方法。這些元素（如字母）出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少。其基本步驟為：將壓縮的各字符的出現(xiàn)概率按減少（或增加）的順序進(jìn)行排列。將兩個最小的概率進(jìn)行組合

2、相加得到一個新概率將這一新概率與其它概率一起繼續(xù)執(zhí)行1和2的操作直至最后概率為1.0。(5)對每對組合中的概率較大者指定為1,較小者指定為00畫出由每個信源符號概率到1.0處的路徑記下路徑的1和0。對每個信源符號由從右到左寫出1/0序列，對概率較高的標(biāo)1,對概率較低的 標(biāo)0（或?qū)Ω怕瘦^高的標(biāo)0，對概率較低的標(biāo)1）,就得到了對應(yīng)的Huffman碼。下面舉個例子來說明霍夫曼編碼的具體過程。設(shè)需要編碼的信息為: 現(xiàn)的次數(shù)分別為B（10次）、 概率為 B（10/30）、A（8/30）BACDEBACDEBACDEBADEBAEBA隗BABB, 字符出 A（8次）、C（3次）、D（4次）、E（5次）。各

3、個字符出現(xiàn)的 、E（5/30）、D（4/30）、C（3/30）?；舴蚵幋a的過程如下：B(10/30)A(8/30)E(5/30)D(4/30)C(3/30)00_1 p07/301 18/30012/30B:11A:1030/30E:00D:011C:010霍夫曼編碼后平均碼長為 2 (10/30 8/30 5/30) 3 (4 /30 3/30) 2.23b 。而信源嫡H 2.19b。由此，我們可以看出，霍夫曼編碼結(jié)果已經(jīng)很接近理想 信源嫡。三、設(shè)計方案設(shè)計的流程圖如下:四、各模塊設(shè)計（一）讀入字符串并去除空格在Matalb中使用語句inputstring=input（'請輸入需要

4、編碼的字符：，'s'）,輸入的字符串存入char型數(shù)組inputstring 中。去除空格的思想為：輸出的inputletters數(shù)組存儲的是輸入字符串去除空格后的字符集的ASClfi,如果需要顯示字符需要用語句：disp(char(inputletters) 。這一部分代碼如下： inputstring=input('請輸入需要編碼的字符：，'s' ); %輸入字符并存儲spacenumber=0;用儲空格數(shù)目for i=1:length(inputstring) if abs(inputstring(i)=32spacenumber=spacenum

5、ber+1; continueelseinputletters(i-spacenumber尸inputstring(i); endenddisp('去除空格后字符為：'，char(inputletters)（二）統(tǒng)計字符種類及概率統(tǒng)計字符的種類，需要去除輸入字符中的重復(fù)字符，并存入數(shù)組letters中,其基本流程圖如下：m>length(inputletters)?輸出矩陣letters這一部分的程序如下：letters(1)=inputletters(1);for m=2:length(inputletters)repeatn=0;%E義一個數(shù)記錄是否有重復(fù)for n=

6、1:length(letters)if letters(n)=inputletters(m)repeatn=repeatn+1;endendif repeatn=0letters(length(letters)+1)=inputletters(m); endend概率的統(tǒng)計即是統(tǒng)計letters中每個元素在inputletters出現(xiàn)的次數(shù)，除以總 次數(shù)即可得到每個字符出現(xiàn)的概率。概率統(tǒng)計的程序如下：% 十算重復(fù)次數(shù)for p=1:length(letters)repeatn=0;for q=1:length(inputletters)if letters(p)=inputletters(q)

7、repeatn=repeatn+1;endendletterp(p)=repeatn/length(inputletters);end對得到概率letterp 進(jìn)行降序排序得到huffmanprob ， 并使字符集與概率相對應(yīng)生成字符集huffamnletters。這一過程主要是為了方便輸出字符集的輸出。這一部分的程序如下：huffmanprob,sort_index = sort(letterp);%用來霍夫曼編碼的概率huffmanprob=(fliplr(huffmanprob)'sort_index=fliplr(sort_index);for i=1:length(huffm

8、anprob)huffmanletters(i)=letters(sort_index(i);%用來霍夫曼編碼的字符集enddisp( ' 字符及概率')for i= 1:length(huffmanletters)fprintf( '字符：-4s概率：5.4fn' ,char(huffmanletters(i),huffmanprob(i)end（三）霍夫曼編碼根據(jù)實驗原理，在使用Matlab編程實現(xiàn)霍夫曼編碼的過程中，需要定義一個 元胞數(shù)組huffmantabel來存儲霍夫曼碼表。這個元胞數(shù)組的長度與huffman -letters 中字符相對應(yīng)。同時還需定

9、義一個元胞數(shù)組numorder來存儲每個字符的概率在原 概率矩陣中的位置。其基本流程圖如下：while length(numorder)>1temp,ind=sort(huffmanprob);pminorder=numorderind(1);pmin=huffmanprob(ind(1);pnminorder=numorderind(2);pnmin=huffmanprob(ind(2);for i=1:length(pminorder)huffmantabelpminorder(i)=1,huffmantabelpminorder(i);endfor j=1:length(pnmin

10、order)huffmantabelpnminorder(j)=0,huffmantabelpnminorder(j);endnumorder(ind(1:2)=;numorderlength(numorder)+1=pminorder,pnminorder;huffmanprob(ind(1:2)=;huffmanprob(length(huffmanprob)+1)=pmin+pnmin;end(四)霍夫曼解碼在進(jìn)行霍夫曼解碼的過程中，需要將霍夫曼碼序列中的元素與霍夫曼碼表中 的元素進(jìn)行比較，若一樣則輸出相對應(yīng)的字符。由于考慮到霍夫曼碼長可變，我 們可以歸納每個霍夫曼碼的特點，每個霍夫曼碼

11、可以用其碼長以及十進(jìn)制數(shù)值唯 一表示，將其十進(jìn)制及碼長存入一個新的元胞數(shù)組huffmandec中，將霍夫曼碼元中的一位位取出，算出其十進(jìn)制對應(yīng)的值tempsum及二進(jìn)制長度i存入一個數(shù)組A 中，使用語句 c2=find(cellfun(t)all(A(:)=t(:),huffmandec);即可找到元胞數(shù)組huffmandec中與數(shù)組At目同的數(shù)組的位置。利用這個次序即可找到對應(yīng)的 huffmanletters 數(shù)組中的字符刪除后的數(shù)組重新賦值給 huffmanletter- s,將這個字符存入decodeletters,將剛剛統(tǒng)計的i個二進(jìn)制刪除并用語句isequal(decodelette

12、rs,inputletters)判斷解碼輸出的結(jié)果與輸入是否相同。將二進(jìn)制霍夫曼碼表轉(zhuǎn)變?yōu)槭M(jìn)制霍夫曼碼表并與長度一起存入元胞數(shù)組 的語句如下：for i=1:length(huffmanletters)temparray=huffmantabeli;%temparray 是一個臨時的矩陣huffmandeci=bin2dec(num2str(temparray),length(temparray);湘霍夫曼碼表的十進(jìn)制值及長度形成霍夫曼碼的唯一標(biāo)志end實現(xiàn)霍夫曼解碼的流程圖如下：這一過程所對應(yīng)的Matlab 源程序為：decodeletters=;while isempty(huffman

13、codep)=0 tempsum=0;for i=1:length(huffmancodep)tempsum=tempsum*2+huffmancodep(i);A=tempsum i;c2=find(cellfun(t)all(A(:)=t(:),huffmandec);if isempty(c2)=0decodeletters=decodeletters huffmanletters(c2(1);huffmancodep(1:i)=;break ;endendendif isequal(decodeletters,inputletters)=1disp( ' 經(jīng)比較解碼輸出結(jié)果與輸

14、入相同' )end在完成霍夫曼解碼之后經(jīng)過簡單的計算即可求出信源熵，壓縮比， 以及平均碼長。五、結(jié)果演示以書本例2.2為例，運行程序，輸入A( 15個) 、 B(7個) 、 C( 6個) 、 D(6個) 、E( 5 個) ，理論結(jié)果為A( 0)B( 1 1 1)C( 1 1 0)D( 1 0 1)E( 1 0 0)壓縮比為：1.34信源熵為2.1857平均碼長為：2.2308而經(jīng)過程序計算的結(jié)果為：請輸入需要編利的字符：AA.4A4AAAAAAAA.UBEBBBBBCCCCCCDMDBDEEEEE 去呢空格后字符為；AAAAAAAAAAAAAAAB即即即CCCCCCDDDDDDEEEE

15、E!VI字符：A «S¥： C.3S46字符：B 概率：0.1躺字符；D 概率：0"33s字將工。概率：上15相字籽：E 概率：0.12的霍夫曼碼表字母：3 霍夫曼招；1字母:E 霍夫曼碼；0 Q 0李母：D 霍夫量狷：01 0字母二C 霍夫曼碼：C 0 1字母；E 霍夫量碼；0 1 1史上息m! !JMV1 M! (*IBV!n任大H X111L1110ooa000010Q100oioaioo1111111100 0 0 0 010 0 10 i a o i a0 C 0 00 10 10 1100 0 0 00 0 100 0 10110 1霍夫量露碼AAAA

16、AAAAAAAAAA二EEEEE BECCCCCCBDDDDDE EE E經(jīng)比較解碼輸出結(jié)果與輸入相同 壓縮比/信源崛/平均碼長-壓縮比:1. 3448信源嫡：2.1853平均陰喉：2. 2308經(jīng)比較，所得結(jié)果與例2.2結(jié)果相同，即程序運行結(jié)果正確六、源程序%代碼文件：myhuffman.m哨的：從鍵盤輸入字符集使用huffman編碼并解碼%更改記錄% Date Programmer Description of change% = =% 5/11Original code%重要變量定義：%inputstring: 輸入字符串%inputletters:除去空格后的字符串存入的數(shù)組%huff

17、manletters:用來霍夫曼編碼的字符集%huffmanprob:字符集相對應(yīng)的概率%huffmantabel:霍夫曼碼表，與字符集順序?qū)?yīng)%huffmancode:霍夫曼編碼結(jié)果%decodeletters: 霍夫曼解碼輸出的字符集%compratio:壓縮比% 開始編碼 clcclear allinputstring=input( ,請輸入需要編碼的字符:','s' ); %輸入字符并存儲spacenumber=0;篩儲空格數(shù)目%=除空格=for i=1:length(inputstring)if abs(inputstring(i)=32spacenumber

18、=spacenumber+1;continueelseinputletters(i-spacenumber)=inputstring(i);endenddisp('去除空格后字符為：'，char(inputletters)%fprintf('去除空格后字符：%s',char(letters)%=統(tǒng)計輸入字符種類=letters(1)=inputletters(1);for m=2:length(inputletters)repeatn=0;%t義一個數(shù)記錄是否有重復(fù)for n=1:length(letters)if letters(n)=inputletters

19、(m)repeatn=repeatn+1;endendif repeatn=0letters(length(letters)+1)=inputletters(m);endend%disp('輸入無重復(fù)字符為：',char(letters)%=統(tǒng)計率=:for p=1:length(letters)repeatn=0;%計算重復(fù)次數(shù)for q=1:length(inputletters)if letters(p)=inputletters(q) repeatn=repeatn+1;endletterp(p)=repeatn/length(inputletters); end%=排

20、序并對應(yīng)=huffmanprob,sort_index = sort(letterp);%ffl 來霍夫曼編碼的概率huffmanprob=(fliplr(huffmanprob),; sort_index=fliplr(sort_index); for i=1:length(huffmanprob)huffmanletters(i)=letters(sort_index(i);%來霍夫曼編碼的字符集end%=輸出字符及概率=disp(' 字符及概率 ) for i= 1:length(huffmanletters)fprintf( '字符：-4s概率：5.4fn' ,

21、char(huffmanletters(i),huffmanprob(i) end%=開始霍夫曼編碼=huffmantabel=cell(1,length(huffmanletters);numorder_temp=1:length(huffmanletters);numorder=num2cell(numorder_temp);while length(numorder)>1temp,ind=sort(huffmanprob);原概率中位置pminorder=numorderind(1);置，此位置對應(yīng)編碼字符pmin=huffmanprob(ind(1);pnminorder=num

22、orderind(2);pnmin=huffmanprob(ind(2);for i=1:length(pminorder)%定義元胞數(shù)組用來存儲 huffman碼表%等1- 這一系列數(shù)轉(zhuǎn)變?yōu)樵麛?shù)組嘲E序，不需要結(jié)果，只需要最小概率在%艮據(jù)ind得出最小概率元胞數(shù)組對應(yīng)位huffmantabelpminorder(i)=1,huffmantabelpminorder(i); endfor j=1:length(pnminorder)huffmantabelpnminorder(j)=0,huffmantabelpnminorder(j); endnumorder(ind(1:2)=口；num

23、orderlength(numorder)+1=pminorder,pnminorder;huffmanprob(ind(1:2)=口；huffmanprob(length(huffmanprob)+1)=pmin+pnmin;end%=輸出霍夫曼碼表=disp(' 霍夫曼碼表 ) for i=1:length(huffma nletters)%fprintf(' 字符：-4s 概率：%fn',char(huffmanletters(i),num2str(huffmantabeli)disp('字母：char(huffmanletters(i) '

24、9;'霍夫曼碼：'num2str(huffmantabeli) end%=成霍夫曼碼=disp(' 霍夫曼碼')huffmancode二口；%huffmancode 用來存儲 huffman 碼for i=1:length(inputletters)c1=find(huffmanletters=inputletters(i)；huffmancode=huffmancode,huffmantabelc1(1);endfor i=1:ceil(length(huffmancode)/10)disp(num2str(huffmancode(i-1)*20+1:min(i*20,length(huffmancode)end%=霍夫曼解碼=huffmancodep=huffmancode;%1十進(jìn)制霍夫曼碼組元胞數(shù)組元素變成十進(jìn)制數(shù)組方便解碼for i=1:le