エントロピー符号化を1から — ハフマンから算術符号まで

「情報量がそのまま符号長になる」——この一行が圧縮のすべてです。シャノンの下限からハフマン符号の作り方、整数ビットという限界、それを外す算術符号とANS、そしてJPEG・PNG・H.264・zstdのどこで何が動いているかまで。最後に、圧縮率が頭打ちになったときの切り分け方を置きます。

モールス信号が正しかった理由

モールス信号では、英語で最も多く出る E は「・」の1つ、めったに出ない Q は「− − ・ −」の4つです。1837年の発明者たちは情報理論を知りませんでしたが、よく出るものを短くという原則を経験で掴んでいました。

1948年、シャノンはこの直感に正確な形を与えます。しかも「短くすべき」だけでなく、どこまで短くできるかの限界まで示した。エントロピー符号化とは、その限界に近づくための技術の総称です。JPEGの末尾でも、PNGの末尾でも、gzipでも、H.264でも、最後に走っているのは必ずこれです。

中心思想: 情報量が、そのまま符号長になる

情報理論の記事で、出来事 $x$ の情報量を $-\log_2 p(x)$ と定義しました。確率が低いほど大きい「驚きの量」です。符号化の理論は、この量に物理的な意味を与えます。

この式が言っているのは要するに、確率 $p$ で出る記号には、$-\log_2 p$ ビットを割り当てるのが最適だということです。確率 $1/2$ の記号は1ビット、$1/4$ なら2ビット、$1/256$ なら8ビット。「驚きの大きさ」という抽象的な量が、そのままビット数という具体物になっている。ここがこの分野のいちばん美しいところです。

理想の割り当てができたとき、1記号あたりの平均符号長は情報量の期待値、すなわちエントロピーそのものになります。

つまり、その情報源が出しうる記号を1つずつ見ていって、「その記号が出る割合 $p(x)$」×「その記号に与えるべきビット数 $-\log_2 p(x)$」を全部足す、ということです。$H(p)$ はその加重平均——すべての記号を正しく値付けしたときに、1記号あたり払うことになる請求額です。

そしてシャノンの情報源符号化定理は、これが破れない床であることを保証します。どんな一意復号可能な符号でも、平均符号長は $H(p)$ を下回れない。同時に、$H(p) + 1$ ビット未満は必ず達成できる。圧縮の上限も下限も、この1つの量で決まっています。

接頭符号とクラフトの不等式

符号長を自由に選べるわけではありません。区切り記号なしで復号するには、どの符号語も他の符号語の先頭部分になっていないことが必要です（接頭符号）。0 と 01 を両方使うと、0 を読んだ時点で確定できません。

この制約は、符号長 $\ell_i$ について次の不等式に集約されます。

これがクラフトの不等式です。言い換えれば、短い符号語には高いコストがある。1ビットの符号語は予算の $1/2$、2ビットなら $1/4$ を消費し、合計1を超えられない。「よく出る記号を短く」が最適化問題になるのは、この有限の予算を奪い合うからです。

ハフマン符号を手で作る

最適な接頭符号を作る手続きは、驚くほど短い。確率が最も小さい2つを取り出して束ね、その和を新しい要素として戻す。要素が1つになるまで繰り返すだけです。

5記号でやってみます。$p(A)=0.40$, $p(B)=0.20$, $p(C)=0.20$, $p(D)=0.10$, $p(E)=0.10$。

1. 最小の2つ $D, E$（各0.10）を束ねて $DE = 0.20$
2. 残りは $A\,0.40,\ B\,0.20,\ C\,0.20,\ DE\,0.20$。最小の2つとして $B, C$ を束ねて $BC = 0.40$
3. 残りは $A\,0.40,\ BC\,0.40,\ DE\,0.20$。最小の2つ $DE$ と $A$ を束ねて $ADE = 0.60$
4. $ADE$ と $BC$ を束ねて根

出来た木の枝に0と1を振ると、$A=00$, $B=10$, $C=11$, $D=010$, $E=011$。どれも他の先頭になっていません。平均符号長は

$$0.4(2) + 0.2(2) + 0.2(2) + 0.1(3) + 0.1(3) = 2.20 \ \text{bit}$$

各項は「その記号が出る割合 × その符号語の長さ」です。$A$ は40%の頻度で出て2ビット、$D$ は10%の頻度で出て3ビット。要するにこの合計が、記号1つあたりに払う値段ということになります。

一方エントロピーは $H = 2.12$ ビット。固定長なら5記号に3ビット必要ですから、3.00 → 2.20 ビットまで縮み、理論下限 2.12 まであと 0.08 という位置にいます。ハフマン符号は「記号ごとに整数ビットを割り当てる符号のなかでは最適」であることが証明されており、この 0.08 は手抜きではなく構造的な取りこぼしです。