tecktom.com

この章のまとめ

2026年10月15日7分で読めますAI生成教科書『虎の巻』第1部 第5章 データ圧縮

AI 生成・木下が未勉強

相対エントロピーから情報と物理を組み立てる　第1部 第5章 §1.5.7　★★★ 圧縮の限界 HH と、分布を取り違えた代価 DD は、平均符号長の分解式1本から導かれる

この章では、符号語の長さの並び ℓ(x)\ell(x) を確率分布 qC(x)=2−ℓ(x)/K(C)q_C(x)=2^{-\ell(x)}/K(C) と読み替えた。これが分布として意味を持つのは、一意に復号できる符号では Kraft 和 K(C)K(C) が 11 以下になるからである（Kraft–McMillan の不等式）。同じ不等式から、平均符号長を最小にする問題では語頭符号に限ってよいこともわかった。

読み替えた結果、平均符号長は (ln⁡2)ℓˉ(C)=H(p)+D(p ∥ qC)−ln⁡K(C)(\ln2)\bar\ell(C)=H(p)+D(p\,\|\,q_C)-\ln K(C) と分かれる。第1部第3章の D≥0D\ge0 を当てると、圧縮の下界 ℓˉ≥H(p)/ln⁡2\bar\ell\ge H(p)/\ln2 ビットが出る。長さを ⌈−log⁡2q⌉\lceil-\log_2q\rceil に選んだ Shannon 符号は、pp に使うと (H+D(p ∥ q))/ln⁡2(H+D(p\,\|\,q))/\ln2 ビットから1ビット未満の範囲に入る。こうして D(p ∥ q)/ln⁡2D(p\,\|\,q)/\ln2 は、分布を qq と取り違えた代価のビット数という操作的な意味を持った。平均符号長を最小にする符号は Huffman の手続きで作れ、それは 22 の負べきの分布の中で D(p ∥ qC)D(p\,\|\,q_C) を最小にする qCq_C を選ぶことにあたる。記号を nn 個まとめると、1記号あたりの最小の長さは H/ln⁡2H/\ln2 と H/ln⁡2+1/nH/\ln2+1/n の間に入り、固定長の符号でも典型集合を使えば率 HH で誤り確率を 00 にできる（情報源符号化定理）。

この巻の背骨の言葉でまとめると、データ圧縮で比べている2つの分布は「情報源の分布 pp」と「符号が見込んでいる分布 qCq_C」で、当てている性質は DD の非負性である。次の章（第1部第6章）では、比べる2つの分布を「通信路の入力と出力の結合分布」と「それらが独立だとした分布」に替え、相互情報量 I(X;Y)=D(pXY ∥ pXpY)I(X;Y)=D(p_{XY}\,\|\,p_Xp_Y) の最大値として通信路容量を出す。圧縮が「冗長な部分を削る」操作なら、通信路符号化は「雑音に備えて冗長な部分を足す」操作で、どちらの限界も同じ相対エントロピーの非負性から導かれる。

総合問題　4つの記号の情報源を圧縮する ★★★

オリジナル4つの記号 a,b,c,da,b,c,d が確率 p=(0.5, 0.2, 0.2, 0.1)p=(0.5,\,0.2,\,0.2,\,0.1) で独立に出る無記憶情報源 XX を考える。

  1. (1) H(X)/ln⁡2H(X)/\ln2 を求めよ。また pp に合わせた Shannon 符号の長さと平均符号長を求め、定理 1.5.8 の範囲に入ることを確かめよ。（使う道具：第1部第2章のエントロピー、この章の 1.5.3節）
  2. (2) Huffman 符号を作り、平均符号長と下界の差が D(p ∥ qC)/ln⁡2D(p\,\|\,q_C)/\ln2 に等しいことを確かめよ。（使う道具：この章の 1.5.4節、第1部第3章の相対エントロピー）
  3. (3) 記号の確率を逆順の (0.1,0.2,0.2,0.5)(0.1,0.2,0.2,0.5) だと思い込み、その分布で平均符号長が下界に等しくなるように長さ (3,3,2,1)(3,3,2,1) の符号を作ってしまった。実際の平均符号長と、下界との差を求めよ。（使う道具：この章の 1.5.3節）
  4. (4) 記号を nn 個ずつまとめて pp に合わせた Shannon 符号を作るとき、1記号あたりの平均符号長が下界から 0.010.01 ビット以内に入ることを保証するには nn をいくつ以上にすればよいか。（使う道具：この章の 1.5.5節）
  5. (5) 受け手は cc と dd を区別する必要がなく、Y=f(X)Y=f(X)（f(c)=f(d)f(c)=f(d)、ほかは別の値）だけを知りたい。YY の Huffman 符号の平均符号長を求めよ。また H(X)−H(Y)H(X)-H(Y) をビットで求め、それが H(X ∣ Y)H(X\,|\,Y) に等しく 00 以上であることを説明せよ。（使う道具：第1部第2章の連鎖律、第1部第4章のデータ処理不等式）
解答

(1) H(X)/ln⁡2=0.5log⁡22+2×0.2log⁡25+0.1log⁡210=0.5+0.929+0.332=1.761H(X)/\ln2=0.5\log_22+2\times0.2\log_25+0.1\log_210=0.5+0.929+0.332=1.761 ビット。Shannon 符号の長さは ⌈−log⁡2p⌉=(⌈1⌉,⌈2.32⌉,⌈2.32⌉,⌈3.32⌉)=(1,3,3,4)\lceil-\log_2p\rceil=(\lceil1\rceil,\lceil2.32\rceil,\lceil2.32\rceil,\lceil3.32\rceil)=(1,3,3,4) で、平均符号長は 0.5+0.6+0.6+0.4=2.10.5+0.6+0.6+0.4=2.1 ビット。1.761≤2.1<2.7611.761\le2.1<2.761 なので、定理 1.5.8（q=pq=p）の範囲に入る。この符号は Kraft 和が 12+18+18+116=1316<1\tfrac12+\tfrac18+\tfrac18+\tfrac1{16}=\tfrac{13}{16}<1 で、木に使い残しがある。

(2) 最小の 0.10.1（dd）と 0.20.2 をまとめて 0.30.3、次に残る 0.20.2 と 0.30.3 をまとめて 0.50.5、最後に 0.50.5 と 0.50.5 をまとめて根になる。最初の一手で bb と cc のどちらの 0.20.2 を選んでも、長さは 1,2,3,31,2,3,3 を aa と残りの記号に割り振ったものになり、たとえば a:0a:0、b:10b:10、c:110c:110、d:111d:111。平均符号長は 0.5+0.4+0.6+0.3=1.80.5+0.4+0.6+0.3=1.8 ビット。下界との差は 1.8−1.761=0.03901.8-1.761=0.0390 ビット。qC=(12,14,18,18)q_C=(\tfrac12,\tfrac14,\tfrac18,\tfrac18) で完全な符号なので、分解 (1.5.5) から差は D(p ∥ qC)/ln⁡2D(p\,\|\,q_C)/\ln2 に等しく、実際

D(p ∥ qC)ln⁡2=0.5log⁡21+0.2log⁡20.20.25+0.2log⁡20.20.125+0.1log⁡20.10.125=0−0.0644+0.1356−0.0322=0.0390\begin{aligned}\frac{D(p\,\|\,q_C)}{\ln2}&=0.5\log_21+0.2\log_2\frac{0.2}{0.25}+0.2\log_2\frac{0.2}{0.125}+0.1\log_2\frac{0.1}{0.125}\\ &=0-0.0644+0.1356-0.0322=0.0390\end{aligned}

ビットである。

(3) 平均符号長は 0.5×3+0.2×3+0.2×2+0.1×1=2.60.5\times3+0.2\times3+0.2\times2+0.1\times1=2.6 ビット。この符号は qC=(18,18,14,12)q_C=(\tfrac18,\tfrac18,\tfrac14,\tfrac12) を見込んだ完全な符号なので、下界との差は D(p ∥ qC)/ln⁡2=2.6−1.761=0.839D(p\,\|\,q_C)/\ln2=2.6-1.761=0.839 ビットになる。思い込みが当たっていれば 1.7611.761 ビット付近で済んだはずのところ、分布の取り違えで約半分の長さが余分にかかった。

(4) XnX^n に pp に合わせた Shannon 符号を使うと、定理 1.5.8 を XnX^n に当てて nH/ln⁡2≤ℓˉ<nH/ln⁡2+1nH/\ln2\le\bar\ell<nH/\ln2+1、1記号あたりでは上界との幅が 1/n1/n になる。1/n≤0.011/n\le0.01 から n≥100n\ge100 にすれば保証される。実際には Huffman 符号はもっと早く近づき、n=2n=2（16個の記号）の Huffman 符号を数値で作ると1記号あたり 1.7851.785 ビットで、n=1n=1 の 1.81.8 ビットより短い。

(5) YY の分布は (0.5, 0.2, 0.3)(0.5,\,0.2,\,0.3) で、Huffman 符号は 0.20.2 と 0.30.3 をまとめて 0.50.5、それと 0.50.5 をまとめて根になるので長さ (1,2,2)(1,2,2)、平均符号長は 0.5+0.4+0.6=1.50.5+0.4+0.6=1.5 ビット。H(Y)/ln⁡2=0.5+0.2log⁡25+0.3log⁡2103=1.485H(Y)/\ln2=0.5+0.2\log_25+0.3\log_2\tfrac{10}3=1.485 ビットなので、(H(X)−H(Y))/ln⁡2=1.761−1.485=0.2755(H(X)-H(Y))/\ln2=1.761-1.485=0.2755 ビット。YY は XX の関数なので H(X,Y)=H(X)H(X,Y)=H(X) で、連鎖律 H(X,Y)=H(Y)+H(X ∣ Y)H(X,Y)=H(Y)+H(X\,|\,Y) から H(X)−H(Y)=H(X ∣ Y)H(X)-H(Y)=H(X\,|\,Y)。YY が cc か dd のどちらかを表す値（確率 0.30.3）のときだけ XX に不確かさが残り、その中で cc、dd の条件付き確率は 23\tfrac23、13\tfrac13 なので、H(X ∣ Y)/ln⁡2=0.3 hb(13)/ln⁡2=0.3×0.918=0.2755H(X\,|\,Y)/\ln2=0.3\,h_{\mathrm b}(\tfrac13)/\ln2=0.3\times0.918=0.2755 ビットで一致する。条件付きエントロピーは 00 以上なので H(Y)≤H(X)H(Y)\le H(X) で、関数で情報を捨てた変数はもとの変数より短く圧縮することができる。これは、YY が XX を処理した結果であるときに成り立つ第1部第4章のデータ処理不等式を、圧縮の側から見たものである。下界の減り 0.27550.2755 ビットが捨てた情報の量 H(X ∣ Y)/ln⁡2H(X\,|\,Y)/\ln2 に等しい（Huffman 符号の平均符号長は、整数の長さの都合で 1.81.8 から 1.51.5 へ 0.30.3 ビット減る）。

木下の勉強ステータス

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

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

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

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