ソース符号化と圧縮

エントロピーは可逆圧縮の理論的下界である——任意の符号化における期待符号長は H(X) を逃れられない。クラフトの不等式は接頭符号の存在可否を定め、ハフマン符号はそれへ貪欲に近づき、算術符号はエントロピー率にほぼ到達する。言語モデルは確率予測を提供し、エントロピー符号化器と組み合わせることで圧縮システムを構成する。モデルの交差エントロピーは、データ上での理想的な平均符号長に対応する。

導入: 圧縮は誰と戦っているのか

前2章で何度も登場した数値が一つある。エントロピー H(X) だ。これは「平均で何回質問するか」「平均で何ビット必要か」と説明されてきた。本章では、これを具体的なタスク——⁠圧縮⁠——として現実のものにする。

タスクは極めて素朴である。一連の記号を2進数に符号化し、期待符号長をできるだけ短くする。そして、一字一句漏れなく復元可能でなければならない（可逆圧縮）。問題は、どこまで短くできるのか？ 誰も越えられない壁があるのか？

ある。その壁がエントロピーだ。本章では以下の3点を明らかにする。壁がどこにあるか（ソース符号化定理）、壁に近づいて符号をどう作るか（ハフマン符号、算術符号）、そしてなぜ「言語モデル」と「圧縮器」が実質的に同じものなのか。

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

まず、「曖昧さなく復号できるか」を解決する。最も実用的な符号化の一種が接頭符号（prefix code）⁠である。接頭符号とは、どの符号語も他の符号語の接頭部分（プレフィックス）にならない符号のことである。これにより、復号時に完全な符号語を読み取った瞬間に区切りを認識でき、区切り文字を必要としない。

どのような符号長の組み合わせが接頭符号を構成し得るか？⁠クラフトの不等式は、その必要十分条件を与える。符号長が l_1, l_2, \ldots, l_n の2進接頭符号が存在するための必要十分条件は、

\sum_i 2^{-l_i} \leq 1

直感的理解⁠: 符号語を2分木の葉ノードとみなす。長さ l_i の符号語は、符号空間の 2^{-l_i} の割合を占有する。総占有量は 1 を超えてはならず、超えると符号語の衝突が避けられない。

この不等式は、もう一つ重要なことをほのめかしている。ある符号語をより短くしたい（l_i を小さくしたい）場合、他の符号語を長くしなければならない。⁠符号長はゼロサムなのだ——どこかで短くすれば、どこかで必ず補わなければならない。

シャノンのソース符号化定理: エントロピーは下界

シャノンのソース符号化定理（可逆） は、任意の一意復号可能な符号化において、期待符号長 L が

L \geq H(X)

を満たすことを述べる。さらに、H(X) \leq L < H(X) + 1 となる符号化が常に存在することも示す。

この命題には二つの層がある。第一に、エントロピー は可逆圧縮の硬い下界であり、誰もエントロピー以下には圧縮できない。第二に、この下界はほぼ到達可能である——+1 のギャップは、「複数の記号をまとめてグループ化して符号化する」ことで、任意の小さい値に薄めることができる。

証明の骨子⁠（覚えておく価値がある）: クラフトの不等式とギブスの不等式を組み合わせると、

L - H(X) = \sum_x p(x)(l_x + \log_2 p(x)) \geq 0

となり、l_x = -\log_2 p(x) のときに等号が成立する——⁠理想的な符号長は自己情報量そのものである。

問題は、自己情報量は通常整数ではなく、符号語の長さは整数でなければならない点にある。この「切り捨て誤差」こそが、次節のハフマン符号と算術符号が争う対象なのである。

ハフマン符号: 貪欲法による逼近

ハフマン符号 は、貪欲な手順を用いて、⁠期待符号長が最適となる整数接頭符号を構築する。規則は以下の通りである。現在確率が最小の2つのノードを繰り返し選び、それらを親ノード（確率の和）にマージし、ルートノードが一つ残るまで続ける。マージする際、2つの枝にそれぞれ 0 と 1 を割り当て、ルートから葉へのパスが符号語となる。

結果として、高頻度の記号はルートに近く、符号長が短くなり、低頻度の記号はルートから遠く、符号長が長くなる。

この例では、確率がちょうど 2 の累乗になっている。期待符号長を計算すると、

L = 0.5\times 1 + 0.25\times 2 + 0.125\times 3 + 0.125\times 3 = 1.75\ \text{bit}

となり、エントロピー H = 1.75 bit と完全に一致し、下界を完璧に達成している。

しかし、これは特殊な例である。確率が 2 の累乗でない場合、整数の符号長で理想的な -\log_2 p(x) を実現できず、ハフマン符号では記号ごとに最大 1 bit の無駄が生じる。この無駄はどこから来るのか？ それは前節で述べた「切り捨て誤差」なのである。

算術符号: 整数ビットからの脱却

算術符号（arithmetic coding） は、ハフマン符号の整数のボトルネックを直接回避する。

そのアプローチは全く異なる。個々の記号に整数の符号語を割り当てるのではなく、⁠メッセージ全体を [0,1) 区間内の小さな部分区間にマッピングする。記号を一つ読むたびに、その確率に応じて現在の区間を比率で細分化し、対応する部分区間を選択する。メッセージ全体を読み終えた後、その区間を一意に特定するのに十分な2進小数を出力する。

これにより、以下の2つの重要な利点が得られる。

• 整数ビットである必要がない⁠。確率 0.9 の記号は約 0.15 bit で表現でき、ハフマン符号では不可能（最低でも 1 bit 必要）である。
• エントロピー率に逼近可能⁠。長いメッセージでは、平均符号長を H(X) に任意に近づけることができ、ハフマン符号の +1 のギャップをほぼ解消できる。

代償として2つの欠点がある。計算がハフマン符号より複雑であること、そして正確な確率モデルが必要であることだ。後者を覚えておいてほしい——「正確な確率モデルを提供する」という役割こそが、言語モデルが担っているものであり、これにより後で接続が可能になる。実用的な変種として range coding と ANS（Asymmetric Numeral Systems） があり、後者は zstd や LLM 圧縮ベンチマークで頻繁に登場する。

エントロピー率: 記号間の依存関係

ここまでは記号が独立であると仮定し、H(X) を単一記号のエントロピーとして扱ってきた。しかし、実際のデータ（テキスト、音声）では記号間に強い依存関係があるため、別の量、⁠エントロピー率（entropy rate） を用いる必要がある。

H_\text{rate} = \lim_{n\to\infty} \frac{1}{n} H(X_1, X_2, \ldots, X_n)

一般的な定常情報源では、これは無限の履歴における平均条件エントロピーと等しくなり、記号間の依存関係がすべて考慮される。ここで極限と同等性が成立するには定常性などの条件が必要だが、個人知識ベースでは、「長期において記号ごとに残る予測不可能性の度合い」という直感的理解を覚えておけば十分である。

英語が最も良い例である。単一文字の独立仮定では約 4.7 bit だが、文字の頻度を考慮すると約 4.1 bit に下がり、さらに文脈依存を考慮すると、シャノンの推定するエントロピー率は約 1.0–1.3 bit/文字 まで低下する。依存関係が強いほどエントロピー率は低くなり、圧縮可能な余地が大きくなる。すべての実用的圧縮器（および言語モデル）が絞り出しているのは、この冗長性なのである。

AEP と典型集合: なぜ長い列がエントロピーに近づくのか

単一記号の理想的な符号長 -\log_2p(x) は通常整数ではないが、なぜ列を長くすることで平均符号長がエントロピーに逼近できるのか？ これらを結びつけるのが漸近等分性（Asymptotic Equipartition Property, AEP） である。

独立同分布（i.i.d.）情報源から生成された長い列 X^n=(X_1,\ldots,X_n) において、以下のことが高い確率で成り立つ。

-\frac{1}{n}\log_2 p(X^n)\approx H(X)

つまり、確率質量の大部分が典型列（typical sequences） の集合に集中している。この集合には約 2^{nH(X)} 本の列があり、それぞれの確率は約 2^{-nH(X)} である。したがって、典型列に番号を振るには約 nH(X) bit しか必要なく、少数の非典型列は別途処理すればよく、その追加コストは n の増加とともに薄められる。

これが、「単一記号では H\leq L<H+1 しか達成できないが、長いブロックでは記号あたりの符号長を H に圧縮できる」理由である。依存関係を持つ定常エルゴード情報源では、同じ直感がエントロピー率によって支配される。AEP は、なぜ後のチャネル符号化定理 で長い符号語と漸近極限が語られるのかを説明する。

言語モデルはどのように圧縮に接続されるのか

上記のチェーンを繋げると、情報論で最も美しい等価性が得られる。

言語モデルは、各ステップで各トークンに対して確率分布 q を出力する。これを使って算術符号を駆動する場合、あるテキストの理想的な符号長は、トークンごとの -\log_2q(x_i\mid x_{<i}) の和となる。有限精度と終端のオーバーヘッドを無視すれば、トークンあたりの平均符号長は、モデルがこのテキスト上での交差エントロピーに等しくなる（交差エントロピー 参照）。そしてソース符号化定理は、この符号長の下界がデータの真のエントロピー率 H_\text{rate} であることを示す。したがって、

モデルの交差エントロピー損失は、それを確率モデルとして用いた際の理想的な圧縮ビットレートに対応する。損失が低いほど、予測が正確であり、エントロピー符号化器と組み合わせることで通常、より高い圧縮率を得られる。モデルがデータの分布に完全に一致する場合、その交差エントロピーはデータのエントロピー率に達する。

これは比喩ではなく、役割を明確に区別する必要がある。⁠言語モデルは確率を提供し、算術符号 / ANS がその確率を復元可能なビットストリームに変換する⁠。復号側でも同じモデルを共有する必要があり、モデル重みの保存と転送コストも考慮に入れなければならない。大量のデータにわたってこの固定コストを分散させて初めて、これを無視できる近似とみなせる。したがって、予測能力と圧縮能力は強く相関しているが、あらゆる状況で無条件に等しいわけではない。

トークン化の段階である BPE も、圧縮アルゴリズムの血統を持っている。それは高頻度の隣接記号を貪欲にマージし、一般的なフレーズをより少ないトークンで表現させる。しかし、⁠シーケンスが短くなっても、バイトあたりの情報量が必ずしも減少するわけではない⁠——語彙サイズが大きくなれば、トークンの確率やモデルの能力も変化する。より正確に言えば、BPE はシーケンス長、語彙サイズ、学習可能性の間で工学的なトレードオフを行っている。アルゴリズムの詳細は トークンとサンプリング を、圧縮の視点からスケーリング則を理解する方法は LLM における情報論 で展開している。

参考文献

• 論文⁠: "A Mathematical Theory of Communication" (Shannon, 1948 — ソース符号化定理と英語エントロピー率推定の原典)
• 教科書⁠: "Elements of Information Theory" (Cover & Thomas — 第5章 データ圧縮, Kraft/ハフマン/算術符号)
• ベンチマーク/プロジェクト⁠: "Hutter Prize" と "Language Modeling Is Compression" (Delétang et al., 2023 — LLM による可逆圧縮の実証、損失がビットレートに相当)

キーワード: 接頭符号 prefix code, クラフトの不等式, ソース符号化定理 source coding theorem, ハフマン符号, 算術符号 arithmetic coding, ANS, エントロピー率 entropy rate, AEP, 典型集合 typical set, 可逆圧縮, 言語モデルと圧縮, Hutter Prize, BPE