シャノンの情報源符号化定理

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：無歪み符号化とKraft不等式、漸近等分割性とAEP　|　次：ハフマン符号

要点（BLUF）

シャノンの情報源符号化定理：i.i.d. 情報源の1記号あたり平均符号長 $L$ は、どんな無歪み符号でも $L\ge H$ 。逆に $L$ をいくらでも $H$ に近づける符号が作れる。エントロピーが圧縮の理論限界。
下界（逆定理） $L\ge H$ は Kraft 不等式＋Gibbs の不等式から。達成可能性 はシャノン符号 $l_i=\lceil-\log_2 p_i\rceil$ で $L<H+1$ 、ブロック長 $k$ にすると $L/k< H+1/k\to H$ 。
根拠は AEP（漸近等分割性とAEP）：典型系列は約 $2^{nH}$ 個、それらに $nH$ bit の番号を振ればほぼ誤りなく圧縮できる。

1. 下界（逆定理）： $L\ge H$

一意復号可能な符号の符号長は Kraft 不等式 $\sum_i 2^{-l_i}\le1$ を満たします（無歪み符号化とKraft不等式）。 $q_i=2^{-l_i}/Z$ （ $Z=\sum 2^{-l_i}\le1$ ）とおくと、平均符号長は

L = \sum_i p_i l_i = \sum_i p_i\big(-\log_2 q_i - \log_2 Z\big) = H(p) + D(p\,\|\,q) - \log_2 Z \;\ge\; H(p)

$D(p\|q)\ge0$ と $\log_2 Z\le0$ の両方が $L$ を押し上げるので、どんな符号でも平均長はエントロピー以上。等号は $q=p$ かつ $Z=1$ 、すなわち $l_i=-\log_2 p_i$ が整数のとき（確率が2の冪のとき）だけ。

2. 達成可能性：シャノン符号とブロック化

シャノン符号長 $l_i=\lceil-\log_2 p_i\rceil$ は Kraft を満たし（無歪み符号化とKraft不等式）、 $-\log_2 p_i\le l_i< -\log_2 p_i+1$ から

H \le L < H + 1

「+1」は1記号ごとに最大1 bit 無駄になりうるという意味。そこで $k$ 記号をまとめて1ブロックとして符号化すると、無駄はブロック全体で1 bit、すなわち1記号あたり $1/k$ に薄まります：

H \le \frac{L_k}{k} < H + \frac{1}{k} \;\xrightarrow{\;k\to\infty\;}\; H

ブロックを長くするほど1記号あたりの符号長はエントロピーに収束します。これが「達成可能」の意味です。

3. コード：ブロック化で $L/k\to H$ （底2, bit）

情報源 $p(a)=0.8,p(b)=0.2$ （ $H=0.7219$ bit）で、ブロック長 $k$ の最適符号（ハフマン）平均長を1記号あたりに直すと、 $H$ に収束します。

import numpy as np, heapq
from itertools import product

def huffman_avg_len(probs):
    # probs: list of probabilities -> 最適接頭符号の平均長
    heap=[[pp,i,[i]] for i,pp in enumerate(probs)]; heapq.heapify(heap)
    lengths=[0]*len(probs); cnt=len(probs)
    if len(probs)==1: return 1.0
    while len(heap)>1:
        lo=heapq.heappop(heap); hi=heapq.heappop(heap)
        for i in lo[2]: lengths[i]+=1
        for i in hi[2]: lengths[i]+=1
        heapq.heappush(heap,[lo[0]+hi[0],cnt,lo[2]+hi[2]]); cnt+=1
    return sum(p*l for p,l in zip(probs,lengths))

pv=np.array([0.8,0.2])
H = -np.sum(pv*np.log2(pv))
print(f"エントロピー H = {H:.4f} bit/記号（情報源 p(a)=0.8, p(b)=0.2）")
print(f"{'ブロック長 k':>12}{'L_k/k(bit/記号)':>18}{'上界 H+1/k':>14}")
for k in [1,2,4,8,12]:
    probs=[np.prod(pv[list(b)]) for b in product([0,1],repeat=k)]
    Lk=huffman_avg_len(probs)
    print(f"{k:>12}{Lk/k:>18.4f}{H+1/k:>14.4f}")
print(f"\n下界 H={H:.4f} <= L_k/k < H+1/k。ブロックを伸ばすと H に収束（符号化定理）")

出力：

エントロピー H = 0.7219 bit/記号（情報源 p(a)=0.8, p(b)=0.2）
     ブロック長 k     L_k/k(bit/記号)      上界 H+1/k
           1            1.0000        1.7219
           2            0.7800        1.2219
           4            0.7408        0.9719
           8            0.7322        0.8469
          12            0.7250        0.8053

下界 H=0.7219 <= L_k/k < H+1/k。ブロックを伸ばすと H に収束（符号化定理）

出力の意味：1記号ずつ符号化すると $L=1.0$ bit と無駄が大きい（2値は最低1 bit 必要なので $H=0.72$ には届かない）。しかしブロック長を $k=2,4,8,12$ と伸ばすと、1記号あたりの符号長が $0.78\to0.74\to0.73\to0.725$ と単調に $H=0.7219$ へ収束していきます。理論上界 $H+1/k$ も $1.72\to0.81$ と縮み、達成可能性を裏づけます。整数長の制約による無駄はブロック化で償却できる——これが「エントロピーは到達可能な限界」という定理の中身です。

4. AEP による証明の骨格

直接的な証明は AEP（漸近等分割性とAEP）から来ます。長さ $n$ の系列のうち典型集合 $A_\varepsilon^{(n)}$ は約 $2^{nH}$ 個で、確率のほぼ全部を占めます。

達成可能性：典型系列だけに $\lceil n(H+\varepsilon)\rceil$ bit の番号を振り、非典型系列は捨てる（または長い符号を振る）。非典型系列の確率は $\to0$ なので、平均符号長は $n(H+\varepsilon)$ bit、1記号あたり $H+\varepsilon$ 。
逆： $2^{n(H-\varepsilon)}$ 個未満しか符号語を用意しないと、典型系列の大半が表現できず復号誤りが1に近づく。だから $H$ 未満では不可能。

「典型系列の個数の対数＝ $nH$ 」が、そのまま必要ビット数になります。

5. 数式の直観的意味

符号化定理は「圧縮率には越えられない壁があり、その壁の高さがエントロピー」と言っています。テキストファイルが gzip で半分になるのは、元の表現（1文字8 bit）が実際のエントロピー（英語で約1.5 bit/文字）よりずっと冗長だから。逆に、すでにエントロピー近くまで圧縮されたデータ（暗号文・乱数）はそれ以上縮みません。この限界は記憶のある情報源ではエントロピーレート（結合・条件付きエントロピーと連鎖則）に置き換わり、実際の汎用圧縮器（算術符号とユニバーサル符号）がこの限界に肉薄します。

⚠️ よくある誤解

「どんなデータも半分に圧縮できる」ではない：すでにエントロピー近くのデータ（乱数・暗号文・圧縮済み）はほとんど縮みません。圧縮はあくまで冗長性の除去。
「 $L<H$ の符号を作れる天才的方法がある」ではない：逆定理が $L\ge H$ を証明しています。例外はありません（無歪みの場合）。
「シャノン符号は最適」ではない： $L<H+1$ を保証しますが最適ではありません。同じブロックではハフマンの方が短い（ハフマン符号）。
「ブロック化すればいくらでも縮む」ではない：縮むのは整数長の無駄（最大1 bit/記号）だけ。下限 $H$ は越えられません。

対応シミュレーション

本文のコードでブロック化による $L/k\to H$ の収束を実証済み。