算術符号とユニバーサル符号

🎓 レベル：発展　|　重要度：B（重要）

📎 前提：ハフマン符号、シャノンの情報源符号化定理　|　関連：結合・条件付きエントロピーと連鎖則（エントロピーレート）

要点（BLUF）

算術符号：記号を1つずつではなく 系列全体を $[0,1)$ の1つの区間に対応づけ、その区間内の数を出力する。符号長は $\approx -\log_2 p(\text{系列})$ で、ハフマンの整数長の無駄（1記号最大1 bit）を系列全体で償却します。
ユニバーサル符号（Lempel-Ziv など）：情報源の確率分布を事前に知らなくても、データを見ながら学習し、漸近的にエントロピーレートまで圧縮できる。gzip・PNG・zip の理論的土台。
どちらも「1記号ごとの整数長」というハフマンの制約を超え、実用的な無歪み圧縮の主力です。

1. 算術符号：系列を1つの区間に畳む

区間 $[0,1)$ から始め、記号を読むたびに「現在の区間を、各記号の確率に比例して分割し、読んだ記号の小区間に縮める」を繰り返します。系列 $x_1\cdots x_n$ を処理し終えると、幅 $p(x_1\cdots x_n)=\prod_i p(x_i)$ の区間が残ります。その区間内の数を2進小数で1つ指定すれば符号化完了。区間幅 $w$ を一意に指すには約 $-\log_2 w$ bit 必要なので、

\text{符号長} \approx -\log_2 p(x_1\cdots x_n) = \sum_{i=1}^n \big(-\log_2 p(x_i)\big)

1記号あたりに均すと自己情報量の平均＝エントロピー。ハフマンと違い各記号を整数 bit に丸めないので、 $-\log_2 p_i$ が非整数でも無駄が系列全体で2 bit 程度に収まり、長い系列では1記号あたりほぼ消えます。条件付き確率 $p(x_i\mid x_{<i})$ を使えば、記憶のある情報源のエントロピーレート（結合・条件付きエントロピーと連鎖則）まで圧縮できます。

graph TD
  s0["区間 0〜1 から開始"] --> s1["x1=a で 0〜0.7 に縮小"]
  s1 --> s2["x2=b で 0.49〜0.63 に縮小"]
  s2 --> s3["系列を読むほど区間は狭まる"]
  s3 --> out["最終区間内の1点を2進小数で出力（約 -log2 幅 bit）"]

2. ユニバーサル符号：確率を知らずに圧縮する

ハフマンも算術符号も確率分布 $p$ を知っている前提でした。実データでは $p$ は未知・非定常です。ユニバーサル符号は分布を仮定せず、データの統計を走りながら学習します。代表が Lempel-Ziv（LZ77/LZ78）：過去に出た部分列を「（位置, 長さ）」の参照に置き換える辞書式圧縮で、繰り返しが多いほど縮みます。LZ は任意の定常エルゴード情報源に対し、1記号あたり符号長がエントロピーレートに漸近することが証明されています。gzip（LZ77＋ハフマン）、zip、PNG はこの系譜です。

3. コード：算術符号 vs ハフマン（底2, bit）

i.i.d. 情報源 $p=\{a:0.7,b:0.2,c:0.1\}$ から系列を生成し、算術符号の符号長 $-\log_2 p(\text{系列})$ が1記号ハフマンより $H$ に近いことを確かめます。

import numpy as np, heapq
rng=np.random.default_rng(0)
pv=np.array([0.7,0.2,0.1])     # a,b,c
H=-np.sum(pv*np.log2(pv))
n=10000
seq=rng.choice(3,size=n,p=pv)

# 算術符号の理想符号長 ~ -log2 p(系列)
arith_bits = -np.sum(np.log2(pv[seq]))

# 1記号ハフマン（整数長）
def huffman_len(prob):
    heap=[[pp,i,[i]] for i,pp in enumerate(prob)]; heapq.heapify(heap)
    lengths=[0]*len(prob); cnt=len(prob)
    while len(heap)>1:
        lo=heapq.heappop(heap); hi=heapq.heappop(heap)
        for i in lo[2]: lengths[i]+=1
        for i in hi[2]: lengths[i]+=1
        heapq.heappush(heap,[lo[0]+hi[0],cnt,lo[2]+hi[2]]); cnt+=1
    return lengths
L1=np.sum(pv*np.array(huffman_len(pv)))

print(f"エントロピー H = {H:.4f} bit/記号")
print(f"系列長 n={n}")
print(f"算術符号の符号長 ~ -log2 p(系列) = {arith_bits:.1f} bit")
print(f"  1記号あたり = {arith_bits/n:.4f} bit/記号  (H={H:.4f} に近い)")
print(f"1記号ハフマン平均長 = {L1:.4f} bit/記号 (整数丸めで H より大)")

出力：

エントロピー H = 1.1568 bit/記号
系列長 n=10000
算術符号の符号長 ~ -log2 p(系列) = 11549.6 bit
  1記号あたり = 1.1550 bit/記号  (H=1.1568 に近い)
1記号ハフマン平均長 = 1.3000 bit/記号 (整数丸めで H より大)

出力の意味：算術符号は1記号あたり $1.1550$ bit で、エントロピー $1.1568$ bit にほぼ一致（標本ゆらぎで僅かに下にも出ます）。対して1記号ハフマンは $1.3000$ bit と、整数長への丸めで $0.14$ bit/記号も無駄が出ています。算術符号は系列全体を1つの数に符号化することで、ハフマンが記号ごとに払う整数丸めの税金を償却しているわけです。1万記号なら算術符号は約 1400 bit（約 175 バイト）得をします。実用の汎用圧縮（gzip 等）はユニバーサル符号でこの効率に近づきつつ、分布が未知でも動きます。

4. 数式の直観的意味

ハフマンの限界は「各記号に整数 bit を割り当てる」点にありました。算術符号は 系列を1つの実数とみなす ことで、実質的に分数 bit を扱えます—— $-\log_2 0.7\approx0.515$ bit を、丸めずにそのまま積み上げられる。だから符号長は系列の自己情報量 $-\log_2 p(\text{系列})$ にぴたり一致し、AEP（漸近等分割性とAEP）が言う「長い系列は約 $2^{-nH}$ の確率」と整合します（典型系列を $nH$ bit で指す）。ユニバーサル符号はさらに「 $p$ を知らなくても、長く見れば実効的に学習できる」という、符号化定理の実用的な完成形です。

⚠️ よくある誤解

「算術符号はハフマンより必ず大幅に良い」ではない：確率が2の冪に近いと両者の差は小さい。差が大きいのは偏った分布（最大確率が大きい）や小さなアルファベットのとき。
「ユニバーサル符号は魔法で何でも縮む」ではない：縮むのは冗長性のあるデータだけ。エントロピーレートが上限で、乱数や暗号文は縮みません（シャノンの情報源符号化定理）。
「算術符号は無限精度が必要」ではない：実装はレンジコーダ等で有限精度の整数演算に落とせます。理論の区間が実装のレジスタに対応。
「LZ は確率モデルを持たない」ではない：明示的な確率は持ちませんが、暗黙にデータの統計を学習しエントロピーレートに漸近します。

対応シミュレーション

本文のコードで算術符号の符号長 $\approx -\log_2 p(\text{系列})$ と1記号ハフマンとの差を実証済み。