關於此實驗
每個 ZIP 檔案、PNG 圖片和 MP3 音軌都比原始資料小，因為它們會移除重複內容。用你自己的訊息試試兩種經典的無損壓縮方法。游程編碼會將一串相同的符號替換為其數量，這種方法非常適合簡單圖片，卻不適用於一般文字。霍夫曼編碼為常見符號指定較短的編碼，為罕見符號指定較長的編碼，並透過逐步建構一棵樹來產生編碼，其效率與克勞德·香農於 1948 年發現的理論極限相差不到每個符號 1 位元。
學習目標
- 說明無損壓縮與有損壓縮的差異
- 使用游程編碼對訊息進行編碼和解碼，並說明它在哪些情況下有用
- 反覆合併出現頻率最低的兩個符號，建構霍夫曼樹
- 從樹中讀取碼字，並說明為什麼沒有任何編碼是另一個編碼的前綴
- 將壓縮後的大小與熵極限比較，並計算壓縮率
使用方法
- 1選擇 Pixel 列並選擇游程編碼。編碼前後，這一列分別需要多少位元？為什麼它的效果這麼好？
- 2選擇游程編碼，然後切換到 Hamlet。為什麼訊息變大了？
- 3選擇 Mississippi，然後按下「建立樹」。每一步中，哪兩棵樹會合併？為什麼？
- 4樹建立完成後，找出出現頻率最高和最低的字母所對應的碼字，並數一數各有多少位元。
- 5從根節點開始沿著樹往下走，手動解碼編碼訊息的前幾個位元。
- 6輸入一則只使用同一個字母的訊息，再輸入一則每個字母都不同的訊息。在這兩種情況下，比較霍夫曼編碼與熵極限。
模型
假設
- 原始訊息每個字元使用 8 位元，與 ASCII 相同。
- 每個遊程對都儲存為一個 8 位元計數和一個 8 位元字元，因此長度超過 255 的遊程會被拆分。
- 霍夫曼編碼的大小只計算編碼後的訊息。實際檔案還需要儲存碼表或各字元的計數，這對較短的訊息很重要。
- 如果兩棵樹的權重相同，則先建立的樹先被選取，較輕的樹成為 0 分支。採用其他的平手處理規則，會得到總長度相同但內容不同的編碼。
在課堂上試試這個實驗
- Q1使用遊程編碼對 BBBBBWWWBBBBBBBB 進行編碼。需要多少位元組？
- Q2根據計數 A 5、B 2、R 2、C 1、D 1 建立霍夫曼樹，並求出編碼 ABRACADABRA 所需的總位元數。
- Q3為什麼霍夫曼編碼必須是前綴碼？如果 A 編為 0、B 編為 01，會有什麼問題？
- Q4一段文字中有 8 個不同的字母，且出現頻率相同。它的熵是多少？霍夫曼編碼能壓縮它嗎？
- Q5JPEG 和 MP3 的壓縮率遠高於霍夫曼編碼。它們為此犧牲了什麼？
常見問題
如今霍夫曼編碼用在什麼地方？
它應用於許多日常格式：ZIP 和 gzip（DEFLATE 方法）、PNG 影像、有損壓縮步驟之後的 JPEG 影像，以及 MP3 音訊。通常，這是在另一種方法將重複內容轉換為數字之後進行的最後一個階段。
任何檔案都能壓縮嗎？
不能。如果存在一種能讓每個檔案都變小的無損壓縮方法，就可以不斷地再次壓縮壓縮後的結果。但短檔案的數量少於長檔案，因此這不可能實現。隨機資料和已經壓縮過的檔案通常不會變得更小。
哈夫曼樹是唯一的嗎？
不一定。計數相同時，不同的選擇會產生不同的樹和碼字，但對於相同的計數，任何哈夫曼樹所需的總位元數都相同。