4.6 Huffman 符号の最適性

4.5 節までで問題は次の形に整理された．Kraft の不等式を満たし，かつすべての $𝑥$ で $ℓ (𝑥) \geq 1$ である長さの組のうち， $\sum 𝑥 𝑝 (𝑥) ℓ (𝑥)$ を最小にするものを求めよ．定理 4.3.2 はこの最小値が $𝐻 𝐷 (𝑋)$ 以上であることを，定理 4.4.4 は $𝐻 𝐷 (𝑋) + 1$ 未満であることを教えたが，最小値そのものはまだ分かっていない．例 4.4.5 で見たとおり，Shannon 符号はその最小を与えるとは限らない．本節は最小を与える長さの組を，確率を見比べるだけの手続きで作る．

本節では $𝐷 = 2$ に固定する．一般の $𝐷$ にも同じ考えで拡張できるが，一度に併合する個数の調整が要るので，本書は二元の場合だけを扱う．

手続き

定義 4.6.1（Huffman 符号語長）. $X$ を $2$ 個以上の文字からなる有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．長さの組 $ℓ H$ を，アルファベットの大きさについての再帰で次のように定める．

$| X | = 2$ のときは，二つの文字のどちらにも値 $1$ を与える．

$| X | \geq 3$ のときは， $𝑝 (𝑢) \leq 𝑝 (𝑧)$ がすべての $𝑧 \in X$ で成り立つ文字 $𝑢$ と， $𝑝 (𝑣) \leq 𝑝 (𝑧)$ が $𝑢$ 以外のすべての $𝑧$ で成り立つ文字 $𝑣 \neq 𝑢$ をとる． $𝑢$ と $𝑣$ を新しい $1$ 文字 $𝑤$ に置き換えたアルファベットを $X'$ ，その上の分布 $𝑝'$ を $𝑝' (𝑤) : = 𝑝 (𝑢) + 𝑝 (𝑣)$ ， $𝑝' (𝑧) : = 𝑝 (𝑧)$ （ $𝑧 \neq 𝑤$ ）で定める． $(X', 𝑝')$ に対して定まる長さの組を $ℓ'$ として

ℓ H (𝑢) : = ℓ' (𝑤) + 1, ℓ H (𝑣) : = ℓ' (𝑤) + 1, ℓ H (𝑧) : = ℓ' (𝑧) (𝑧 \neq 𝑢, 𝑣)

と定める．こうして得られる $ℓ H$ を Huffman 符号語長 と呼ぶ．確率が等しい文字があって $𝑢$ と $𝑣$ の選び方に任意性があるときは，そのいずれから得られる組も Huffman 符号語長と呼ぶ．

手続きの読み方は素直で，確率のいちばん小さい二つの文字を一つにまとめる操作を，文字が二つになるまで繰り返している．まとめられるたびに，そのまとまりに入っている文字の符号語が一つずつ伸びる．最後に残った二つに長さ $1$ を与える操作も，二つを一つにまとめる操作を一度行ったと数えれば，符号語長の勘定は一つの規則にまとまる．すなわち各文字の符号語長は，その文字を含むまとまりが併合に加わった回数に等しい．確率の小さい文字ほど早い段階でまとめられる．4.2 節の言葉でいえば，これは短い符号語から場所を詰めていくのとは逆向きで，いちばん狭い幅を確率の小さい二つに先に与え，その二つが占める場所をまとめて一つの幅として扱い直していく作り方である．

形式化: huffmanLength (ソース)

形式化上の注記. 形式化はこの手続きを，文字の集まりと重みの組を並べた多重集合の上の再帰として書いている．確率が等しいときの選び方を一つに決めるため，アルファベットに全順序を入れて優先順位を添えてあり，形式化が与える長さの組は，本文が許す組の一つにあたる．本節の形式化ポインタはどれもその一つについての主張で，選び方すべてを覆ってはいない．

例 4.6.2（五つの記号）. $𝐷 = 2$ ， $X = {1, 2, 3, 4, 5}$ とし， $𝑝 (1) = 𝑝 (2) = 0.25$ ， $𝑝 (3) = 0.2$ ， $𝑝 (4) = 𝑝 (5) = 0.15$ とする．どの Huffman 符号語長も $ℓ H (1) = ℓ H (2) = ℓ H (3) = 2$ ， $ℓ H (4) = ℓ H (5) = 3$ であり，平均符号長は $2.3$ である．同じ分布に対する Shannon 符号語長は $ℓ S (1) = ℓ S (2) = 2$ ， $ℓ S (3) = ℓ S (4) = ℓ S (5) = 3$ で，平均符号長は $2.5$ である．また $𝐻 2 (𝑋) = 2.2854 \dots$ である．

証明. 手続きを実行する．最初の併合では，最小の確率が $0.15$ でそれをもつのは $4$ と $5$ の二つだけだから， $𝑢, 𝑣$ はこの二つに決まる．まとめてできた文字の重みは $0.3$ で，残りは $0.25$ ， $0.25$ ， $0.2$ である．二度目の併合では最小が $0.2$ ，次が $0.25$ で， $0.25$ をもつ文字が二つあるためどちらを選んでもよいが， $1$ と $2$ を入れ替えるだけなので得られる長さの組は変わらない． $3$ と $1$ をまとめたとすると重みは $0.45$ で，残りは $0.25$ （文字 $2$ ）と $0.3$ （ $4$ と $5$ の組）である．三度目の併合ではこの二つがまとめられて重み $0.55$ になり，このとき残る文字は ${3, 1}$ のまとまりと ${2, 4, 5}$ のまとまりの二つである．ここから定義 4.6.1 の再帰を巻き戻す．文字が二つになった段では，どちらのまとまりにも値 $1$ が与えられる．一つ手前の段に戻ると， ${2, 4, 5}$ を分けた文字 $2$ と ${4, 5}$ のまとまりの値が $1 + 1 = 2$ になり， ${3, 1}$ の値は $1$ のままである．さらに一つ戻ると， ${3, 1}$ を分けた文字 $3$ と文字 $1$ の値が $1 + 1 = 2$ になる．最初の段まで戻ると， ${4, 5}$ を分けた文字 $4$ と文字 $5$ の値が $2 + 1 = 3$ になる．

値を計算する．平均符号長は

2 \times (0.25 + 0.25 + 0.2) + 3 \times (0.15 + 0.15) = 1.4 + 0.9 = 2.3

である．Shannon 符号語長は定義 4.4.1 より $⌈ l o g 2 4 ⌉ = 2$ ， $⌈ l o g 2 5 ⌉ = 3$ ， $⌈ l o g 2 (1 / 0.15) ⌉ = 3$ （ $l o g 2 5 = 2.3219 \dots$ ， $l o g 2 (1 / 0.15) = 2.7369 \dots$ ）で，その平均符号長は $2 \times 0.5 + 3 \times 0.5 = 2.5$ である．エントロピーは定義 4.3.1 より

𝐻 2 (𝑋) = 2 \times 0.25 l o g 2 4 + 0.2 l o g 2 5 + 2 \times 0.15 l o g 2 1 0.15 = 2.2854 \dots

である． $◼$

例 4.6.3（確率が $2$ の冪であるとき）. $𝐷 = 2$ ， $X = {1, 2, 3, 4}$ とし， $𝑝 (1) = 1 / 2$ ， $𝑝 (2) = 1 / 4$ ， $𝑝 (3) = 𝑝 (4) = 1 / 8$ とする．どの Huffman 符号語長も $ℓ H (1) = 1$ ， $ℓ H (2) = 2$ ， $ℓ H (3) = ℓ H (4) = 3$ であり，平均符号長は $7 / 4$ である．

証明. 最小の確率は $1 / 8$ で，それをもつのは $3$ と $4$ の二つだけだから，最初の併合はこの二つに決まる．できたまとまりの重みは $1 / 4$ で，残りは $1 / 2$ と $1 / 4$ （文字 $2$ ）である．二度目の併合では重み $1 / 4$ の二つがまとめられ，どちらを $𝑢$ にとっても同じ組がまとまるので，重み $1 / 2$ のまとまりと文字 $1$ が残る．再帰を巻き戻すと，文字が二つになった段でこの二つに値 $1$ が与えられ，一つ手前に戻ると文字 $2$ と ${3, 4}$ のまとまりの値が $2$ になり，最初の段まで戻ると文字 $3$ と文字 $4$ の値が $3$ になる．文字 $1$ の値は $1$ のままである．平均符号長は $12 \cdot 1 + 14 \cdot 2 + 18 \cdot 3 + 18 \cdot 3 = 74$ である． $◼$

例 4.6.3 の長さの組は例 4.1.4 の符号の符号語長そのもので，例 4.2.3 が定理 4.2.2 の構成でたどりついた組でもある．確率がちょうど $2$ の冪の逆数に並んでいるので定理 4.3.2 の等号が成り立ち，平均符号長 $7 / 4$ は $𝐻 2 (𝑋)$ に等しい．手続きが $𝐻 2 (𝑋)$ そのものに届いたということである．

命題 4.6.4. $X$ を $2$ 個以上の文字からなる有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．定義 4.6.1 のどの Huffman 符号語長 $ℓ H$ についても，すべての $𝑥$ で $ℓ H (𝑥) \geq 1$ であり，

\sum 𝑥 \in X 2 - ℓ H (𝑥) = 1

が成り立つ．したがって $X$ 上の二元語頭符号で，各 $𝑥$ の符号語長が $ℓ H (𝑥)$ に等しいものが存在する．

証明（アルファベットの大きさについての帰納法）. $| X | = 2$ のときは両方の値が $1$ で，和は $2 - 1 + 2 - 1 = 1$ である．

$| X | \geq 3$ とし，定義 4.6.1 の $𝑢$ ， $𝑣$ ， $𝑤$ ， $X'$ ， $𝑝'$ ， $ℓ'$ をとる． $𝑝'$ はすべての点で正であり $| X' | = | X | - 1 \geq 2$ だから， $ℓ'$ に帰納法の仮定が使える． $𝑧 \neq 𝑢, 𝑣$ については $ℓ H (𝑧) = ℓ' (𝑧) \geq 1$ であり， $ℓ H (𝑢) = ℓ H (𝑣) = ℓ' (𝑤) + 1 \geq 2$ である．和は

\sum 𝑥 \in X 2 - ℓ H (𝑥) = \sum 𝑧 \neq 𝑢, 𝑣 2 - ℓ' (𝑧) + 2 \cdot 2 - (ℓ' (𝑤) + 1) = \sum 𝑦 \in X' 2 - ℓ' (𝑦) = 1

となる（ $2$ 個ぶんの $2 - (ℓ' (𝑤) + 1)$ が $2 - ℓ' (𝑤)$ にまとまる）．

最後の主張は，得られた $ℓ H$ に定理 4.2.2 を当てれば従う． $◼$

形式化: $ℓ H (𝑥) \geq 1$ にあたる huffmanLength_pos (ソース)， $\sum 𝑥 2 - ℓ H (𝑥) = 1$ にあたる huffmanLength_kraft_eq_one，語頭符号の存在 exists_huffman_prefix_code (ソース)

定義 4.6.5（Huffman 符号）. $X$ を $2$ 個以上の文字からなる有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．Huffman 符号語長（定義 4.6.1）を符号語長にもつ二元語頭符号を Huffman 符号 と呼ぶ．命題 4.6.4 より，そのような符号は存在する．

Huffman 符号は一つに定まらない．符号語の中身は定理 4.2.2 の構成の取り方に依り，長さの組 $ℓ H$ のほうも定義 4.6.1 の $𝑢$ と $𝑣$ の選び方に依る． $4$ 文字の確率が $0.4$ ， $0.2$ ， $0.2$ ， $0.2$ のときがそうで，長さの組は $2, 2, 2, 2$ にも $1, 3, 3, 2$ にもなる．どちらでも平均符号長は $2$ である．選び方に依らずこの値が定まることは，定理 4.6.9 から従う．

和がちょうど $1$ になることには意味がある．4.2 節の木の言葉でいえば，場所を一つも余らせずに使いきったということである．場所が余っていればどれかの符号語を $1$ 文字縮められるので，余らせる符号は最良ではありえない．この観察を最良の長さの組がもつ性質として書き下すために，比べる相手に名前を付けておく．

定義 4.6.6（候補）. $X$ を有限アルファベットとする． $X$ 上の長さの組 $ℓ$ （定義 4.2.4）が，すべての $𝑥 \in X$ で $ℓ (𝑥) \geq 1$ を満たし，かつ

\sum 𝑥 \in X 2 - ℓ (𝑥) \leq 1

を満たすとき， $ℓ$ を $X$ 上の候補と呼ぶ．

定義 4.2.4 の長さの組は $0$ 以上の整数値をとる関数だから，候補は $1$ 以上の整数値をとる．系 4.2.5 を $𝐷 = 2$ に当てると，候補とはちょうど二元語頭符号の符号語長の組のことである．補題 4.6.7 は，場所を余らせる長さの組が最良ではないことを，候補の言葉で書き下したものである．

最良の長さの組がもつ性質

補題 4.6.7. $X$ を $2$ 個以上の文字からなる有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする． $𝑢 \in X$ を $𝑝 (𝑢) \leq 𝑝 (𝑧)$ がすべての $𝑧 \in X$ で成り立つ文字， $𝑣 \in X ∖ {𝑢}$ を $𝑝 (𝑣) \leq 𝑝 (𝑧)$ が $𝑢$ 以外のすべての $𝑧$ で成り立つ文字とする． $X$ 上の候補（定義 4.6.6） $ℓ$ すべてにわたる $\sum 𝑥 𝑝 (𝑥) ℓ (𝑥)$ の最小値は存在し，しかもそれを達成する候補のうちには

ℓ (𝑢) = ℓ (𝑣) = m a x 𝑧 \in X ℓ (𝑧)

を満たすものがある．

証明. 最小値が存在することを示す．系 4.4.3 より Shannon 符号語長 $ℓ S$ はすべての $𝑥$ で $1$ 以上であり，命題 4.4.2 よりその Kraft 和は $1$ 以下だから， $ℓ S$ は候補である． $𝐵 : = \sum 𝑥 𝑝 (𝑥) ℓ S (𝑥)$ とおくと，最小を探すのは $\sum 𝑥 𝑝 (𝑥) ℓ (𝑥) \leq 𝐵$ を満たす候補の中だけでよい．この条件のもとでは各項が非負なので $𝑝 (𝑥) ℓ (𝑥) \leq 𝐵$ であり， $𝑝 (𝑥) > 0$ だから $ℓ (𝑥) \leq 𝐵 / 𝑝 (𝑥)$ となる．候補の値は $1$ 以上の整数だから， $ℓ (𝑥)$ のとりうる値は文字ごとに有限個で，そのような候補は有限個しかない．空でない有限集合の上の最小値だから，最小値が存在する．

値の入れ替えが何をするかを見る． $ℓ$ を候補， $𝑧, 𝑧' \in X$ とし， $ℓ$ の $𝑧$ での値と $𝑧'$ での値を入れ替えたものを $˜ ℓ$ と書く．値の多重集合は変わらないので， $˜ ℓ$ も候補である．平均符号長の差は

\sum 𝑥 𝑝 (𝑥) ˜ ℓ (𝑥) - \sum 𝑥 𝑝 (𝑥) ℓ (𝑥) = (𝑝 (𝑧) - 𝑝 (𝑧')) (ℓ (𝑧') - ℓ (𝑧))

となる．したがって $𝑝 (𝑧) \leq 𝑝 (𝑧')$ かつ $ℓ (𝑧) \leq ℓ (𝑧')$ ならば差は $0$ 以下であり， $ℓ$ が最小を達成していれば $˜ ℓ$ も達成する．

最大値を二つ以上の文字が達成することを示す． $ℓ$ を最小を達成する候補とし， $𝑚 : = m a x 𝑧 ℓ (𝑧)$ を達成する文字がただ一つ，それを $𝑡$ とする． $| X | \geq 2$ だから他の文字があり，その値は $1$ 以上 $𝑚$ 未満なので $𝑚 \geq 2$ である．ここで

2 𝑚 \sum 𝑧 2 - ℓ (𝑧) = \sum 𝑧 2 𝑚 - ℓ (𝑧)

を見ると， $𝑧 = 𝑡$ の項は $1$ で，他の項は $𝑚 - ℓ (𝑧) \geq 1$ より偶数だから，右辺は奇数である．Kraft の不等式より右辺は $2 𝑚$ 以下で， $𝑚 \geq 1$ より $2 𝑚$ は偶数だから，右辺は $2 𝑚 - 1$ 以下である．すなわち $\sum 𝑧 2 - ℓ (𝑧) \leq 1 - 2 - 𝑚$ である．そこで $𝑡$ での値だけを $𝑚 - 1$ に取り替えた長さの組を考えると，その値は $1$ 以上で，Kraft の和は $\sum 𝑧 2 - ℓ (𝑧) + 2 - 𝑚 \leq 1$ となるから候補であり，平均符号長は $𝑝 (𝑡) > 0$ だけ小さい．これは $ℓ$ の最小性に反する．よって最大値を達成する文字は二つ以上ある．

あとは最長の位置へ $𝑢$ と $𝑣$ を順に運ぶだけである．入れ替えても平均符号長は増えないのだから，最長の値をもつ文字と入れ替えていけばよい．以下はその確認である．

まず $𝑢$ を移す． $ℓ$ を最小を達成する候補とし， $𝑚 : = m a x 𝑧 ℓ (𝑧)$ とおく．前段より $𝑚$ を達成する文字は二つ以上あるので，そのうち相異なる二つを $𝑎, 𝑏$ とする． $𝑢 \notin {𝑎, 𝑏}$ のときは， $𝑝 (𝑢) \leq 𝑝 (𝑎)$ かつ $ℓ (𝑢) \leq 𝑚 = ℓ (𝑎)$ だから， $𝑢$ と $𝑎$ の値を入れ替えても最小性は保たれる．入れ替えたあと $ℓ (𝑢) = 𝑚$ であり， $𝑏$ は $𝑢$ とも $𝑎$ とも異なるので $ℓ (𝑏) = 𝑚$ のままである． $𝑢 \in {𝑎, 𝑏}$ のときは名前を付け替えて $𝑎 = 𝑢$ としてよく，はじめから $ℓ (𝑢) = 𝑚$ かつ $ℓ (𝑏) = 𝑚$ である．どちらの場合も， $ℓ (𝑢) = 𝑚$ であり， $𝑢$ と異なる文字 $𝑏$ が $ℓ (𝑏) = 𝑚$ を満たす．

次に $𝑣$ を扱う． $𝑣 = 𝑏$ ならすでに $ℓ (𝑣) = 𝑚$ である． $𝑣 \neq 𝑏$ のときは， $𝑏 \neq 𝑢$ より $𝑝 (𝑣) \leq 𝑝 (𝑏)$ であり， $ℓ (𝑣) \leq 𝑚 = ℓ (𝑏)$ だから， $𝑣$ と $𝑏$ の値を入れ替えても最小性は保たれる．入れ替えたあと $ℓ (𝑣) = 𝑚$ であり， $𝑢$ は $𝑣$ とも $𝑏$ とも異なるので $ℓ (𝑢) = 𝑚$ のままである．値の多重集合は入れ替えで変わらないから最大値も $𝑚$ のままで， $ℓ (𝑢) = ℓ (𝑣) = m a x 𝑧 ℓ (𝑧)$ を満たす候補が最小を達成している． $◻$

奇偶を見た段は，最長の符号語の隣が空いていることを見つけている．最長の値 $𝑚$ をもつ文字が $𝑡$ ただ一つだとすると，他の符号語はどれも深さ $𝑚$ より浅いので，それが深さ $𝑚$ で塞ぐ場所は偶数個ずつまとまっており， $𝑡$ の場所と対になる隣の場所を塞ぐなら $𝑡$ の場所も一緒に塞ぐことになる． $𝑡$ の場所は $𝑡$ が使っているのだから，隣は空いている．空いているなら $𝑡$ の符号語を $1$ 文字縮めて，対になる二つの場所をまとめて使える．縮めれば平均符号長は $𝑝 (𝑡)$ だけ小さくなるから，最長を一つの文字しか達成しない長さの組は最小を達成していない．

形式化上の注記. 補題 4.6.7 に対応する単独の宣言はない．形式化にも値の入れ替えによる正規化の段があり，swap_normalization_strong (InformationTheory/Shannon/Huffman/StrongForm.lean) がそれである．そこで扱うのは「確率が最小の二文字の長さを等しくそろえる」という部分だけで，本文の補題とは切り取り方が違う．

併合が最小値を引き継ぐ

補題 4.6.8. $X$ を $3$ 個以上の文字からなる有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする． $𝑢 \in X$ と $𝑣 \in X ∖ {𝑢}$ を補題 4.6.7 と同じ条件でとり， $𝑢$ と $𝑣$ を新しい $1$ 文字 $𝑤$ に置き換えたアルファベットを $X'$ ，その上の分布を $𝑝' (𝑤) : = 𝑝 (𝑢) + 𝑝 (𝑣)$ ， $𝑝' (𝑧) : = 𝑝 (𝑧)$ （ $𝑧 \neq 𝑤$ ）とする． $X$ 上の候補（定義 4.6.6） $ℓ$ すべてにわたる $\sum 𝑥 𝑝 (𝑥) ℓ (𝑥)$ の最小値を $𝐿 *$ ， $X'$ と $𝑝'$ について同じように定めた最小値を $𝐿' *$ と書くと

𝐿 * = 𝐿' * + 𝑝 (𝑢) + 𝑝 (𝑣)

が成り立つ．

証明. どちらの最小値も，補題 4.6.7 より存在する（ $| X' | = | X | - 1 \geq 2$ であり， $𝑝'$ もすべての点で正である）．

$𝐿 * \leq 𝐿' * + 𝑝 (𝑢) + 𝑝 (𝑣)$ を示す． $X'$ 上で最小を達成する長さの組 $ℓ'$ をとり， $X$ 上の長さの組 $ℓ$ を $ℓ (𝑢) : = ℓ' (𝑤) + 1$ ， $ℓ (𝑣) : = ℓ' (𝑤) + 1$ ， $ℓ (𝑧) : = ℓ' (𝑧)$ （ $𝑧 \neq 𝑢, 𝑣$ ）で定める．値はすべて $1$ 以上で，

\sum 𝑥 2 - ℓ (𝑥) = \sum 𝑧 \neq 𝑢, 𝑣 2 - ℓ' (𝑧) + 2 \cdot 2 - (ℓ' (𝑤) + 1) = \sum 𝑦 \in X' 2 - ℓ' (𝑦) \leq 1

だから Kraft の不等式も満たす．平均符号長は

\sum 𝑥 𝑝 (𝑥) ℓ (𝑥) = \sum 𝑧 \neq 𝑢, 𝑣 𝑝' (𝑧) ℓ' (𝑧) + (𝑝 (𝑢) + 𝑝 (𝑣)) (ℓ' (𝑤) + 1) = 𝐿' * + 𝑝 (𝑢) + 𝑝 (𝑣)

である．最小値はこれ以下だから，主張の不等式を得る．

$𝐿' * \leq 𝐿 * - 𝑝 (𝑢) - 𝑝 (𝑣)$ を示す．補題 4.6.7 より， $X$ 上で最小を達成し $ℓ (𝑢) = ℓ (𝑣) = 𝑚 : = m a x 𝑧 ℓ (𝑧)$ を満たす長さの組 $ℓ$ がとれる． $𝑚 \geq 2$ である．というのも $𝑚 = 1$ ならすべての値が $1$ になり，Kraft の和が $| X | / 2$ となって $| X | \leq 2$ を強いるが，これは仮定に反するからである．そこで $X'$ 上の長さの組 $ℓ'$ を $ℓ' (𝑤) : = 𝑚 - 1$ ， $ℓ' (𝑧) : = ℓ (𝑧)$ （ $𝑧 \neq 𝑤$ ）で定めると，値はすべて $1$ 以上で

\sum 𝑦 \in X' 2 - ℓ' (𝑦) = \sum 𝑧 \neq 𝑢, 𝑣 2 - ℓ (𝑧) + 2 \cdot 2 - 𝑚 = \sum 𝑥 \in X 2 - ℓ (𝑥) \leq 1

だから Kraft の不等式を満たす．平均符号長は

\sum 𝑦 𝑝' (𝑦) ℓ' (𝑦) = \sum 𝑧 \neq 𝑢, 𝑣 𝑝 (𝑧) ℓ (𝑧) + (𝑝 (𝑢) + 𝑝 (𝑣)) (𝑚 - 1) = 𝐿 * - 𝑝 (𝑢) - 𝑝 (𝑣)

である．最小値はこれ以下だから，主張の不等式を得る．

二つを合わせて等号が従う． $◻$

形式化上の注記. 補題 4.6.8 に対応する単独の宣言はない．形式化は最小値そのものを扱わず，任意の候補と Huffman 符号語長を直接比べる形で最適性へ進む．

補題 4.6.8 は，最小化の問題が一段小さい同じ問題に化けることを言っている．確率が最小の二文字については，その二つが同じ長さの最長の符号語をもつような最良の符号を必ずとれる（補題 4.6.7）．ならばその二文字は一つにまとめてしまってよく，まとめたぶんだけ符号語が $1$ 文字伸びる代償として $𝑝 (𝑢) + 𝑝 (𝑣)$ を払う．この代償は長さの組の選び方に依らない定数なので，最小化には関わらない．手続きが確率の小さい二つをまとめていくのは，この読み替えを繰り返しているということである．

最適性

定理 4.6.9（Huffman 符号の最適性）. $X$ を $2$ 個以上の文字からなる有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．定義 4.6.1 のどの Huffman 符号語長 $ℓ H$ についても， $X$ 上のどの候補（定義 4.6.6） $ℓ$ に対しても

\sum 𝑥 \in X 𝑝 (𝑥) ℓ H (𝑥) \leq \sum 𝑥 \in X 𝑝 (𝑥) ℓ (𝑥)

である．

証明（アルファベットの大きさについての帰納法）. $| X | = 2$ のとき， $ℓ H$ は両方の文字で $1$ だから左辺は $1$ である．右辺は $ℓ (𝑥) \geq 1$ より $1$ 以上である．

$| X | \geq 3$ とし，定義 4.6.1 の $𝑢$ ， $𝑣$ ， $𝑤$ ， $X'$ ， $𝑝'$ ， $ℓ'$ をとる． $ℓ'$ は $(X', 𝑝')$ の Huffman 符号語長であり， $| X' | = | X | - 1 \geq 2$ で $𝑝'$ はすべての点で正だから，帰納法の仮定より $ℓ'$ は $X'$ 上のどの候補にも負けない．命題 4.6.4 より $ℓ'$ 自身も候補だから， $\sum 𝑦 𝑝' (𝑦) ℓ' (𝑦)$ は補題 4.6.8 の $𝐿' *$ に等しい．定義 4.6.1 の作り方から

\sum 𝑥 𝑝 (𝑥) ℓ H (𝑥) = \sum 𝑧 \neq 𝑢, 𝑣 𝑝' (𝑧) ℓ' (𝑧) + (𝑝 (𝑢) + 𝑝 (𝑣)) (ℓ' (𝑤) + 1) = 𝐿' * + 𝑝 (𝑢) + 𝑝 (𝑣)

であり，補題 4.6.8 よりこれは $𝐿 *$ に等しい． $𝐿 *$ は候補にわたる最小値だから，どの候補 $ℓ$ に対しても $\sum 𝑥 𝑝 (𝑥) ℓ H (𝑥) = 𝐿 * \leq \sum 𝑥 𝑝 (𝑥) ℓ (𝑥)$ である． $◼$

形式化: huffmanLength_optimal (ソース)

系 4.6.10. $X$ を $2$ 個以上の文字からなる有限アルファベット， $𝑋$ を $X$ 上に分布 $𝑝$ をもつ確率変数で，すべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．このとき定義 4.6.1 のどの Huffman 符号語長 $ℓ H$ についても

𝐻 2 (𝑋) \leq \sum 𝑥 \in X 𝑝 (𝑥) ℓ H (𝑥) < 𝐻 2 (𝑋) + 1

である．

証明. 左側は，命題 4.6.4 より $ℓ H$ が Kraft の不等式を満たすので，定理 4.3.2 から従う．

右側を見る．系 4.4.3 より Shannon 符号語長 $ℓ S$ はすべての $𝑥$ で $1$ 以上であり，命題 4.4.2 より Kraft の不等式を満たすから，定理 4.6.9 を $ℓ = ℓ S$ に当てて $\sum 𝑥 𝑝 (𝑥) ℓ H (𝑥) \leq \sum 𝑥 𝑝 (𝑥) ℓ S (𝑥)$ を得る．定理 4.4.4 より右辺は $𝐻 2 (𝑋) + 1$ 未満である． $◼$

形式化上の注記. 系 4.6.10 に対応する単独の宣言はない．左側は，命題 4.6.4 の形式化のうち huffmanLength_kraft_le_one (InformationTheory/Shannon/Huffman/KraftSum.lean) を，定理 4.3.2 の形式化 entropyD_le_expectedLength_of_kraft (InformationTheory/Shannon/ShannonCode/Basic.lean) と合わせた形になる．右側は定理 4.6.9 の形式化と定理 4.4.4 の形式化を合わせた形だが，前者が Shannon 符号語長を比べる相手として受け取るには，それが $1$ 以上であることが要り，それを与える宣言はない．

本章の問いはこれで閉じた．一意復号可能などんな符号でも平均符号長は $𝐻 𝐷 (𝑋)$ を下回れず（定理 4.3.2，系 4.5.2），アルファベットが $2$ 文字以上ですべての記号の確率が正なら $𝐻 𝐷 (𝑋) + 1$ 未満で済ませる符号があり（系 4.4.3，定理 4.4.4）， $𝐷 = 2$ のときは同じ仮定のもとで，最良の符号を手続きで作れる（命題 4.6.4 が符号を与え，定理 4.6.9 がその最良性を保証する）．例 4.4.5 で Shannon 符号が最良でない場合を見たが，その「最良」がどこにあるかは，確率を小さいものから二つずつまとめていくだけで決まる．エントロピーが答えるのは幅 $1$ までで，その幅の中で最良の平均符号長がどこに落ちるかは定義 4.6.1 の手続きが答える，というのが本章の結論である．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．