データ圧縮の理論的限界はどこにあるのでしょうか。シャノンの情報源符号化定理（Shannon’s source coding theorem）は、「情報源のエントロピーが、無歪みデータ圧縮の究極の限界である」ことを数学的に示した定理です。1948年にクロード・シャノンが証明したこの定理は、ZIP、gzip、PNG などの圧縮アルゴリズムの背後にある理論的基盤を提供しています。
本記事では、符号理論の基礎からクラフトの不等式の証明を経て、情報源符号化定理を厳密に証明します。
本記事の内容
- 符号化の基本概念（一意復号可能性、瞬時符号）
- クラフトの不等式の証明
- 情報源符号化定理の主張と証明（達成可能性と逆定理）
- 典型列（typical sequence）と AEP（漸近等分割性）
- Pythonでの固定長符号と可変長符号の比較シミュレーション
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
符号化の基本
符号とは
情報源アルファベット $\mathcal{X} = \{x_1, x_2, \dots, x_m\}$ の各シンボルに対して、$D$ 元符号アルファベット $\{0, 1, \dots, D-1\}$ から成る有限長の系列（符号語, codeword）を割り当てる写像を符号と呼びます。
通常は $D=2$（2元符号、ビット列）を考えます。シンボル $x_i$ に対応する符号語の長さを $l_i$ とします。
一意復号可能符号
符号が一意復号可能（uniquely decodable）であるとは、任意の符号語の連結列が元のシンボル列に一意に復号できることを意味します。
例えば、$\mathcal{X} = \{a, b, c\}$ に対して
| 符号1（一意復号不可） | 符号2（一意復号可能） |
|---|---|
| $a \to 0$ | $a \to 0$ |
| $b \to 01$ | $b \to 10$ |
| $c \to 1$ | $c \to 11$ |
符号1では、ビット列 01 が $ab$ か $b$ かを区別できません。符号2は一意復号可能です。
瞬時符号（接頭辞符号）
瞬時符号（instantaneous code）または接頭辞符号（prefix-free code）とは、どの符号語も他の符号語の接頭辞になっていない符号です。
瞬時符号では、ビット列を左から読んでいくだけで符号語の境界が確定するため、復号に遅延が生じません。
例えば、
| シンボル | 符号語 |
|---|---|
| $a$ | 0 |
| $b$ | 10 |
| $c$ | 110 |
| $d$ | 111 |
は瞬時符号です。0 は他のどの符号語の接頭辞にもなっていません（10 は 0 で始まりません）。
重要な事実: すべての瞬時符号は一意復号可能です。逆は必ずしも成り立ちませんが、任意の一意復号可能符号に対して、同じ符号語長を持つ瞬時符号が存在します（マクミランの定理）。
クラフトの不等式
定理
$D$ 元アルファベット上の瞬時符号が存在するための必要十分条件は、符号語の長さ $l_1, l_2, \dots, l_m$ が次の不等式を満たすことです。
$$ \boxed{\sum_{i=1}^{m} D^{-l_i} \leq 1} $$
2元の場合は $\sum_{i=1}^{m} 2^{-l_i} \leq 1$ です。
証明（十分性: 瞬時符号の構成）
$\sum_{i} D^{-l_i} \leq 1$ を満たす長さ $l_1 \leq l_2 \leq \cdots \leq l_m$ が与えられたとき、瞬時符号が構成できることを示します。
$D$ 元の完全 $l_{\max}$-ary木（深さ $l_{\max} = \max_i l_i$ の木）を考えます。この木の各ノードは $D$ 個の子を持ちます。
- シンボル $x_1$ に対して、深さ $l_1$ のノードを1つ選び、その符号語とします。そのノードの子孫をすべて使用不可にします。
- シンボル $x_2$ に対して、深さ $l_2$ で使用可能なノードを1つ選び、その符号語とします。同様にその子孫を使用不可にします。
- これを $x_m$ まで繰り返します。
この手順が成功する（使用可能なノードが常に存在する）ことを示します。
シンボル $x_i$ を深さ $l_i$ に割り当てると、深さ $l_{\max}$ のリーフノードが $D^{l_{\max} – l_i}$ 個使用不可になります。全シンボルの割り当て後に使用不可となるリーフの合計は
$$ \sum_{i=1}^{m} D^{l_{\max} – l_i} = D^{l_{\max}} \sum_{i=1}^{m} D^{-l_i} \leq D^{l_{\max}} $$
深さ $l_{\max}$ のリーフの総数は $D^{l_{\max}}$ 個なので、使用不可のリーフ数が全リーフ数以下であり、各ステップで割り当てが可能です。
証明（必要性: 瞬時符号ならクラフトの不等式が成立）
瞬時符号が与えられたとします。深さ $l_i$ のノードに割り当てられた符号語は、$D^{l_{\max} – l_i}$ 個のリーフを排他的に占有します（接頭辞条件により、異なる符号語の占有するリーフ集合は互いに素）。
$$ \sum_{i=1}^{m} D^{l_{\max} – l_i} \leq D^{l_{\max}} $$
両辺を $D^{l_{\max}}$ で割ると、
$$ \sum_{i=1}^{m} D^{-l_i} \leq 1 \qquad \square $$
情報源符号化定理の主張
定理（シャノンの第1定理）
離散無記憶情報源 $X$ のエントロピーを $H(X)$ とし、$D$ 元瞬時符号の平均符号長を
$$ L = \sum_{i=1}^{m} p_i l_i $$
とするとき、
$$ \boxed{\frac{H(X)}{\log_2 D} \leq L} $$
が成り立ちます。ここで $H(X) = -\sum_{i} p_i \log_2 p_i$ です。$D = 2$ のとき、
$$ H(X) \leq L $$
さらに、
$$ L < \frac{H(X)}{\log_2 D} + 1 $$
を満たす瞬時符号が存在します。つまり、エントロピーは平均符号長の達成可能な下界です。
逆定理の証明（平均符号長の下界）
任意の一意復号可能な $D$ 元符号に対して $L \geq H_D(X)$ を示します。ここで $H_D(X) = -\sum_i p_i \log_D p_i = H(X) / \log_2 D$ です。
$r_i = D^{-l_i} / \sum_j D^{-l_j}$ とおくと、$\sum_i r_i = 1$ であり、これは確率分布になります。
クラフトの不等式より $c = \sum_j D^{-l_j} \leq 1$ なので、$r_i = D^{-l_i}/c$ です。
KLダイバージェンスの非負性を使います。$D_{\text{KL}}(p \| r) \geq 0$ より、
$$ \begin{align} 0 &\leq D_{\text{KL}}(p \| r) = \sum_i p_i \log_D \frac{p_i}{r_i} \\ &= \sum_i p_i \log_D p_i – \sum_i p_i \log_D r_i \\ &= -H_D(X) – \sum_i p_i \log_D \frac{D^{-l_i}}{c} \\ &= -H_D(X) – \sum_i p_i (-l_i \log_D D – \log_D c) \\ &= -H_D(X) + \sum_i p_i l_i + \log_D c \\ &= -H_D(X) + L + \log_D c \end{align} $$
$c \leq 1$ より $\log_D c \leq 0$ なので、
$$ 0 \leq -H_D(X) + L + \log_D c \leq -H_D(X) + L $$
したがって、
$$ L \geq H_D(X) \qquad \square $$
達成可能性の証明（上界の構成）
$L < H_D(X) + 1$ を満たす瞬時符号の存在を示します。
各シンボル $x_i$ に対して符号語長を
$$ l_i = \lceil -\log_D p_i \rceil = \lceil \log_D \frac{1}{p_i} \rceil $$
と設定します（シャノン符号）。
クラフトの不等式を満たすことの確認:
$l_i \geq -\log_D p_i$ より $D^{-l_i} \leq p_i$ なので、
$$ \sum_i D^{-l_i} \leq \sum_i p_i = 1 $$
クラフトの不等式を満たすので、この符号語長を持つ瞬時符号が存在します。
平均符号長の上界:
$l_i = \lceil -\log_D p_i \rceil$ より $-\log_D p_i \leq l_i < -\log_D p_i + 1$ なので、
$$ \begin{align} L = \sum_i p_i l_i &< \sum_i p_i (-\log_D p_i + 1) \\ &= -\sum_i p_i \log_D p_i + \sum_i p_i \\ &= H_D(X) + 1 \end{align} $$
したがって $H_D(X) \leq L < H_D(X) + 1$ が成り立ちます。 $\square$
典型列と AEP
典型列（Typical Sequence）
情報源符号化定理の深い理解には、典型列の概念が重要です。
確率変数 $X_1, X_2, \dots, X_n$ が独立同一分布（i.i.d.）に従うとき、長さ $n$ の系列 $\bm{x} = (x_1, x_2, \dots, x_n)$ の出現確率は
$$ p(\bm{x}) = \prod_{i=1}^{n} p(x_i) $$
対数を取ると
$$ -\frac{1}{n} \log_2 p(\bm{x}) = -\frac{1}{n} \sum_{i=1}^{n} \log_2 p(x_i) $$
AEP（漸近等分割性, Asymptotic Equipartition Property）
大数の弱法則により、$n \to \infty$ のとき
$$ -\frac{1}{n} \log_2 p(\bm{x}) \xrightarrow{p} H(X) $$
つまり、十分長い系列では、ほとんどすべての系列が $p(\bm{x}) \approx 2^{-nH(X)}$ という「ほぼ等しい確率」を持つようになります。これが漸近等分割性（AEP）です。
$\epsilon$-典型列集合
任意の $\epsilon > 0$ に対して、$\epsilon$-典型列集合 $A_\epsilon^{(n)}$ を次のように定義します。
$$ A_\epsilon^{(n)} = \left\{ \bm{x} \in \mathcal{X}^n : \left| -\frac{1}{n} \log_2 p(\bm{x}) – H(X) \right| < \epsilon \right\} $$
典型列集合は以下の性質を持ちます。
性質1: 典型列の確率はほぼ等しい
$$ \bm{x} \in A_\epsilon^{(n)} \Rightarrow 2^{-n(H(X)+\epsilon)} \leq p(\bm{x}) \leq 2^{-n(H(X)-\epsilon)} $$
性質2: 典型列集合の確率は 1 に近い
$$ \Pr(\bm{x} \in A_\epsilon^{(n)}) \to 1 \quad (n \to \infty) $$
より正確には、十分大きな $n$ に対して $\Pr(\bm{x} \in A_\epsilon^{(n)}) > 1 – \epsilon$ です。
性質3: 典型列の個数
$$ (1-\epsilon) \cdot 2^{n(H(X)-\epsilon)} \leq |A_\epsilon^{(n)}| \leq 2^{n(H(X)+\epsilon)} $$
上界の証明: $1 \geq \sum_{\bm{x} \in A_\epsilon^{(n)}} p(\bm{x}) \geq |A_\epsilon^{(n)}| \cdot 2^{-n(H(X)+\epsilon)}$ より $|A_\epsilon^{(n)}| \leq 2^{n(H(X)+\epsilon)}$
下界の証明: $1 – \epsilon \leq \sum_{\bm{x} \in A_\epsilon^{(n)}} p(\bm{x}) \leq |A_\epsilon^{(n)}| \cdot 2^{-n(H(X)-\epsilon)}$ より $|A_\epsilon^{(n)}| \geq (1-\epsilon) \cdot 2^{n(H(X)-\epsilon)}$
AEP から情報源符号化定理へ
AEP の意味は明快です。$n$ が大きいとき、情報源の出力系列は約 $2^{nH(X)}$ 個の典型列にほぼ集中します。これらの系列を等長のビット列で表現するには、
$$ nR \geq \log_2 2^{nH(X)} = nH(X) \quad \Rightarrow \quad R \geq H(X) $$
すなわち、1シンボルあたり平均 $H(X)$ ビット以上が必要です。逆に、$R > H(X)$ ならば、典型列だけを符号化すれば十分です。
Pythonでのシミュレーション
固定長符号 vs 可変長符号（シャノン符号）
import numpy as np
import matplotlib.pyplot as plt
# 情報源の定義
symbols = ['A', 'B', 'C', 'D']
probs = np.array([0.5, 0.25, 0.125, 0.125])
# エントロピーの計算
H = -np.sum(probs * np.log2(probs))
print(f"エントロピー H(X) = {H:.4f} bits")
# 固定長符号: すべての符号語が同じ長さ
fixed_lengths = np.array([2, 2, 2, 2]) # ceil(log2(4)) = 2
L_fixed = np.sum(probs * fixed_lengths)
print(f"固定長符号の平均符号長 L_fixed = {L_fixed:.4f} bits")
# シャノン符号: l_i = ceil(-log2(p_i))
shannon_lengths = np.ceil(-np.log2(probs)).astype(int)
L_shannon = np.sum(probs * shannon_lengths)
print(f"シャノン符号の符号語長: {dict(zip(symbols, shannon_lengths))}")
print(f"シャノン符号の平均符号長 L_shannon = {L_shannon:.4f} bits")
# 最適符号（ハフマン符号に近い）
# この例ではA:0, B:10, C:110, D:111が最適
optimal_lengths = np.array([1, 2, 3, 3])
L_optimal = np.sum(probs * optimal_lengths)
print(f"最適符号の符号語長: {dict(zip(symbols, optimal_lengths))}")
print(f"最適符号の平均符号長 L_optimal = {L_optimal:.4f} bits")
print(f"\n理論限界: H(X) = {H:.4f} <= L")
print(f"上界: L < H(X) + 1 = {H + 1:.4f}")
# 可視化
fig, ax = plt.subplots(figsize=(10, 6))
x_pos = np.arange(len(symbols))
width = 0.25
bars1 = ax.bar(x_pos - width, fixed_lengths, width, label='Fixed-length', color='skyblue')
bars2 = ax.bar(x_pos, shannon_lengths, width, label='Shannon code', color='salmon')
bars3 = ax.bar(x_pos + width, optimal_lengths, width, label='Optimal code', color='lightgreen')
ax.set_xlabel('Symbol', fontsize=12)
ax.set_ylabel('Codeword length (bits)', fontsize=12)
ax.set_title('Comparison of coding schemes', fontsize=13)
ax.set_xticks(x_pos)
ax.set_xticklabels([f'{s}\n(p={p})' for s, p in zip(symbols, probs)])
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3, axis='y')
# 確率を表示
for i, p in enumerate(probs):
ax.annotate(f'p={p}', (i, 0), textcoords="offset points",
xytext=(0, -20), ha='center', fontsize=9)
plt.tight_layout()
plt.show()
print(f"\n平均符号長の比較:")
print(f" 固定長: {L_fixed:.4f} bits (冗長度 = {L_fixed - H:.4f})")
print(f" シャノン: {L_shannon:.4f} bits (冗長度 = {L_shannon - H:.4f})")
print(f" 最適: {L_optimal:.4f} bits (冗長度 = {L_optimal - H:.4f})")
AEP（典型列集合）のシミュレーション
import numpy as np
import matplotlib.pyplot as plt
# 情報源のパラメータ
probs = np.array([0.5, 0.25, 0.125, 0.125])
H = -np.sum(probs * np.log2(probs))
print(f"エントロピー H(X) = {H:.4f} bits")
# 系列長ごとにシミュレーション
np.random.seed(42)
seq_lengths = [10, 50, 100, 500, 1000]
n_trials = 10000
epsilon = 0.3
fig, axes = plt.subplots(2, 3, figsize=(15, 10))
axes = axes.flatten()
for idx, n in enumerate(seq_lengths):
# ランダム系列を生成
sequences = np.random.choice(len(probs), size=(n_trials, n), p=probs)
# 各系列の -1/n * log2(p(x)) を計算
log_probs = np.log2(probs)
per_symbol_info = np.zeros(n_trials)
for trial in range(n_trials):
per_symbol_info[trial] = -np.mean(log_probs[sequences[trial]])
# ヒストグラムをプロット
ax = axes[idx]
ax.hist(per_symbol_info, bins=50, density=True, alpha=0.7, color='steelblue',
edgecolor='black', linewidth=0.5)
ax.axvline(H, color='red', linewidth=2, linestyle='--', label=f'H(X) = {H:.3f}')
ax.axvline(H - epsilon, color='orange', linewidth=1.5, linestyle=':')
ax.axvline(H + epsilon, color='orange', linewidth=1.5, linestyle=':')
# 典型列の割合
typical_ratio = np.mean(np.abs(per_symbol_info - H) < epsilon)
ax.set_title(f'n = {n} (typical: {typical_ratio:.1%})', fontsize=12)
ax.set_xlabel('$-\\frac{1}{n} \\log_2 p(\\mathbf{x})$', fontsize=11)
ax.set_ylabel('Density', fontsize=11)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
# 空のサブプロットに典型列の割合の推移をプロット
ax = axes[5]
all_lengths = np.arange(5, 1001, 5)
typical_ratios = []
for n in all_lengths:
sequences = np.random.choice(len(probs), size=(n_trials, n), p=probs)
per_symbol_info = np.zeros(n_trials)
for trial in range(n_trials):
per_symbol_info[trial] = -np.mean(log_probs[sequences[trial]])
typical_ratios.append(np.mean(np.abs(per_symbol_info - H) < epsilon))
ax.plot(all_lengths, typical_ratios, 'b-', linewidth=1.5)
ax.axhline(1.0, color='red', linewidth=1, linestyle='--', alpha=0.5)
ax.set_xlabel('Sequence length n', fontsize=12)
ax.set_ylabel('Fraction of typical sequences', fontsize=12)
ax.set_title(f'AEP convergence (ε = {epsilon})', fontsize=12)
ax.grid(True, alpha=0.3)
plt.suptitle('Asymptotic Equipartition Property (AEP)', fontsize=14, y=1.02)
plt.tight_layout()
plt.show()
ブロック符号化による圧縮率の改善
import numpy as np
import matplotlib.pyplot as plt
# 情報源の定義
probs = np.array([0.5, 0.25, 0.125, 0.125])
H = -np.sum(probs * np.log2(probs))
def block_shannon_code_avg_length(probs, block_size):
"""
ブロックサイズkの拡大情報源に対するシャノン符号の
1シンボルあたりの平均符号長を計算
"""
m = len(probs)
# 拡大情報源の各ブロックの確率と符号語長を計算
# 全ブロックを列挙
from itertools import product
total_avg_length = 0.0
for block in product(range(m), repeat=block_size):
p_block = np.prod([probs[s] for s in block])
l_block = int(np.ceil(-np.log2(p_block)))
total_avg_length += p_block * l_block
# 1シンボルあたり
return total_avg_length / block_size
# ブロックサイズを変えてシミュレーション
block_sizes = range(1, 8)
avg_lengths_per_symbol = []
for k in block_sizes:
L_k = block_shannon_code_avg_length(probs, k)
avg_lengths_per_symbol.append(L_k)
print(f"ブロックサイズ k={k}: L/k = {L_k:.4f} bits/symbol")
print(f"\nエントロピー H(X) = {H:.4f} bits/symbol")
# 可視化
fig, ax = plt.subplots(figsize=(10, 6))
ax.plot(list(block_sizes), avg_lengths_per_symbol, 'bo-',
linewidth=2, markersize=8, label='Shannon code L/k')
ax.axhline(H, color='red', linewidth=2, linestyle='--',
label=f'H(X) = {H:.4f}')
ax.axhline(H + 1, color='orange', linewidth=1.5, linestyle=':',
label=f'H(X) + 1 = {H + 1:.4f}')
ax.fill_between(list(block_sizes), H, [H + 1/k for k in block_sizes],
alpha=0.15, color='green', label='Achievable region')
# H + 1/k の理論上界も表示
theory_upper = [H + 1/k for k in block_sizes]
ax.plot(list(block_sizes), theory_upper, 'g--', linewidth=1.5,
label='H(X) + 1/k (upper bound)')
ax.set_xlabel('Block size k', fontsize=12)
ax.set_ylabel('Average bits per symbol', fontsize=12)
ax.set_title('Block coding: convergence to entropy', fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
ax.set_xticks(list(block_sizes))
ax.set_ylim(H - 0.1, H + 1.1)
plt.tight_layout()
plt.show()
上のグラフは、ブロックサイズ $k$ を大きくすると1シンボルあたりの平均符号長がエントロピー $H(X)$ に近づくことを示しています。シャノンの定理が予測する通り、
$$ H(X) \leq \frac{L_k}{k} < H(X) + \frac{1}{k} $$
が成り立ち、$k \to \infty$ で $L_k / k \to H(X)$ となります。
まとめ
本記事では、情報源符号化定理（シャノンの第1定理）について解説しました。
- クラフトの不等式: 瞬時符号の存在条件 $\sum_i D^{-l_i} \leq 1$
- 情報源符号化定理: 平均符号長の下界はエントロピー $H(X) \leq L$
- 達成可能性: シャノン符号で $L < H(X) + 1$ を達成可能
- 典型列と AEP: 長い系列はほぼ $2^{nH}$ 個の典型列に集中する
- ブロック符号化: ブロックサイズ $k$ を大きくすると $L/k \to H(X)$
情報源符号化定理は「データ圧縮にはエントロピーという越えられない壁がある」ことを示すと同時に、「その壁にいくらでも近づける」ことも保証しています。
次のステップとして、以下の記事も参考にしてください。