1948 - Shannon 資訊理論（位元與熵的誕生）#

import numpy as np
from collections import Counter
import heapq

# 1) 資訊熵的計算
def entropy(probs):
    """H = -Σ p log₂ p"""
    probs = np.array([p for p in probs if p > 0])
    return -np.sum(probs * np.log2(probs))

print("資訊熵：")
print(f"  均勻 2 面（公平硬幣）：H = {entropy([0.5, 0.5]):.4f} 位元")
print(f"  均勻 6 面（公平骰子）：H = {entropy([1/6]*6):.4f} 位元")
print(f"  均勻 256 面（1 byte）：H = {entropy([1/256]*256):.4f} 位元（= log₂256 = 8）")
print(f"  偏斜（p=0.9/0.1）：  H = {entropy([0.9, 0.1]):.4f} 位元")
print(f"  確定事件（p=1）：    H = {entropy([1.0]):.4f} 位元\n")

# 2) 中文與英文的熵（估計）
text_en = "the quick brown fox jumps over the lazy dog the the the"
text_zh = "資訊科學是研究資訊的科學資訊是消除不確定性的度量"
def text_entropy(text):
    cnt = Counter(text)
    total = len(text)
    probs = [c/total for c in cnt.values()]
    return entropy(probs), len(cnt)

H_en, n_en = text_entropy(text_en)
H_zh, n_zh = text_entropy(text_zh)
print(f"英文樣本（{n_en} 個字元）：H = {H_en:.4f} 位元/字元")
print(f"中文樣本（{n_zh} 個字元）：H = {H_zh:.4f} 位元/字元\n")

# 3) 信道容量（二進位對稱信道）
def h2(p):
    """二進位熵函數"""
    if p == 0 or p == 1:
        return 0.0
    return -p*np.log2(p) - (1-p)*np.log2(1-p)

def bsc_capacity(p):
    """BSC 容量：C = 1 - H₂(p)"""
    return 1 - h2(p)

print("二進位對稱信道容量（C = 1 - H₂(p)）：")
for p in [0.0, 0.01, 0.1, 0.25, 0.5]:
    C = bsc_capacity(p)
    print(f"  錯誤率 p = {p:.2f}: C = {C:.4f} 位元/次")
print("  → 即使 10% 錯誤，仍能可靠傳輸 53% 的容量（Shannon 極限）\n")

# 4) Huffman 編碼（最優前綴碼，1952）
def huffman_codes(text):
    """產生 Huffman 編碼"""
    cnt = Counter(text)
    heap = [[w, [sym, ""]] for sym, w in cnt.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return dict(sorted(heapq.heappop(heap)[1:]))

text = "abracadabra"
codes = huffman_codes(text)
cnt = Counter(text)
total = len(text)
print(f"Huffman 編碼（'{text}'）：")
avg_len = 0
for sym in sorted(cnt):
    print(f"  '{sym}' (p={cnt[sym]/total:.2f}): {codes[sym]}")
    avg_len += cnt[sym]/total * len(codes[sym])
H = text_entropy(text)[0]
print(f"  平均碼長 = {avg_len:.4f} 位元")
print(f"  熵 H = {H:.4f} 位元")
print(f"  H ≤ 平均碼長 < H+1：{H:.4f} ≤ {avg_len:.4f} < {H+1:.4f} ✓")
print(f"  壓縮率（vs 固定 4 位元/字元）：{(1 - avg_len/4)*100:.1f}%")

資訊熵：
  均勻 2 面（公平硬幣）：H = 1.0000 位元
  均勻 6 面（公平骰子）：H = 2.5850 位元
  均勻 256 面（1 byte）：H = 8.0000 位元（= log₂256 = 8）
  偏斜（p=0.9/0.1）：  H = 0.4690 位元
  確定事件（p=1）：    H = 0.0000 位元

英文樣本（27 個字元）：H = 4.1671 位元/字元
中文樣本（16 個字元）：H = 3.8554 位元/字元

二進位對稱信道容量（C = 1 - H₂(p)）：
  錯誤率 p = 0.00: C = 1.0000 位元/次
  錯誤率 p = 0.01: C = 0.9192 位元/次
  錯誤率 p = 0.10: C = 0.5310 位元/次
  錯誤率 p = 0.25: C = 0.1887 位元/次
  錯誤率 p = 0.50: C = 0.0000 位元/次
  → 即使 10% 錯誤，仍能可靠傳輸 53% 的容量（Shannon 極限）

Huffman 編碼（'abracadabra'）：
  'a' (p=0.45): 0
  'b' (p=0.18): 110
  'c' (p=0.09): 1110
  'd' (p=0.09): 1111
  'r' (p=0.18): 10
  平均碼長 = 2.0909 位元
  熵 H = 2.0404 位元
  H ≤ 平均碼長 < H+1：2.0404 ≤ 2.0909 < 3.0404 ✓
  壓縮率（vs 固定 4 位元/字元）：47.7%