ハフマン符号｜情報理論

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

📎 前提：無歪み符号化とKraft不等式、シャノンの情報源符号化定理　|　次：算術符号とユニバーサル符号

要点（BLUF）

ハフマン符号 は、各記号の確率が与えられたとき 平均符号長を最小化する接頭符号（記号ごとに整数 bit を割り当てる中で最適）。
アルゴリズム：確率最小の2記号を併合して新ノードにする操作を繰り返し、符号木を葉から根へボトムアップに構成する。貪欲法。
性能： $H\le L_{\text{Huffman}} < H+1$ 。シャノン符号より短く（または同等）、ブロック化すれば $H$ に収束。ただし整数長ゆえ1記号符号化では原理的に「+1」未満の無駄が残る（それを消すのが算術符号、算術符号とユニバーサル符号）。

1. アルゴリズム（ボトムアップの貪欲法）

すべての記号を、確率を重みとする葉ノードとして用意する。
重み最小の2つのノードを取り出し、それらを子に持つ新ノード（重み＝子の和）を作る。一方の枝に 0、他方に 1 を割り当てる。
ノードが1つ（根）になるまで 2 を繰り返す。
根から各葉へのパスのビット列が、その記号の符号語。

直観：確率が低い記号ほど木の深く（長い符号）に、高い記号ほど浅く（短い符号）に配置される。最も稀な2記号を最初に併合するので、それらが最も深くなります。優先度付きキュー（ヒープ）で効率よく実装できます。

graph TD
  root["根 1.0"] -->|"1"| a["a 0.4"]
  root -->|"0"| n3["0.6"]
  n3 -->|"0"| n1["bc 0.4"]
  n3 -->|"1"| n2["de 0.2"]
  n1 -->|"0"| b["b 0.2"]
  n1 -->|"1"| c["c 0.2"]
  n2 -->|"0"| d["d 0.1"]
  n2 -->|"1"| e["e 0.1"]

2. 最適性

ハフマン符号が最適である理由は2つの観察から：(a) 最適符号では確率が低い記号ほど符号長が長い（でなければ入れ替えて改善できる）、(b) 最適符号木で最も深い2葉は兄弟にできる（最も確率の低い2記号）。この2記号を1つに併合した縮小問題の最適符号に、併合した記号を展開すると元の最適符号が得られる——帰納法で最適性が言えます。「最も稀な2つを束ねる」貪欲操作が、各段階で最適性を保つわけです。

3. コード：ハフマン符号の構成と最適性（底2, bit）

5記号の情報源でハフマン符号を作り、平均長がエントロピー以上シャノン符号以下になることを確かめます。

import heapq, numpy as np
def huffman(prob):  # prob: dict symbol->p
    # [重み, 一意カウンタ, [記号, 符号語], ...] をヒープで管理
    heap=[[p,i,[s,""]] for i,(s,p) in enumerate(prob.items())]
    heapq.heapify(heap); cnt=len(heap)
    while len(heap)>1:
        lo=heapq.heappop(heap); hi=heapq.heappop(heap)
        for pair in lo[2:]: pair[1]='0'+pair[1]   # 低確率側に 0
        for pair in hi[2:]: pair[1]='1'+pair[1]   # 高確率側に 1
        heapq.heappush(heap,[lo[0]+hi[0],cnt]+lo[2:]+hi[2:]); cnt+=1
    return {s:code for s,code in heap[0][2:]}

p={'a':0.4,'b':0.2,'c':0.2,'d':0.1,'e':0.1}
H=-sum(pi*np.log2(pi) for pi in p.values())
code=huffman(p)
L=sum(p[s]*len(code[s]) for s in p)
kraft=sum(2**(-len(code[s])) for s in p)
shannon_len={s:int(np.ceil(-np.log2(p[s]))) for s in p}
Ls=sum(p[s]*shannon_len[s] for s in p)
print(f"確率: {p}")
print(f"ハフマン符号: { {s:code[s] for s in p} }")
print(f"符号語長: { {s:len(code[s]) for s in p} }")
print(f"エントロピー H        = {H:.4f} bit")
print(f"ハフマン平均長 L_H    = {L:.4f} bit  (Kraft={kraft:.3f})")
print(f"シャノン平均長 L_S    = {Ls:.4f} bit")
print(f"最適性: H <= L_H <= L_S < H+1 : {H<=L<=Ls<H+1}")
print(f"冗長度 L_H - H = {L-H:.4f} bit/記号")

出力：

確率: {'a': 0.4, 'b': 0.2, 'c': 0.2, 'd': 0.1, 'e': 0.1}
ハフマン符号: {'a': '11', 'b': '00', 'c': '01', 'd': '100', 'e': '101'}
符号語長: {'a': 2, 'b': 2, 'c': 2, 'd': 3, 'e': 3}
エントロピー H        = 2.1219 bit
ハフマン平均長 L_H    = 2.2000 bit  (Kraft=1.000)
シャノン平均長 L_S    = 2.8000 bit
最適性: H <= L_H <= L_S < H+1 : True
冗長度 L_H - H = 0.0781 bit/記号

出力の意味：確率の高い $a$ は2 bit、稀な $d,e$ は3 bit と、確率に応じて符号長が振り分けられています。ハフマン平均長 $2.20$ bit はエントロピー $2.1219$ bit のすぐ上で、冗長度はわずか $0.078$ bit/記号。一方、素朴なシャノン符号 $\lceil-\log_2 p\rceil$ は $2.80$ bit と無駄が大きい——同じ確率に対してハフマンの方が確実に短い（または同等）。Kraft 和が $1.000$ で木を使い切っており、これ以上1記号単位では縮められません。残る $0.078$ bit の無駄を消すには、記号をまとめる（ブロックハフマン）か算術符号が要ります。

4. 数式の直観的意味

ハフマンの冗長度 $L_H-H$ は、確率が2の冪からどれだけずれているかで決まります。 $p_i=2^{-l_i}$ ぴったりなら $L_H=H$ （無駄ゼロ）、ずれるほど整数長への丸めで損が出ます。だから「確率が偏っているほど（最大確率が大きいほど）1記号符号化の無駄が目立つ」。極端な例として $p=\{0.99,0.01\}$ では $H\approx0.08$ bit なのにハフマンは必ず1 bit/記号——12倍以上の無駄。これがブロック化や算術符号（算術符号とユニバーサル符号）が必要になる典型場面です。

⚠️ よくある誤解

「ハフマン符号は一意」ではない：併合時の 0/1 の割り当てや同確率の選び方で複数の符号木がありえます。**平均長は同じ（最適）**ですが符号語は異なりえます。
「ハフマンは常に最良の圧縮」ではない：記号ごとに整数 bit を割り当てる中では最適ですが、整数長の制約があるため算術符号に負けます。確率が未知・非定常なら適応型やユニバーサル符号（算術符号とユニバーサル符号）が有利。
「冗長度は必ず小さい」ではない：1記号あたり最大1 bit 近く無駄になりえます（偏った分布）。ブロック化で薄めます。
「ハフマン符号は接頭符号でない場合もある」ではない：木の葉に対応するので常に接頭符号＝瞬時復号可能です。

対応シミュレーション

本文のコードでハフマン構成と $H\le L_H\le L_S<H+1$ を実証済み。