無歪み符号化とKraft不等式

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：自己情報量とエントロピー　|　次：シャノンの情報源符号化定理

要点（BLUF）

接頭符号（prefix code）：どの符号語も他の符号語の接頭辞でない符号。区切り記号なしで一意に復号でき、受け取りながら即座に復号できます。
Kraft 不等式：符号語長 $l_1,\dots,l_m$ を持つ一意復号可能な符号が存在する必要十分条件は $\sum_i 2^{-l_i}\le 1$ 。
確率 $p_i$ に対し シャノン符号長 $l_i=\lceil -\log_2 p_i\rceil$ を選べば Kraft を満たし、平均符号長は $H\le L< H+1$ 。これが符号化定理（シャノンの情報源符号化定理）の足場。

1. 接頭符号と符号木

符号語を2分木の葉に対応させます。根から左を 0、右を 1 とたどると、各葉が符号語に対応。接頭符号 ⇔ すべての符号語が葉（内部ノードに符号語を置かない）。葉なら、ある符号語が別の符号語の途中に現れることがなく、ビット列を頭から読んで葉に着いた瞬間に1記号を確定できます（瞬時符号）。

graph TD
  root["根"] -->|"0"| a["a（符号 0）"]
  root -->|"1"| n1["内部"]
  n1 -->|"0"| b["b（符号 10）"]
  n1 -->|"1"| n2["内部"]
  n2 -->|"0"| c["c（符号 110）"]
  n2 -->|"1"| d["d（符号 111）"]

深さ $l$ の葉は「符号長 $l$ 」。深い葉を1つ使うと、その下にあったはずの $2^{-l}$ 分の「木の容量」を消費します。

2. Kraft 不等式

符号語長 $\{l_i\}$ を持つ接頭符号が存在する必要十分条件は

\sum_{i=1}^{m} 2^{-l_i} \le 1

（McMillan により、接頭符号でなくても一意復号可能な符号すべてに同じ不等式が成り立ちます）。直観：深さ $l_i$ の葉は木全体の割合 $2^{-l_i}$ を占有し、葉同士は重ならないので合計は1（木全体）を超えられない。逆に $\sum 2^{-l_i}\le1$ なら、長さを短い順に葉を割り当てていけば必ず接頭符号を構成できます。

含意：符号長を勝手に短くはできません。1つを短くすれば別を長くせざるを得ない——Kraft は「符号長の予算制約」です。この制約のもとで平均符号長 $L=\sum p_i l_i$ を最小化するのが符号設計の問題で、答えの下限がエントロピーになります。

3. コード：Kraft 和とシャノン符号長（底2, bit）

接頭符号の Kraft 和を確かめ、シャノン符号長 $\lceil-\log_2 p_i\rceil$ が Kraft を満たし $L<H+1$ になることを見ます。

import numpy as np
# 接頭符号(prefix code)の例。符号語長 l_i と Kraft和 Σ 2^{-l_i}
code = {'a':'0', 'b':'10', 'c':'110', 'd':'111'}
lengths = {s:len(c) for s,c in code.items()}
kraft = sum(2**(-l) for l in lengths.values())
print("接頭符号:", code)
print(f"符号語長: {lengths}")
print(f"Kraft和 Σ2^(-l) = {kraft:.4f}  (<=1 なら一意復号可能な接頭符号が存在)")
print("-"*50)
# シャノン符号長 l_i = ceil(-log2 p_i) は Kraft を満たし、平均長 < H+1
p = {'a':0.5,'b':0.25,'c':0.125,'d':0.125}
H = -sum(pi*np.log2(pi) for pi in p.values())
shannon_len = {s:int(np.ceil(-np.log2(pi))) for s,pi in p.items()}
L = sum(p[s]*shannon_len[s] for s in p)
kraft_s = sum(2**(-l) for l in shannon_len.values())
print(f"確率: {p}")
print(f"エントロピー H = {H:.4f} bit")
print(f"シャノン符号長 ceil(-log2 p): {shannon_len}")
print(f"Kraft和 = {kraft_s:.4f} (<=1)")
print(f"平均符号長 L = {L:.4f} bit   (H <= L < H+1: {H<=L<H+1})")

出力：

接頭符号: {'a': '0', 'b': '10', 'c': '110', 'd': '111'}
符号語長: {'a': 1, 'b': 2, 'c': 3, 'd': 3}
Kraft和 Σ2^(-l) = 1.0000  (<=1 なら一意復号可能な接頭符号が存在)
--------------------------------------------------
確率: {'a': 0.5, 'b': 0.25, 'c': 0.125, 'd': 0.125}
エントロピー H = 1.7500 bit
シャノン符号長 ceil(-log2 p): {'a': 1, 'b': 2, 'c': 3, 'd': 3}
Kraft和 = 1.0000 (<=1)
平均符号長 L = 1.7500 bit   (H <= L < H+1: True)

出力の意味：この符号の Kraft 和はちょうど $1$ ——木の容量を使い切った「完全（飽和）」な符号です。確率が $2$ の冪 $\{1/2,1/4,1/8,1/8\}$ のときは、シャノン符号長が $-\log_2 p_i$ にぴたり一致し、平均長 $L=1.75$ がエントロピー $H=1.75$ と等しくなります（この特別な場合だけ等号）。一般の確率では $\lceil\cdot\rceil$ の切り上げで $L$ は $H$ より少し大きくなりますが、 $H\le L<H+1$ の枠は必ず守られます。次のノートでこの「+1」をブロック化で消します。

4. 数式の直観的意味

$2^{-l_i}$ を確率とみなすと、Kraft 和が1ということは「符号長の集合は、ある確率分布 $q_i=2^{-l_i}$ に対応する」ことを意味します。すると平均符号長は $L=\sum p_i l_i=\sum p_i(-\log_2 q_i)$ ＝交差エントロピー $H(p,q)$ 。Gibbs の不等式（エントロピーの性質と最大エントロピー）から $H(p,q)\ge H(p)$ で等号は $q=p$ 、すなわち $l_i=-\log_2 p_i$ のとき。符号長を確率に合わせるのが最適——これが符号化定理の核心であり、 $p_i$ が2の冪でないと整数長にできず「+1」の無駄が出る理由です。

⚠️ よくある誤解

「Kraft 和は接頭符号だけの話」ではない：McMillan の定理により、一意復号可能な符号すべてに $\sum 2^{-l_i}\le1$ が成り立ちます。だから接頭符号に限っても一般性を失いません。
「Kraft を満たせば必ず良い符号」ではない：Kraft は存在条件であって最適性ではありません。最適にするには符号長を確率に合わせる必要があります（ハフマン符号）。
「符号長は自由に決められる」ではない：1つを短くすれば予算制約 $\sum 2^{-l_i}\le1$ から他を長くせざるを得ません。
「Kraft 和は必ず1」ではない： $<1$ でも一意復号可能（容量に余りがある＝最適でない）。 $=1$ で木を使い切った状態。

対応シミュレーション

本文のコードで Kraft 和とシャノン符号長の枠 $H\le L<H+1$ を実証済み。