目錄
一、用二叉樹實作哈夫曼算法
二、哈夫曼樹能夠提升壓縮比率
三、可逆壓縮和非可逆壓縮
一、用二叉樹實作哈夫曼算法
上一篇部落格已經提到，莫爾斯編碼是根據日常文本中各字元的出現頻率來決定表示各字元的編碼資料長度的。不過該編碼體系中，對 AAAAAABBCDDEEEEEF 這種文本來說并不是效率最高的
下面用哈夫曼算法試一下，哈夫曼算法是指，為各壓縮對象檔案分别構造最佳的編碼體系，并以該編碼體系為基礎來進行壓縮。是以，用什麼樣的編碼（哈夫曼編碼）對資料進行分隔，就要由各個檔案而定。用哈夫曼算法壓縮過的檔案中，存儲着哈夫曼編碼資訊和壓縮過的資料
下面，對AAAAAABBCDDEEEEEF 中的A - F的字元，按照 出現頻率高的字元用盡量少的位數編碼來表示
| 字元 | 出現頻率 | 編碼（方案） | 位數 |
| A | 6 | 1 | |
| E | 5 | 1 | 1 |
| B | 2 | 10 | 2 |
| D | 2 | 11 | 2 |
| C | 1 | 100 | 3 |
| F | 1 | 101 | 3 |
在上表編碼方案中，随着出現頻率的降低，字元編碼資訊的資料位數逐漸增加，從最開始的1位、2位一次增加到3位。不過這個編碼體系是存在問題的，你不知道100這個3位的編碼，它的意思是用1、0、0這三個編碼來表示E、A、A呢？還是用10、0來表示B、A呢？還是用100來表示C呢？
而在哈夫曼算法中，通過借助哈夫曼樹的構造編碼體系，即使在不使用字元區分符号的情況下，也可以建構能夠進行區分的編碼體系。不過哈夫曼樹的算法要比較複雜，下面式一個哈夫曼樹的構造構成
自然界樹的從根開始生葉，而哈夫曼樹則是葉生枝
二、哈夫曼樹能夠提升壓縮比率
使用哈夫曼樹之後，出現頻率越高的資料所占用的位數越少，這也是哈夫曼樹的核心思想。通過上圖的步驟二可以看出，枝條連接配接資料時，我們是從出現頻率較低的資料開始的。這就意味着出現頻率低的資料到達根部的枝條也越多。而枝條越多則意味着編碼的位數随之增加
接下來我們來看哈夫曼樹的壓縮比率，用上圖得到的資料表示AAAAAABBCDDEEEEEF 為
000000000000 100100 110 101101 0101010101 111,40位 = 5位元組。壓縮前的資料是17位元組，壓縮後的資料達到了驚人的5位元組，也就是壓縮比率 = 5 /17 = 29%，達到了如此高的壓縮率
可以參考一下，無論哪種類型的資料，都可以用哈夫曼樹作為壓縮算法：
| 檔案類型 | 壓縮前 | 壓縮後 | 壓縮比率 |
| 文本檔案 | 14862位元組 | 4119位元組 | 28% |
| 圖像檔案 | 96062位元組 | 9456位元組 | 10% |
| EXE檔案 | 24576位元組 | 4652位元組 | 19% |
三、可逆壓縮和非可逆壓縮
圖像檔案的使用目的通常是把圖像資料傳輸到顯示器、列印機等裝置上。常用的圖像格式有：BMP、JPEG、TIFF、GIF格式等
BMP：是使用Windows自帶的畫筆來做成的一種圖像形式
JPEG：是數位相機等常用的一種圖像資料形式
TIFF：是一種通過在檔案中包含"标簽"就能夠快速顯示出資料形式的圖像形式
GIF：是由美國開發的一種資料形式，要求色數不超過256個