【文章內(nèi)容簡介】 兩個值作為葉子節(jié)點構(gòu)成一棵二叉樹，值較 大的葉子節(jié)點在左，兩個葉子節(jié)點對應的頻率之和作為根節(jié)點。把原排列中最小的兩個節(jié)點刪除，新的根節(jié)點插入排列保持大小從左到右的排列順序不變；重復執(zhí)行 2），直到最后得到值為 1 的根節(jié)點。得到一棵哈夫曼 樹，如下圖所示： 圖 哈夫曼編碼樹 在得到的 哈夫曼 樹上左分支標記 1，右分支標記 0，所有的字符根據(jù)其頻率標記到對應的葉子節(jié)點上，從根節(jié)點到葉子節(jié)點路徑上遇到的 0、 1 字符串即為對應葉子節(jié)點所在字符的武漢理工大學《 信息處理課群綜合訓練與設(shè)計 》 5 編碼。 a、 b、 c、 d、 e、 f、 g 七個字符的 哈夫曼 編碼分別是： 000 0000、 001 1 00010，可以看到 ,符號只能出現(xiàn)在樹葉上 ,任何一個字符的路徑都不會是另一字符路徑的前綴路徑。 哈夫曼編碼的缺點 哈夫曼編碼雖然是最佳編碼，但 存在一些缺點 ，具體如下 ： （ 1）對于過短的文件進行編碼，意義不大。因為存儲哈夫曼樹的信息需要一定的存儲空間； （ 2）利用哈夫曼編碼，若用于通信網(wǎng)絡(luò)，會引起較大的延時； （ 3）對較大文件進行編碼，會出現(xiàn)頻繁的磁盤讀寫訪問，降低了數(shù)據(jù)編碼的速度。 武漢理工大學《 信息處理課群綜合訓練與設(shè)計 》 6 3 基于哈夫曼編碼的圖像編解碼 系統(tǒng)的程序設(shè)計 分塊程序設(shè)計 分析 （ 1）首先，尋找出 現(xiàn)的所有元素，接著計算各元素出現(xiàn)的概率，并將元素按照出現(xiàn)概率排列，產(chǎn)生碼字。部分程序如下： function [huffcode， info]=codeing（ vector） p=probability（ vector）； %計算各元素出現(xiàn)的概率 simbols=find（ p）； %尋找出現(xiàn)的所有元素 p=p（ simbols）； [p， sortindex]=sort（ p）； %概率從小到大排列 simbols=simbols（ sortindex）； %將元素按照出現(xiàn)概率排列 len=length（ simbols） ； %產(chǎn)生碼字 （ 2）把出現(xiàn)的元素概率最小的兩個相加合并成新的概率，與剩余的概率組成新的概率集合，直到剩下最后兩個概率。部分程序如下： while length（ p） 1； index1=simbols_index{1}； index2=simbols_index{2}； codeword_tmp （ index1） =addnode （ codeword_ tmp（ index1）， uint8（ 0））； codeword_tmp （ index2） =addnode （ codeword_ tmp（ index2）， uint8（ 1））； p=[sum（ p（ 1:2）） p（ 3:end） ]； simbols_index =[{[index1 index2]} simbols_index（ 3:end） ]； [p， sortindex]=sort（ p）； %將數(shù)據(jù)重新排列 simbols_index=simbols_index（ sortindex）； （ 3）從最后一步開始反向進行分配碼字，對于每次相加的兩個概率，給大的賦 “0”，小的賦 “1”，存儲到一個稀疏矩陣，最后寫出 01 序列的哈夫曼編碼。部分程序如下： 武漢理工大學《 信息處理課群綜合訓練與設(shè)計 》 7 pad=8mod（ len， 8）； if pad0； string=[string uint8（ zeros（ 1， pad）） ]； end cols=length（ string） /8； %計算壓縮后的向量 string=reshape（ string， 8， cols）； weights=2.^（ 0:7）； huffcode =uint8 （ weights*double （ string））； % 編碼字符串湊成一個 %字節(jié)一個字節(jié)存在 huffcode codeword=codeword（ simbols）； %保存實際有出現(xiàn)元素對應的碼字 （ 4） 把整字節(jié)存儲的 huffcode 一位一位取出，轉(zhuǎn)為字符串，去掉原來為湊整字節(jié)數(shù)所添加的零進行解碼。部分解碼程序如下： vector=zeros（ 1， ， 39。uint839。）； %解碼 vectorindex=1； codeindex=1； code=0； for index=1:len； code=bitset（ code， codeindex， string（ index））； codeindex=codeindex+1； byte = （ bitset （ code， codeindex））； %從碼字表中讀出對應元素 if byte0； vector（ vectorindex） =byte1； codeindex=1； code=0； vectorindex=vectorindex+1； （ 5）顯示編碼的壓縮信息（如壓縮率、最大碼長等），部分程序如下所示： whos data huffcode huffdecode %顯示壓縮效果 fprintf（ 39。pad=%d\n39。， ）； %=為湊整字節(jié)數(shù)，編碼字符 武漢理工大學《 信息處理課群綜合訓練與設(shè)計 》 8 串最后添加零的位數(shù) fprintf （ 39。ratio=%f\n39。， ）； %=壓縮率 fprintf （ 39。maxcodelen=%d\n39。， ）； %=最大碼長 主程序 系統(tǒng)設(shè)計的完整主程序如下 %%%%%%%%%%%%%%%%%%%%%%%%%主程序 %%%%%%%%%%%%%%%%%%%%%%%%%%% % 信息處理課群綜合訓練與設(shè)計 基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計及實現(xiàn) %信息 SY1001 班 王鳴 0121009320403 clc clear cd。 X=imread(39。39。)。 data=uint8(X)。 [zipped,info]=huffencode(data)。 unzipped=huffdecode(zipped,info)。 subplot(121)。imshow(data)。title(39。原始圖像 39。) subplot(122)。imshow(unzipped)。title(39。解碼后的圖像 39。) whos data unzipped zipped fprintf(39。pad=%d\n39。,)。 %=為湊整字節(jié)數(shù)，編碼字符串最后添加零的位數(shù) fprintf(39。ratio=%f\n39。,)。 %=壓縮率 fprintf(39。maxcodelen=%d\n39。,)。%=最大碼長 程序函數(shù) 編碼函數(shù) 主程序中使用的函數(shù)代碼如下 武漢理工大學《 信息處理課群綜合訓練與設(shè)計 》 9 %%%%%%%%%%%%%%%%%%%%%%%%%%編碼 函數(shù) %%%%%%%%%%%%%%%%%%%%%%%%%% % 信息處理課群綜合訓練與設(shè)計 基于哈夫 曼編碼的圖像編解碼系統(tǒng)設(shè)計及實現(xiàn) %信息 SY1001 班 王鳴 0121009320403 %huffencode 函數(shù)對輸入矩陣 vector 進行 huffman 編碼，返回編碼后的向量及相關(guān)信息 function [zipped,info]= huffencode(vector) if ~isa(vector,39。uint839。) eror(39。input argument must be a uint8 vector39。)。 end