エントロピー符号化プレイグラウンド

異なるシンボル分布がシャノンエントロピーにどう影響するかを探り、ハフマン符号化の限界を比較し、現代のAI大規模言語モデル(LLM)で損失関数と語彙の不確実性をエントロピーがどう支配するかを学びます。

初期値 — エントロピー符号化プレイグラウンド

分布パラメータ(λ)	1.5

上のコントロールを変えると、ここから結果が計算し直されます。

インタラクティブシミュレーションを読み込んでいます...

ハフマンが払う代償は「整数ビット」 🖖

エントロピー符号化は統計的な冗長性を利用して、メッセージをより少ないビットで表現します。シャノンの情報源符号化定理によれば、あらゆる無損失符号の絶対的な最小平均長はシャノンエントロピーです: H(X) = −Σ p_i log₂ p_i。ハフマン符号化は、シンボルを個別に符号化する場合の与えられたアルファベットに対して最適ですが、整数長の符号語に制約されます。この整数制約により、ハフマンは理論上のエントロピーから最大0.086ビット/シンボルずれる可能性があります(あるシンボルのp_i ≈ 1の場合はさらに大きくずれます)。算術符号化(ANSなど)は、シーケンス全体を小数区間にマッピングすることでこの限界を克服します。

LLMとAIとのつながり: 現代の言語モデル(LLM)では、エントロピーは学習と生成の両方における中核概念です。LLMは、語彙予測と実際のテキストとの間の交差エントロピー損失を最小化することで学習されます。生成(推論)時には、LLMは次のトークンについて語彙全体にわたる確率分布を出力します。この分布のエントロピーはモデルの予測の不確実性を測るもので、平坦な分布(高エントロピー)は創造的またはランダムなテキストを生み、鋭い分布(低エントロピー)は非常に予測可能なテキストを生みます。温度(Temperature)などのサンプリングパラメータはこのエントロピーを直接スケーリングし(温度を下げるとエントロピーが減り、上げると増えます)、nucleusサンプリング(Top-p)は累積確率を動的に制限して高エントロピーの裾を切り落とします。

なぜ珍しい記号ほどビットを食うのか 🖖

このツールの本当の教訓は、記号を符号化する理想的なビット数がその「意外性」、つまり −log₂ p だということです。半分の確率で現れる記号は1ビット、1000回に1回の記号は約10ビットに値します。エントロピーとは、全記号にわたるこの意外性の平均にすぎません。だからラプラス分布や指数分布のような偏った分布はよく圧縮できますが、一様な記号集合は圧縮できません。すべてが等確率なら、取り除くべき冗長性が存在しないのです。

モールス符号：シャノン以前のエントロピー符号化 🖖

モールス符号は、最も短い信号である単一の点を英語で最頻の文字 E に割り当て、Q や Z のような珍しい文字には長い並びを割り当てました。長さを決めるため、アルフレッド・ヴェイルは印刷所の活字ケースにある活字を数えて文字の出現頻度を推定したと言われます。これは1840年代に実際に機能していた可変長符号化であり、シャノンが1948年にその仕組みを理論的に定式化するおよそ一世紀前のことでした。

連鎖のひとつの段 — 何が入り、何が出て、後段で何が壊れるか

この段はエンコード処理のどこに位置するか

動画エンコーダは単一のアルゴリズムではなく、順序の決まった 8 つの段です。その順序は恣意的ではありません。どの段も、直前の段が仕事を可能にしてくれたからこそ存在します。このツールはそのうちの 1 つを扱います。下の連鎖から残りの 7 つに移動できます。

エントロピー符号化プレイグラウンド — 量子化された記号を、その統計が許す限り少ないビットに詰める

入ってくるもの: 量子化された整数の流れ。ゼロへ大きく偏っています。
出ていくもの: 完成したビットストリーム。ここでは何も捨てません。
次の段が前提とすること: 後段には何もありません。これが最後の符号化段です。前提は上流にあり、記号の分布がすでに偏らせてあることです。
ここで壊れるもの: どのエントロピー符号化器も、渡されたもののシャノン・エントロピーを下回れません。つまりその天井は前の段が完全に決めています。量子化されていない係数に対して走らせても見つかる冗長性はほとんどなく、それこそが情報を捨てる段が最後ではなく先に来る理由です。

前の段: 量子化次の段: レート制御

全プロセスの詳細解説

16個のシンボルにおけるハフマン符号より賢明なアルゴリズムの余地 6 ステップ
16個のシンボル、ラプラス分布、エントロピー 3.010 bits。ハフマン符号は 3.012 を達成する。より高度なアルゴリズムに改善の余地がどれだけ残されているかを求めよ。
1. エントロピーとは、この分布から引かれた 1 つのシンボルの平均的な情報量（bits 単位）である。これは確率のみの性質であり、いかなる符号についても関知しない。
  
  $H (X) = - i = 1 \sum N p_{i} lo g_{2} p_{i} = 3.010 bits/symbol (N = 16, Laplacian, λ = 1.5)$
2. 素朴な代替策ではすべてのシンボルに同じ bits 数を割り当てるが、16 個のシンボルには 4 bits が必要となる。これが、削減効果を測定する際の基準となる。
  
  $L_{fixed} = ⌈ lo g_{2} N ⌉ = ⌈ lo g_{2} 16 ⌉ = 4.0 bits/symbol$
3. ハフマン符号は頻出するシンボルに短い符号を、稀なシンボルに長い符号を割り当て、その平均は確率で重み付けされた符号長となる。
  
  $\overset{ˉ}{L} = \sum p_{i} L_{i} = 3.012 bits/symbol$
4. 削減効果の比較はこれら 2 つの符号長同士の比較であり、符号とエントロピーの比較ではない。だからこそ、この主張は理論的限界についてではなく、あくまでこの代替策に対するものなのである。
  
  $savings = \frac{4.0 - 3.012}{4.0} = 24.7%$
5. 次に、限界と比較する。シャノンの情報源符号化定理によれば、いかなるプレフィックス符号も H 未満になることはできず、ハフマン符号は確実に H + 1 未満に収まることが保証されている。
  
  $H \leq \overset{ˉ}{L} < H + 1 (Shannon); \overset{ˉ}{L} - H = 3.012 - 3.010 = 0.002 bits$
6. 残されたギャップを割合として表せば、最適化という問いの答えは自ずと明らかになる。
  
  $\frac{0.002}{3.010} = 0.07% above the floor$
解答

記号あたり0.002ビット、すなわち0.07%です。シャノンの定理によれば、任意の接頭符号の平均符号長は H と H + 1 の間に収まります。そして、その中でのハフマン符号の最適性は証明済みです。つまり、接頭符号を使う限り、このテキストで3.012を下回ることはありません。固定長符号からの24.7%の削減は、紛れもない成果です。残る0.07%は、今後どれほど技術を尽くしても得られる改善のすべてです。これ以降の圧縮は、符号化ではなくモデルを変更することで得られます。隣り合う記号間に相関があるならば、条件付き分布のエントロピーは3.010を下回ります。全く別の数値になるのです。

$\overset{ˉ}{L} - H = 0.002 bits : Huffman is 0.07% off optimal here$

参考文献 (1)

Insight block 2 — entropy as average surprise, and the limit Huffman cannot beat: C. E. Shannon, "A Mathematical Theory of Communication." Bell System Technical Journal 27(3), 379–423, 1948.

42Math チーム · 更新 2026-07-29

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

一様分布8 - 均一な8シンボル情報源: H=3 bits、符号化による利得はゼロ — エントロピーが固定長符号と一致する
DCT風(ラプラス) - DCT的なラプラス分布: H≈2.1 bits、23%の節約 — ほとんどの映像AC係数はゼロ付近に集中する
動きベクトル風 - 動きベクトル的な指数分布: H≈2.3 bits、4bit固定符号に対して43%の節約
双峰分布 - 双峰分布: 2つの支配的なシンボルによりH≈2.5 bitsとなり、ハフマン圧縮の利得が大きい