なぜ貪欲戦略は最適なのか
ハフマンアルゴリズムは貪欲アルゴリズムです: 各ステップで局所最適な選択を行い（最も安い2つのノードをマージ）先読みしません。貪欲アルゴリズムは常に全体最適ではありません — しかしここではそうです。
最適性の議論
符号Cが最小平均長Lを持つと仮定します。最も低い確率を持つ2つの記号、p_aとp_bを考えます。最適な符号では、これら2つの記号は木の最深レベルで兄弟葉として現れる必要があります。なぜですか？
親を共有しなければ、より深い記号を短い符号と交換できます — Lを減らします。したがって、最深葉は最も確率の低い記号である必要があります。
aとbをメタ記号abに結合すると（p_ab = p_a + p_b）、アルファベットが1つ減った縮小問題での最適符号は正確に縮小問題上のハフマン符号です。帰納法が議論を完成させます。
幾何学的見方
ハフマンアルゴリズムはバイナリツリーをボトムアップで構築し、最も確率の低い記号を最大の深さに配置します。これはΣ p_i · depth(i) = Lを最小化します。
同等の見方: 各葉の重みがその確率である加重パス長を最小化するためにツリーの葉にラベルを割り当てています。
貪欲ステップの実行
確率: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1。合計 = 1.0 ✓
ステップ1: 最も低い2つ: C(0.2), D(0.1)。マージ → CD(0.3)。リスト: A(0.4), B(0.3), CD(0.3)。
ステップ2: 最も低い2つ: B(0.3), CD(0.3)（同値 — どちらでも有効）。マージ → BCD(0.6)。リスト: A(0.4), BCD(0.6)。
ステップ3: A(0.4), BCD(0.6)をマージ → root(1.0)。A=0, BCD=1を割り当て。
逆方向: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3)。
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 ビット。
符号長の分散
2つのハフマン符号は同じLを達成できますが、異なる符号長分布を持つことがあります。符号長の分散はこの広がりを測定します:
Var(l) = E[l²] − (E[l])²
ここでE[l] = L（平均符号長）、E[l²] = Σ p_i · l_i²。
分散が重要な理由:
1. バッファ要件。 リアルタイムデコーディングでは、各記号は可変ビット数を消費します。高分散は一部の記号が多くのビットを消費することを意味します — 常に完全な記号を読める入力バッファが必要です。
2. デコーディングレイテンシ。 高分散符号は長い最悪ケースデコーディングパスを持つ。低分散（茂みのような）符号は最悪ケースをより厳密に境界付けます。
3. ロバストネス。 高分散符号の失われたビットは、長い符号語を完全に再読する必要があるため、より多くの同期化ダメージを引き起こします。
ハミングの推奨: 複数の有効なハフマン符号が存在する場合（タイブレーク選択）、分散が低いものを選ぶ — 茂みのような木。
2つのツリーの分散を計算
p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1を使用し、符号A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
3記号ハフマン符号エンドツーエンド
完全なエンドツーエンド例: ハフマン符号を構築し、Lを計算し、Hを計算し、L ≥ Hを検証し、Varを計算。
ソース: p(X)=0.6, p(Y)=0.3, p(Z)=0.1。
ハフマン構築:
ステップ1: ソート済み: X(0.6), Y(0.3), Z(0.1)。最も低い2つ: Y(0.3), Z(0.1)。
マージ → YZ(0.4)。リスト: X(0.6), YZ(0.4)。
ステップ2: X(0.6), YZ(0.4)をマージ → root(1.0)。X=0, YZ=1を割り当て。
YZ → Y=10, Z=11。
符号: X=0 (l=1), Y=10 (l=2), Z=11 (l=2)。
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 ビット。
エントロピ: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 ビット。
L = 1.4 ≥ H = 1.295 ✓。L/H = 1.4/1.295 ≈ 1.081。エントロピから8.1%上。
分散: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2。Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24。
あなたの番: 完全なパイプライン
参照用のlog₂値: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678。