ハフマン符号化ビジュアライザー

テキストを入力すると、ハフマン符号化が頻出文字に短い符号を割り当てる様子がわかります。

計算例 — ハフマン符号化ビジュアライザー

元のサイズ(8ビットASCII)	88
ハフマン符号化後のビット数	32
削減率	63.6%
'l' (3×)	10
'␣' (1×)	000
'w' (1×)	001
'r' (1×)	010
'd' (1×)	011

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

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

ハフマンは 1 ビット未満を使えない 🖖

ハフマン符号は最適ですが、それは高い代償を伴う規則の内側での話です。すべての記号に整数個のビットを割り当てなければならないのです。シャノンの限界によれば、90% の頻度で現れる記号の価値はおよそ 0.15 ビットであり、90% が 1 つの文字、10% が別の文字からなる情報源のエントロピーは 1 記号あたりわずか 0.469 ビットです。ハフマンはビットの端数を書けないので 1 と 1 を割り当て、情報の価値の 2 倍以上を費やします。この差こそ、偏りの大きいデータがここで期待外れの圧縮率になる理由であり、算術符号やレンジコーダが存在する理由です。それらはメッセージ全体を 1 つの数として符号化し、端数ビットを自由に使えます。ハフマンが最適なのは整数ビット符号のなかでの話であり、それは単に最適だと言うより狭い主張です。

常に最も稀な二つを併合して作る 🖖

木は下から上へ組み立てられます。まず各文字を出現頻度順に並べ、次に最も頻度の低い二つの要素を小さな部分木にまとめ、一つの束として扱う操作を繰り返します。木が一つになるまで続け、最後に頂点から下りながら符号を読み取ります。左が 0、右が 1 です。常に最小の二つを結ぶこの「貪欲な」やり方は近視眼的に見えますが、証明上もっとも短い符号を生み出します。

指導教授を超えた学期レポート 🖖

デイヴィッド・ハフマンは1951年、MITの大学院生だったときにこれを考案しました。ロバート・ファノ教授が、期末試験か「最も効率的な符号を見つける」レポートかを学生に選ばせたのです。ファノとクロード・シャノンはすでに挑戦し、木を上から下へ構築していました。ハフマンは諦めかけましたが、下から上へ――最も稀な記号から併合する――のが最適だと気づき、自分の教授の方法を上回りました。

ハフマン符号 — いつ効くのか、そして最適にどこまで近いのか

あなたはどの圧縮のケースにいますか？

ハフマン符号は、よく出る記号に短い符号を、まれな記号に長い符号を与えます。各記号に整数ビットを割り当てるという条件のもとでは、これが最良だと証明されています。どれだけ縮むかは、頻度がどれだけ偏っているかだけで決まります。まったく均等なら利用できる偏りはなく、大きく偏っていれば大勝ちします。ただし、限界を決めるのが頻度ではなく整数ビットになる地点までです。

偏った頻度 — この手法が本来ねらう場面 p_i ↑ ⇒ ℓ_i ↓

どの記号も同じ頻度 — 利用できる偏りがない p_i = 1/n ⇒ ℓ = log₂n

ふつうの文章 — 理論上の下限まで 1 ビット H ≤ ℓ < H + 1

記号が 1 種類だけ — ハフマンが割り込めない下限 n = 1 ⇒ ℓ = 1

偏った頻度 — この手法が本来ねらう場面

わかっていること: ごく少数の記号が文字列を占めています。それらが最短の符号を得て、合計は固定長の符号化をはるかに下回ります。

費用: p_i ↑ ⇒ ℓ_i ↓

計算例: 「mississippi」：11 文字、異なる記号は 4 つ、21 ビットで符号化。8 ビット文字なら 88 ビットなので 76.1 % の節約です

このケースを開く: mississippi

偏った頻度 — この手法が本来ねらう場面. 最も頻度の高い 2 記号が最短の符号を得て、合計はそのぶん下がります。ごく少数の記号が文字列を占めています。それらが最短の符号を得て、合計は固定長の符号化をはるかに下回ります。 — 最も頻度の高い 2 記号が最短の符号を得て、合計はそのぶん下がります。

どの記号も同じ頻度 — 利用できる偏りがない

わかっていること: 平らな分布では、優遇すべき高頻度の記号がありません。ハフマンは固定長の符号にきわめて近いものへと退化します。

費用: p_i = 1/n ⇒ ℓ = log₂n

計算例: 「abcdef」：異なる記号 6 つが各 1 回、16 ビットで符号化。6 記号なら素直な 3 ビット符号で 18 ビットです。

このケースを開く: 均一分布

どの記号も同じ頻度 — 利用できる偏りがない. 平らな分布はほぼ均一な木を生み、符号の長さもどれもほぼ同じになります。平らな分布では、優遇すべき高頻度の記号がありません。ハフマンは固定長の符号にきわめて近いものへと退化します。 — 平らな分布はほぼ均一な木を生み、符号の長さもどれもほぼ同じになります。

ふつうの文章 — 理論上の下限まで 1 ビット

わかっていること: 繰り返される記号と一度きりの記号が現実的に混ざった場合。これが日常の場面で、結果は情報量の下限のすぐ上に着地します。

費用: H ≤ ℓ < H + 1

計算例: 「hello world」：11 文字、異なる記号 8 つ、32 ビットで符号化。88 ビットに対し 63.6 % の節約で、情報量の下限は 31.3 ビットです

このケースを開く: hello world

ふつうの文章 — 理論上の下限まで 1 ビット. 混ざった分布は偏った木を生み、合計は情報量の下限のすぐ上に着地します。繰り返される記号と一度きりの記号が現実的に混ざった場合。これが日常の場面で、結果は情報量の下限のすぐ上に着地します。 — 混ざった分布は偏った木を生み、合計は情報量の下限のすぐ上に着地します。

記号が 1 種類だけ — ハフマンが割り込めない下限

わかっていること: まったく変化のない文字列。情報量は 0 ですが、ハフマンはそれでも 1 記号につき最低 1 ビットを出さねばなりません。1 ビットより短い符号は存在しないからです。

費用: n = 1 ⇒ ℓ = 1

計算例: 「aaaaaaaaaa」：10 文字、異なる記号は 1 つ、10 ビットで符号化。この文字列の情報量は 0 ビットです。

このケースを開く: 単一文字

記号が 1 種類だけ — ハフマンが割り込めない下限. 記号 1 つ、1 つあたり 1 ビット。利用する分布もなく、これより短い符号もありません。まったく変化のない文字列。情報量は 0 ですが、ハフマンはそれでも 1 記号につき最低 1 ビットを出さねばなりません。1 ビットより短い符号は存在しないからです。 — 記号 1 つ、1 つあたり 1 ビット。利用する分布もなく、これより短い符号もありません。

参考文献 (1)

Insight block 3 — the term paper itself: D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE 40(9), 1098–1101, 1952.

全プロセスの詳細解説

ハフマン符号を用いた "hello world" のエンコードによるデータ削減量 5 ステップ
「hello world」をハフマン符号で符号化し、削減量を求めよ。次に、どのような符号であっても達成可能な理論的限界を求めよ。
1. 固定長ASCIIでは、出現頻度にかかわらずすべての文字に同じ8ビットを費やす。ハフマン符号が取り除くのはこの無駄である。すなわち、出現頻度の高い記号には短い符号を、出現頻度の低い記号には長い符号を割り当てる。
  
  $"hello world" : 11 chars \times 8 bits = 88 bits$
2. 符号は出現回数に基づいて構築されるため、まず記号の出現回数を数える。「l」と「o」のみが繰り返し現れ、残りの6文字はそれぞれ1回ずつ出現する。
  
  $ℓ = 3, o = 2, others = 1 each (8 distinct symbols)$
3. シャノンエントロピーは、一記号あたりの平均情報量であり、符号長の厳密な下限です。一意復号可能な符号の平均符号長が、これを下回ることはありません。計算に必要な確率は三種類だけです。「l」が3/11、「o」が2/11、残る六文字がそれぞれ1/11なので、総和は (3/11)(1.8745) + (2/11)(2.4594) + (6/11)(3.4594) となります。
  
  $H = - i \sum p_{i} lo g_{2} p_{i} = 2.845 bits/symbol$
4. 文字列の長さを掛けることで、ビット単位での下限が得られる。ハフマン符号の結果は必ずこの値以上になり、一般にこの下限に到達することはできない。エントロピーは整数とは限らないのに対し、符号長は整数のビット数でなければならないからである。
  
  $11 \times 2.845 = 31.3 bits (entropy floor) \leq 32 (Huffman)$
5. 実際の符号長を求めるため、木を組み立てます。ハフマン法では、そのつど重みが最小の二つを併合します。順に 1+1、1+1、1+1、続いて 2+2、2+2、3+4、4+7 です。併合するたびに、その節の下にある各記号の符号長が一ビットずつ増えます。したがって、符号化後の長さは併合した重みの総和 2+2+2+4+4+7+11 = 32 であり、可視化ツールの表示とも一致します。
  
  $Huffman = 32 bits ⟹ saving = 1 - \frac{32}{88} = 63.6%$
解答

88ビットから32ビットへ — 63.6%の削減。これらの出現頻度に対するエントロピーの下限は31.3ビットであり、ハフマン符号は32ビットとなった。これは最適値より0.7ビット多く、8つの符号長を整数のビット数に切り上げたことによるものである。保証されているのは H ≤ 平均符号長 < H + 1 という挟み込みの不等式であり、ハフマン符号が記号1つあたり最適値を1ビットを超えて上回ることはない。この1ビットの隙間こそが、算術符号が存在する理由である。

$88 \to 32 bits (63.6%) H \leq \overset{ˉ}{ℓ} < H + 1$

学習の道すじ

手作業によるデータ圧縮

この次に LZ77

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

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

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

例題

hello world - ASCIIでは88ビットが32ビットに減り、63.6%節約できます。しかも、エントロピー下限の31.3ビットをわずか0.7ビット上回るだけです。
mississippi - 全十一文字に異なる文字は四つ。88ビットが21ビットになり、sには一ビットの符号が割り当てられます。エントロピー下限との差は0.95ビットで、この中では最大です。
均一分布 - 六種類の記号が一度ずつ現れるため、利用できる頻度の偏りはありません。それでも固定長符号の18ビットに対して16ビットで済みます。六種類では三ビット分の符号を使い切らないからです。
単一文字 - 同じ文字が十個並んでいても、情報量はちょうど0ビットです。それでもハフマン符号では10ビットを使います。一文字につき一ビット必要で、それ未満にはできないためです。