tecktom.com

出てくるもの (1)：Huffman 符号

2026年10月15日9分で読めますAI生成教科書『虎の巻』第1部 第5章 データ圧縮
目次
  1. Huffman の手続き
  2. Huffman 符号が最適である理由
  3. Huffman 符号を で読む
  4. 木下の層

AI 生成・木下が未勉強

相対エントロピーから情報と物理を組み立てる　第1部 第5章 §1.5.4　★★★ 平均符号長を最小にする符号の作り方。完全な符号の中で D(p ∥ qC)D(p\,\|\,q_C) を最小にする qCq_C を選ぶ手続きとして読める

Huffman の手続き

Shannon 符号は H/ln⁡2+1H/\ln2+1 ビット未満を保証するが、最小とは限らない。平均符号長を本当に最小にする符号は、Huffman が与えた次の手続きで作れる1D. A. Huffman (1952), Proceedings of the IRE 40, 1098–1101.下の脚注へ。

定義 1.5.9（Huffman の手続き）

記号が m≥2m\ge2 個あるとき、次を繰り返して符号の木を下から作る。

  1. 確率の最も小さい2つの記号（または節点）を選び、それらを子に持つ新しい節点を1つ作る。新しい節点の確率は2つの和とする。
  2. 選んだ2つを取り除き、新しい節点を加える。残りが1つ（根）になるまで 1 に戻る。

最後に、各節点から出る2本の枝に 00 と 11 を付ける。根から葉までの枝のラベルが符号語である。最小の確率が同じ値で並ぶときは、どれを選んでもよい。

例として、5つの記号が確率 p=(0.35, 0.25, 0.20, 0.12, 0.08)p=(0.35,\,0.25,\,0.20,\,0.12,\,0.08) で出る情報源を考える（図 1.5.2）。まず最小の 0.120.12 と 0.080.08 をまとめて 0.200.20 の節点を作る。次に最小の2つは 0.200.20（記号 cc）と 0.200.20（今作った節点）で、まとめて 0.400.40。残る 0.350.35、0.250.25、0.400.40 のうち小さい 0.350.35 と 0.250.25 をまとめて 0.600.60。最後に 0.600.60 と 0.400.40 をまとめて根になる。符号語は a:00a:00、b:01b:01、c:10c:10、d:110d:110、e:111e:111 で、平均符号長は

ℓˉ=2×(0.35+0.25+0.20)+3×(0.12+0.08)=2.20 ビット\bar\ell=2\times(0.35+0.25+0.20)+3\times(0.12+0.08)=2.20\ \text{ビット}

である。下界は H(p)/ln⁡2=2.153H(p)/\ln2=2.153 ビットで、差は 0.0470.047 ビットにすぎない。比べて、pp に合わせた Shannon 符号の長さは ⌈−log⁡2p⌉=(2,2,3,4,4)\lceil-\log_2p\rceil=(2,2,3,4,4) で、平均符号長は 2.602.60 ビットになる。

図

図 1.5.2　確率 (0.35,0.25,0.20,0.12,0.08)(0.35,0.25,0.20,0.12,0.08) の Huffman 符号の木。丸は手続きの途中で作った節点で、数字はその下の葉の確率の和。平均符号長は 2.202.20 ビット、下界 H(p)/ln⁡2H(p)/\ln2 は 2.1532.153 ビット。

Huffman 符号が最適である理由

補題 1.5.10（最適な符号の形）

記号を確率の大きい順に p1≥p2≥⋯≥pmp_1\ge p_2\ge\cdots\ge p_m と並べる。平均符号長が最小の語頭符号のうちに、次の3つを満たすものがある。

  1. (i) pi>pjp_i>p_j なら ℓi≤ℓj\ell_i\le\ell_j（出やすい記号ほど符号語が短い）。
  2. (ii) 最も長い符号語は2つ以上あり、同じ長さである。
  3. (iii) 確率の最も小さい2つの記号 m−1m-1、mm の符号語は、最後の1桁だけが違う（符号の木で兄弟の葉になる）。
証明

記号は有限個で、長さを mm 以下に限っても最小値は変わらない（それより長い符号語は木に分かれ道のない節点を含み、縮められる）ので、最小の平均符号長を実現する符号はある。その1つを CC とする。

(i) pi>pjp_i>p_j で ℓi>ℓj\ell_i>\ell_j なら、2つの符号語を入れ替えると平均符号長は (pi−pj)(ℓj−ℓi)<0(p_i-p_j)(\ell_j-\ell_i)<0 だけ変わって減り、最小性に反する。

(ii) 最も長い符号語の葉に兄弟の葉が無いと、その親の節点からは枝が1本しか出ていない。最後の1桁を消しても語頭符号のままなので、平均符号長が減って最小性に反する。よって最も長い符号語の葉には兄弟の葉があり、兄弟は同じ長さである。

(iii) (i) から、最も長い深さの葉には確率の最も小さい記号を置ける（確率が同じものどうしの入れ替えは平均符号長を変えない）。(ii) から最も深い葉は兄弟の組で現れるので、兄弟の2枚に記号 m−1m-1、mm を置き直せば、平均符号長を変えずに (iii) を満たす。

定理 1.5.11（Huffman 符号の最適性 ★★★）

Huffman の手続きで作った符号の平均符号長は、一意に復号できるすべての符号の平均符号長の最小値に等しい。

証明

記号の数 mm についての帰納法で示す。m=2m=2 では長さ (1,1)(1,1) が明らかに最小で、Huffman の手続きもこの長さを出す。mm 個の記号の分布 pp について、最小の2つ pm−1p_{m-1}、pmp_m を1つの記号にまとめた m−1m-1 個の分布 p′=(p1,…,pm−2,pm−1+pm)p'=(p_1,\dots,p_{m-2},p_{m-1}+p_m) を考える。p′p' の任意の語頭符号 C′C' から、まとめた記号の符号語の後ろに 00 と 11 を付けて pp の符号 CC を作ると、

ℓˉ(C)=ℓˉ(C′)+pm−1+pm(1.5.8)\bar\ell(C)=\bar\ell(C')+p_{m-1}+p_m\tag{1.5.8}

となる。逆に、補題 1.5.10 の (iii) を満たす pp の符号は、兄弟の2枚の葉を親の節点にまとめれば p′p' の符号になり、同じ関係 (1.5.8) が成り立つ。pm−1+pmp_{m-1}+p_m は符号によらない定数なので、(iii) を満たす pp の符号の中で ℓˉ(C)\bar\ell(C) を最小にすることは、p′p' の符号の中で ℓˉ(C′)\bar\ell(C') を最小にすることと同じである。補題から pp の最適な符号は (iii) を満たすものの中にあり、Huffman の手続きは最初の一手で pp を p′p' に縮め、残りは p′p' の Huffman 符号を作る。帰納法の仮定から p′p' の Huffman 符号は最適なので、pp の Huffman 符号も最適である。McMillan の不等式により、一意に復号できる符号まで広げても最小値は変わらない。

Huffman 符号を DD で読む

最適な符号は完全である（補題の (ii) の議論で、枝が1本しか出ていない節点があれば縮められる）。したがって最適な符号では K(C)=1K(C)=1 で、分解 (1.5.5) は (ln⁡2)ℓˉ(C)=H(p)+D(p ∥ qC)(\ln2)\bar\ell(C)=H(p)+D(p\,\|\,q_C) になる。H(p)H(p) は符号によらないので、平均符号長を最小にすることは、qC=2−ℓq_C=2^{-\ell} の形の分布（各確率が 22 の負べきで、和が 11）の中で、D(p ∥ qC)D(p\,\|\,q_C) を最小にするものを選ぶことと同じである。Huffman の手続きは、この離散的な最小化問題を、最小の2つをまとめる貪欲な操作の繰り返しで正確に解く。

この読み方では、Huffman 符号の平均符号長と下界の差（冗長度と呼ぶ）は、pp と「最も近い 22 の負べきの分布」との相対エントロピーそのものになる。図 1.5.2 の例では、qC=(14,14,14,18,18)q_C=(\tfrac14,\tfrac14,\tfrac14,\tfrac18,\tfrac18) で、D(p ∥ qC)/ln⁡2=0.047D(p\,\|\,q_C)/\ln2=0.047 ビットが差 2.20−2.1532.20-2.153 に一致する。

冗長度は 11 ビット未満だが、HH そのものが小さい情報源では無視することはできない。00 と 11 が確率 0.90.9、0.10.1 で出る情報源では H/ln⁡2=hb(0.1)/ln⁡2=0.469H/\ln2=h_{\mathrm b}(0.1)/\ln2=0.469 ビットなのに、記号が2つしかないので、どんな符号も長さ 11 の符号語を2つ使うしかなく、平均符号長は 11 ビットで、下界の2倍を超える。qCq_C は (12,12)(\tfrac12,\tfrac12) に固定されてしまい、p=(0.9,0.1)p=(0.9,0.1) に近づける余地がない。記号を1つずつ符号にする限りこの差は縮まらず、縮めるには記号をまとめてから符号にする必要がある（1.5.5節）。

例題 1.5.4　3つの等確率の記号と、2つずつまとめた符号 ★★

オリジナル3つの記号が等確率 13\tfrac13 で出る無記憶情報源を考える。

  1. Huffman 符号を作り、平均符号長と下界 log⁡23\log_23 の差を求めよ。その差が D(p ∥ qC)/ln⁡2D(p\,\|\,q_C)/\ln2 に等しいことを確かめよ。
  2. 記号を2つずつまとめた 99 個の記号（確率はどれも 19\tfrac19）に Huffman 符号を作り、元の記号1つあたりの平均符号長と下界の差を求めよ。
解答

(1) 最小の2つ（13\tfrac13 と 13\tfrac13）をまとめて 23\tfrac23、残りの 13\tfrac13 と 23\tfrac23 をまとめて根になる。長さは (1,2,2)(1,2,2) で、平均符号長は 13(1+2+2)=53=1.667\tfrac13(1+2+2)=\tfrac53=1.667 ビット。下界は log⁡23=1.585\log_23=1.585 ビットで、差は 0.08170.0817 ビット。qC=(12,14,14)q_C=(\tfrac12,\tfrac14,\tfrac14) なので

D(p ∥ qC)ln⁡2=13log⁡21/31/2+23log⁡21/31/4=13+23⋅2−log⁡23=53−log⁡23\frac{D(p\,\|\,q_C)}{\ln2}=\frac13\log_2\frac{1/3}{1/2}+\frac23\log_2\frac{1/3}{1/4}=\frac13+\frac23\cdot2-\log_23=\frac53-\log_23

となり、差と一致する。

(2) 等確率の 99 個では、Huffman の手続きは確率 19\tfrac19 の組を 29\tfrac29 に4回まとめ、残った 19\tfrac19 と 29\tfrac29 を 39\tfrac39 にまとめる、と進む。最後にできる木は、深さ 33 の葉が 77 枚、深さ 44 の葉が 22 枚の完全な木になる（Kraft 和 7⋅18+2⋅116=17\cdot\tfrac18+2\cdot\tfrac1{16}=1）。等確率なので、どの記号をどの葉に置いても平均符号長は変わらず、19(7⋅3+2⋅4)=299\tfrac19(7\cdot3+2\cdot4)=\tfrac{29}9 ビット。元の記号1つあたりは 2918=1.611\tfrac{29}{18}=1.611 ビットで、下界との差は 0.02610.0261 ビットに縮まる。2つずつまとめると、qCq_C の候補となる 22 の負べきの分布が細かくなり、一様分布 19\tfrac19 に近いもの（18\tfrac18 と 116\tfrac1{16} の組合せ）を選べるようになったので、差が小さくなった。

1　D. A. Huffman (1952), Proceedings of the IRE 40, 1098–1101.

木下の勉強ステータス

木下はまだこの記事を勉強していません。

AI（Claude）が書いた教材を、木下が勉強しながら公開しています。式と数値は検算していますが、誤りが残っているかもしれません。誤りのご指摘・削除のご依頼をいただければ直します。 連絡先：support@tecktom.com

目次

この記事が含まれている連載

連載AI生成教科書『虎の巻』授業とは別に、分野をまたいで気になったことを AI（Claude）が教材にし、木下が勉強しながら公開しています。上の段は AI が書いた本文、下の段は木下が勉強したあとに書いた文です。1787本の記事・木下 智貴
← AI生成教科書『虎の巻』の記事一覧へ