ソース符号化と圧縮

エントロピーは可逆圧縮の理論的下界である——任意の符号化の期待符号長は H(X) を逃れられない。クラフトの不等式は接頭符号の存在可否を定め、ハフマン符号は貪欲法でこれに迫り、算術符号はエントロピー率にほぼ到達する。そして最も深い洞察は、「言語モデルとは圧縮のことである」というものだ。完璧な大規模言語モデル（LLM）の交差エントロピー損失は、データのエントロピー率の推定量そのものである。

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

前の2章で何度も登場した数値が1つある。それはエントロピー 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 を超えてはならず、超えると必然的に符号語の衝突が生じる。

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

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

シャノンのソース符号化定理（可逆） は、任意の一意復号可能な符号化について、期待符号長 L が以下を満たすことを述べる。

L \geq H(X)

さらに、H(X) \leq L < H(X) + 1 となる符号化が常に存在する。

この文には2つの層がある。第1の層は、エントロピー が可逆圧縮の硬い下界であり、誰也不可能にこれを下回る圧縮はできないということだ。第2の層は、この下界がほぼ到達可能であるということだ——あの +1 のギャップは、「複数の記号をまとめて1つのブロックとして符号化すること」によって任意の小ささに薄めることができる。

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

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

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

問題は、自己情報量は通常整数ではなく、符号語の長さは整数でなければならないことだ。この「切り捨て誤差」こそが、次に説明するハフマン符号と算術符号がせめぎ合っている点である。

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

ハフマン符号 は貪欲な手順を用いて、⁠期待符号長が最適となる整数接頭符号を構築する。ルールは以下の通りである。現在確率が最小の2つのノードを繰り返し選び、それらを親ノードにマージする（確率を合算）。1つのルートノードが残るまでこれを繰り返す。マージの際、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) 区間内の小さな部分区間にマッピングする。記号を1つ読むたびに、その確率に応じて現在の区間を比率で細分化し、対応する部分区間を選択する。メッセージ全体を読み終えた後、その区間を一意に特定するのに十分な2進小数を出力する。

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

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

代償も2つある。計算がハフマンより複雑であること、そして正確な確率モデルが必要であることだ。2つ目の点——「正確な確率モデルを提供する」という行為こそが、言語モデルが行っていることであり、後でこれがつながる。実用的な現代の派生手法として range coding と ANS（非対称数値体系） がある。後者は 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/文字 まで落ちる。依存関係が強いほどエントロピー率は低くなり、圧縮可能な余地が大きくなる。実用的な圧縮器（および言語モデル）が搾り取るのは、この冗長性である。

言語モデルとは圧縮のこと

上記の連鎖を繋げると、情報理論の中で最も美しい等価性が得られる。

言語モデルは、各ステップで各トークンに対して確率分布 q を出力する。これを使って算術符号を駆動し、あるテキストを圧縮した場合の平均符号長は、モデルがこのテキスト上での交差エントロピー H(p,q) に等しくなる（交差エントロピー 参照）。そしてソース符号化定理は、この符号長の下界がデータの本物のエントロピー率 H_\text{rate} であることを示している。したがって、

モデルの交差エントロピー損失 = 可逆圧縮におけるビットレート。損失が低いほど = 圧縮率が高いほど = データのエントロピー率に近い。「完璧な」言語モデルでは、交差エントロピーはデータエントロピー率の下界に等しくなる。

これは比喩ではない。GPT や Claude といったモデルは、⁠本質的に究極の可逆圧縮器なのである。そのため、モデルが強力であればあるほど、圧縮ベンチマーク（例えば enwik9 ウィキテキストを対象とした Hutter Prize）でのパフォーマンスも向上する——これら2つのことは、同じことの2つの尺度に過ぎない。

トークン化の段階における BPE も、この論理の工学的近似である。BPE は貪欲なマージを用いて高頻度の部分文字列を単一のトークンに圧縮し、シークエンスのビットコストをヒューリスティックに低下させる——粗粒度のエントロピー最適化の一種だ。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, 可逆圧縮, 言語モデルとは圧縮のこと, Hutter Prize, BPE