靜態(tài)哈夫曼編碼的原理及應(yīng)用

1、 收稿日期 :20090118 作者簡介 :女 ,1972年生 , 講師 , 張家口市 ,075024靜態(tài)哈夫曼編碼的原理及應(yīng)用康洪波河北建筑工程學(xué)院摘 要 介紹的哈夫曼編碼就是一種無損壓縮編碼 , 應(yīng)用非常廣泛 .關(guān)鍵詞 哈夫曼編碼 ; 數(shù)據(jù)壓縮中圖分類號 TP3 哈夫曼編碼是上個世紀(jì)五十年代由哈夫曼教授研制開發(fā)的 , 它借助了數(shù)據(jù)結(jié)構(gòu)當(dāng)中的樹型結(jié)構(gòu) , 在 哈夫曼算法的支持下構(gòu)造出一棵最優(yōu)二叉樹 , 我們把這類樹命名為哈夫曼樹 . 因此 , 準(zhǔn)確地說 , 哈夫曼編 碼是在哈夫曼樹的基礎(chǔ)之上構(gòu)造出來的一種編碼形式 , .那么 , ?眾所周知 , 在計算機(jī)當(dāng)中 , , 個字節(jié)來表達(dá) , 而一個

2、漢字就要用兩個字節(jié) , 形式稱為定長編碼 . 以西文為例 , :I am a teacher. 就需要 15個字節(jié) , 也就是 . 它根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最 短的編碼 . , 它的編碼就相應(yīng)的短 , 如果一個字符 在一段文檔當(dāng)中出現(xiàn)的次數(shù)少 , 它的編碼就相應(yīng)的長 . 當(dāng)編碼中 , 各碼字的長度嚴(yán)格按照對應(yīng)符號出現(xiàn) 的概率大小進(jìn)行逆序排列時 , 則編碼的平均長度是最小的 . 這就是哈夫曼編碼實現(xiàn)數(shù)據(jù)壓縮的基本原理 .要想得到一段數(shù)據(jù)的哈夫曼編碼 , 需要用到三個步驟 :第一步 :掃描需編碼的數(shù)據(jù) , 統(tǒng)計原數(shù)據(jù)中各 字符出現(xiàn)的概率 . 第二步 :利用得到的概率值創(chuàng)建哈夫曼樹 . 第

3、三步 :對哈夫曼樹進(jìn)行編碼 , 并把編碼后 得到的碼字存儲起來 .我們依然以 I am a teacher. 這句話為例 , 來創(chuàng)建屬于它的哈夫曼編碼 .首先 , 掃描這句話可以得出每一個字符出現(xiàn)的概率 , 并把它記錄下來 , 形成一個集合 , 為計算方便 , 我們以近似整數(shù)值來代替概率值 , 如表 1所示 .表 1字符I 空格 a m t e c h r . 總字符數(shù) 次數(shù)133112111115概率0106701201201067010670113010670106701067010671概率近似整數(shù)值 7191977137777100 其次 , 利用這些概率值構(gòu)造哈夫曼樹 .哈夫曼樹是在

4、哈夫曼算法的支持下建構(gòu)起來的 , 它的具體實現(xiàn)過程如下 :首先從的概率集合 7191977137777中選擇概率最小的兩個如 r 及 1連同這兩個字符的概率之和 14, 構(gòu)成一棵子樹 , 并 將這兩個字符的概率之和放回集合當(dāng)中 , 構(gòu)成一個新的集合 7191977137714, 然后再在這個集合 中取概率最小的兩個數(shù)值 , 以及概率之和構(gòu)成子樹 , 生成新的集合 7191977131414, 依照這樣的規(guī) 則 , 就可以建立起一棵哈夫曼樹 , 如下圖所示 .通過觀察可以發(fā)現(xiàn) , 這棵哈夫曼樹的葉子結(jié)點全部由原文檔中的數(shù)據(jù)字符構(gòu)成 . 其他結(jié)點都有兩個 第 27卷 第 1期 2009年 3月 河

5、 北 建 筑 工 程 學(xué) 院 學(xué) 報 JOURNAL OF HEBEI INSTITUTE OF ARCHITECTURE AND CIVIL ENGINEERING V ol 127No 11March 2009 后繼結(jié)點 , 把每一個結(jié)點的左分支標(biāo)注為 1, 而把每一個結(jié)點的右分支標(biāo)注為 0, 從根結(jié)點開始到需要編 碼字符為至 , 所有分支上標(biāo)注的數(shù)據(jù)將構(gòu)成一個集合 , 這集合就是該字符的哈夫曼編碼 , 例如 e 的編碼 就是 (1,1,1 而 h 的編碼就是 (1,0,0,0 , 這就完成了哈夫曼編碼的第三步 . 也就得到了 I am a teacher. 這句話的哈夫曼編碼如下 : I

6、 :000 空格 :101 a :01 m :0011 t :0010 e :111 c :1001r I 空格 a m 空格 a 空格 t a h e h r .48個字符 , 和 ASCII 碼 120個字符相比 , , 而我們構(gòu)造哈夫曼樹的過程是嚴(yán)格按照 , 這就保證了文檔當(dāng)中出現(xiàn)的次數(shù)多的字符出現(xiàn)在了整棵樹的相對高一些 的層次上 , 編碼就相應(yīng)的短 , 而在文檔當(dāng)中出現(xiàn)的次數(shù)少的字符出現(xiàn)在了整棵樹的最下層 , 它的編碼就 相應(yīng)的長 . 那么這組編碼能否實現(xiàn)準(zhǔn)確的解碼呢 ?我們再來觀察一組字符 :a b c d , 它們的編碼分別為 :0,10,101,11, 如果我們得到的壓縮數(shù)據(jù)為

7、1010時 , 那么在解壓縮時就會存在兩種翻譯的可能 , 一種為 bb , 另一種為 ca , 為什么會出現(xiàn)這樣的現(xiàn)象 呢 ? 通過觀察我們發(fā)現(xiàn) , 字符 b 的編碼為 10, 而字符 c 的編碼為 101,b 的編碼恰好是 c 的編碼的前兩 位 , 就造成了 b 的編碼添加一位就有可能成為 c , 這就增加了解壓縮的過程中誤碼的可能 . 因為定長編 碼已經(jīng)用相同的位數(shù)這個條件保證了任一個字符的編碼都不會成為其它編碼的前綴 , 所以這種情況只 會出現(xiàn)在變長編碼當(dāng)中 , 要想避免這種情況 , 我們就必須用一個條件來制約定長編碼 , 這個條件就是要 想成為壓縮編碼 , 變長編碼就必須是前綴編碼 .

8、什么是前綴編碼呢 ? 所謂的前綴編碼就是任何一個字符的編碼都不能是另一個字符編碼的前綴 . 那么哈夫曼編碼是否是前綴編碼呢 ? 觀察 a 、 b 、 c 、 d 構(gòu)成的編碼樹 , 可以發(fā)現(xiàn) b 之所以成為 c 的前綴 , 是 因為在這棵樹上 ,b 成為了 c 的父結(jié)點 , 從在哈夫曼樹當(dāng)中 , 原文檔中的數(shù)據(jù)字符全都分布在這棵哈夫 曼樹的葉子位置 , 從而保證了哈夫曼編碼當(dāng)中的任何一個字符的編碼都不能是另一個字符編碼的前綴 . 也就是說哈夫曼編碼是一種前綴編碼 , 也就保證了解壓縮過程當(dāng)中譯碼的準(zhǔn)確性 .哈夫曼編碼的解壓縮過程也相對簡單 , 就是將編碼嚴(yán)格按照哈夫曼樹進(jìn)行翻譯就可以了 , 例如

9、遇到000, 就可以順著哈夫曼樹找到 I , 遇到 101就可以順著哈夫曼樹找到空格 , 以此類推 , 我們就可以很順利的找到原來所有的字符 .哈夫曼編碼是一種一致性編碼 , 有著非常廣泛的應(yīng)用 , 例如在J PEG 文件中 , 就應(yīng)用了哈夫曼編碼來實現(xiàn)最后一步的壓縮 ; 在數(shù)字電視大力發(fā)展的今天 , 哈夫曼編碼成為了視頻信號的主要壓縮方式 .應(yīng)當(dāng)說 , 哈夫曼編碼出現(xiàn) , 結(jié)束了熵編碼不能實現(xiàn)最短編碼的歷史 ,也使哈夫曼編碼成為一種非常重要的無損編碼 .(下轉(zhuǎn)第 144頁 621 河 北 建 筑 工 程 學(xué) 院 學(xué) 報 第 27卷現(xiàn)代化管理進(jìn)程 .綜上所述 , 高校教學(xué)檔案管理工作是學(xué)校教學(xué)

10、管理工作的重要組成部分 . 加強(qiáng)教學(xué)檔案管理工作是 強(qiáng)化教學(xué)管理的需要 , 是深化教學(xué)改革的需要 , 也是提高教學(xué)質(zhì)量的需要 . 可以想見 , 以計算機(jī)及其網(wǎng)絡(luò) 作為工具或基本工作環(huán)境自動或半自動地代替人來從事檔案管理工作是時代發(fā)展的需要 . 它對于提高 教學(xué)檔案的保存和利用有著不可低估的作用 . 隨著高?？萍冀逃W(wǎng)的興起和普及 , 必將帶動檔案的全面 信息化 .On the Computer Management of T eaching Files in Colleges Zhong Xi aoch u n 1, Zh u Y i ngli ng 1, Dai Cha ngm i ng 1

11、, L i J i a n h u a 2, D u Ch u n mei 111Hebei Institute of Architecture civil Engineering21Zhangjiakou Maternity and Child 2care CentreAbstract As one of t he college files , teaching files are playing an equally role t hroughout t he teaching management and p ractice. The rising p t education webs

12、ite of colleges and universities must f ully driveK ey w ords teaching files ; comp uter(上接第 126頁 On Theory and Application of H uff m an CodingKa ng HongboHebei Institute of Architecture and Civil EngineeringAbstract This article described a lossless comp ressio n encoding t he Huff man coding ,whi

13、ch has a wide range of applications.K ey w ords t he Huff man coding ; data compression(上接第 138頁 On The Vibration La w of the Vibration Systemof the V ertical Suspending Light SpringCui Hongn aHebei Institute of Architecture and Civil EngineeringAbstract This paper is intended to st udy t he movement of t he vibration system of t he vertical suspen 2 sion sp rings by t he energy law , in which t he quality of sp ring can not be ignored. In addition , it also o btains t he differential equation of t heir movement s and t