樹 - 哈夫曼樹及其應用 - 哈夫曼編碼 （一）

　　編碼方案

　　 編碼和解碼

　　數據壓縮過程稱為編碼即將文件中的每個字符均轉換為一個惟一的二進制位串

　　數據解壓過程稱為解碼即將二進制位串轉換為對應的字符

　　 等長編碼方案和變長編碼方案

　　給定的字符集C可能存在多種編碼方案

　　() 等長編碼方案

　　等長編碼方案將給定字符集C中每個字符的碼長定為[lg|C|]|C|表示字符集的大小

　　【例】設待壓縮的數據文件共有個字符這些字符均取自字符集C={abcdef}等長編碼需要三位二進制數字來表

　　示六個字符因此整個文件的編碼長度為位

　　()變長編碼方案

　　變長編碼方案將頻度高的字符編碼設置短將頻度低的字符編碼設置較長

　　【例】設待壓縮的數據文件共有個字符這些字符均取自字符集C={abcdef}其中每個字符在文件中出現的次數

　　(簡稱頻度)見表

　　表 字符編碼問題

　　

　　字符 a b c d e f

　　頻度(單位千次)

　　定長編碼

　　變長編碼

　　

　　根據計算公式

　　(*+*+*+*+*+)*=

　　整個文件被編碼為位比定長編碼方式節約了約%的存儲空間

　　注意

　　變長編碼可能使解碼產生二義性產生該問題的原因是某些字符的編碼可能與其他字符的編碼開始部分(稱為前綴)相同

　　【例】設ETW分別編碼為則解碼時無法確定信息串是ET還是W

　　 前綴碼方案

　　對字符集進行編碼時要求字符集中任一字符的編碼都不是其它字符的編碼的前綴這種編碼稱為前綴(編)碼

　　注意

　　等長編碼是前綴碼

　　最優前綴碼

　　平均碼長或文件總長最小的前綴編碼稱為最優的前綴碼最優的前綴碼對文件的壓縮效果亦最佳

　　

　　其中

　　p i 為第i個字符得概率

　　l i 為碼長

　　【例】若將表所示的文件作為統計的樣本則a至f六個字符的概率分別為對變長編碼

　　求得的平均碼長為優於定長編碼(平均碼長為)

From:http://tw.wingwit.com/Article/program/sjjg/201311/23863.html