Huffman 編碼

Vibe Prompt

「幫我實作 Huffman 編碼：輸入字串 'hello world'，輸出每個字元的 Huffman 編碼與壓縮率。」

import heapq
from collections import Counter

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    def __lt__(self, other):
        return self.freq < other.freq

def huffman_encoding(text):
    freq = Counter(text)
    heap = [HuffmanNode(c, f) for c, f in freq.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)
    
    codes = {}
    def build_code(node, prefix=""):
        if node.char:
            codes[node.char] = prefix
        else:
            build_code(node.left, prefix + "0")
            build_code(node.right, prefix + "1")
    build_code(heap[0])
    
    encoded = ''.join(codes[c] for c in text)
    original_bits = len(text) * 8
    compressed_bits = len(encoded)
    return codes, encoded, compressed_bits / original_bits

codes, encoded, ratio = huffman_encoding("hello world")
print(f"Huffman 編碼表: {codes}")
print(f"原始: 88 bits → 壓縮後: {len(encoded)} bits")
print(f"壓縮率: {ratio:.1%}")

深入理解：Huffman 編碼的最優性

為什麼 Huffman 是最佳前綴碼？

Huffman 使用貪婪選擇性質：

頻率最低的兩個字元，一定會在最佳編碼樹的最深層，且互為兄弟節點。

證明：如果最低頻的字元不在最深層，交換後可以得到更短的總編碼長度。

壓縮率比較

| 編碼方式 | 優點 | 缺點 | |----------|------|------| | ASCII (8-bit) | 固定長度，簡單 | 浪費空間 | | Huffman | 最佳前綴碼，無失真 | 需傳遞編碼表 | | 算術編碼 | 壓縮率更高 | 更複雜，有專利 | | LZW | 字典式，不需編碼表 | 適合重複模式 |

# 壓縮率對比實驗
texts = [
    "hello world",
    "aaaaabbbbbcccccdddddeeeeefffff",
    "The quick brown fox jumps over the lazy dog"
]

for text in texts:
    result = huffman_encoding(text)
    codes, encoded, ratio = result if len(result) == 3 else (None, None, 0)
    original = len(text) * 8
    print(f"文字: {text[:30]}...")
    print(f"  ASCII: {original} bits")
    print(f"  Huffman: {len(encoded)} bits")
    print(f"  壓縮率: {ratio:.1%}")

關鍵要點

✅ Huffman 編碼 = 最佳前綴碼（無失真壓縮）
✅ 貪婪策略：合併頻率最低的兩個節點
✅ 編碼樹的所有字元都在葉節點，確保前綴碼性質
✅ 壓縮率取決於字元頻率分布（越不均勻壓縮率越高）
✅ Huffman 是 JPEG、DEFLATE (gzip) 等格式的基礎

讓你能夠將所學應用到實際專案中



## 常見錯誤

## 程式碼範例

```python

## Huffman 編碼：貪婪演算法的經典成功案例

Huffman 編碼之所以有名，不是因為它很難——剛好相反，它的演算法非常簡單——而是因為它證明了**貪婪策略在某些問題上可以得到最佳解**。

### Huffman 編碼的關鍵洞察

壓縮的本質是：**用短編碼代表高頻字元，用長編碼代表低頻字元。**

這背後的數學原理是資訊熵（Entropy）——任何無失真壓縮演算法的理論極限就是訊號的熵值。Huffman 編碼的壓縮率非常接近這個理論極限，而且實作超級簡單。

### 在真實世界的應用

| 場景 | 使用 Huffman 編碼的理由 |
|:----|:----------------------|
| **JPEG / PNG 圖檔** | 在 DCT 轉換後對係數進行熵編碼 |
| **ZIP / GZip 壓縮** | 搭配 LZ77 演算法使用 |
| **HTTP Compression** | 網頁伺服器用 GZip/DEFLATE 壓縮傳輸內容 |
| **通訊協定** | 在有限頻寬下最大化資料傳輸量 |

### 為什麼不直接用 Huffman？

因為 Huffman 編碼需要事先知道字元的頻率分布，而且編碼表需要儲存在檔案開頭。現代壓縮工具（如 zstd、brotli）使用更先進的 ANS（Asymmetric Numeral Systems）編碼來解決這些限制。

### 下一章預告：集合覆蓋問題

從 Huffman 編碼我們看到了貪婪演算法可以找到最佳解。但下一章的集合覆蓋問題（Set Cover）將告訴你——貪婪並不總是能得到最佳解，而這正是 NP-hard 問題的開端。