ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

情報量とハフマン符号化

回 1-7　道 1 数と論理と計算量

ハフマン符号化は、よく出る字ほど短く、めったに出ない字ほど長い 0 と 1 の符号を割り当てて、データ全体を短くする可逆の圧縮のやり方です。出る回数の少ない 2 つを束ねることを繰り返して木を作り、根から葉への道の 0 と 1 を符号にします。abracadabra の 11 字は、1 字 3 ビットの固定の長さで 33 ビットのところ、ハフマン符号化では 23 ビットになります。

目安 50 分1-7 (1-1〜1-8 の中)

読み終えたらよく出る字ほど短い符号にすると縮む理由を説明できる

この頁の流れ

  1. 1よく出る字を短くすると、なぜ縮むのか
  2. 2ハフマン符号化はどう符号を決めるのか
  3. 3動かして確かめる
  4. 4縮まないのはどんなときか
  5. 5仕事でどう確かめるか
  6. 6関わる実例
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10一次資料
  11. 11次へ

データの長さと、データが持っている情報の量を切り分けられるようになります。

文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日出典を確かめた日 2026年10月26日

よく出る字を短くすると、なぜ縮むのか

よく出る字に短い符号を、めったに出ない字に長い符号を割り当てると、全体の長さの合計が短くなります。合計の長さは「字の符号の長さ × 出る回数」の足し算なので、回数の多い字を短くするほど効くからです。

コンピュータの中では、英字は 1 字 8 ビット (1 バイト) で保存するのが普通です。a も z も同じ 8 ビットなので、a ばかりの文でも、z ばかりの文でも、長さは同じです。でも、英文では e や t がよく出て、q や z はめったに出ません。どの字も同じ長さで書くのは、もったいなくないでしょうか。

ビットはスイッチのオンとオフで、1 個で 2 通りを表す図

この考えを、損の無い一番よい形にしたのが、1952 年に David Huffman が発表したハフマン符号化です。この回では、abracadabra の 11 字を例に、木を作って符号を決め、何ビットまで縮むかを数えます。

ハフマン符号化はどう符号を決めるのか

ハフマン符号化は、出る回数の少ない 2 つを束ねることを繰り返して木を作り、その木から符号を読み取ります。先に、符号と情報量の言葉を揃えます。

符号化とは、字を 0 と 1 の並びに置き換えること

符号化は、字や記号を、決めた表に従って 0 と 1 の並びに置き換えることです。置き換えた並びを符号と呼び、同じ表で逆に読めば元に戻せます。

abracadabra には a、b、c、d、r の 5 種類の字があります。5 種類を区別するには 3 ビット (8 通り) あれば足りるので、どの字も 3 ビットにすれば、11 字で 33 ビットです。これを固定の長さの符号と呼びます。

字回数固定の長さハフマン符号
a50000
b2001110
r2010111
c1011100
d1100101

右の列は、このあと Python で作るハフマン符号です。5 回出る a が 1 ビット、1 回しか出ない c と d が 3 ビットになっています。

情報量は、確からしさの低さ

情報量は、その字が出たと知ったときの驚きの大きさで、出る確からしさ (確率) が低いほど大きくなります。確率 p の出来事の情報量は −log₂ p ビットと決めます。

表で見ると、次の通りです。

確率情報量
1/21 ビット
1/42 ビット
1/83 ビット

表が出るか裏が出るかの硬貨の結果は、確率 1/2 で 1 ビットです。8 通りから 1 つが同じ確からしさで選ばれるなら 3 ビットで、ちょうど 3 ビットの符号の長さと合います。

情報量の平均をエントロピーと呼びます。1948 年に Claude Shannon が論文「A Mathematical Theory of Communication」で定め、対数の底を 2 にしたときの単位を bits (ビット) と呼びました。論文によると、この呼び名は J. W. Tukey の案です。Shannon は、どう工夫して符号にしても、1 字あたりの平均の長さをエントロピーより短くはできないことも示しました。

ハフマン木の作り方

ハフマン木は、次の手順で作ります。

  1. 字ごとに出る回数を数え、それぞれを 1 つの葉にする
  2. 回数の一番少ない 2 つを取り出し、束ねて 1 つにする。束の回数は 2 つの合計
  3. 束が 1 つになるまで、2 を繰り返す
  4. 根から葉へたどり、左へ進むと 0、右へ進むと 1 を並べたものを、その字の符号にする

abracadabra では、まず 1 回の c と d を束ねて 2 回の束、次に 2 回の b と r を束ねて 4 回の束、その 2 つを束ねて 6 回の束、最後に 5 回の a と束ねて根になります。束ねた回数が少ない字ほど根から遠くなり、符号が長くなります。

次に結ぶ 2 つを、1 段ずつ出して確かめます。heappop で回数の一番少ない 2 つを取り出すたびに、結んだ 2 つと合計を 1 行で表示します。

動かす 結んだ 2 つを 1 段ずつ出す

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

c 1 + d 1 = 2
b 2 + r 2 = 4
cd 2 + br 4 = 6
a 5 + cdbr 6 = 11

1 段ずつ出た「c 1 + d 1 = 2」「b 2 + r 2 = 4」「cd 2 + br 4 = 6」「a 5 + cdbr 6 = 11」が、上の文で説明した束ねる順とそのまま一致します。

枝が 2 本までの木の形で、親から子が 0 から 2 個に分かれる図

Huffman の 1952 年の論文は、こうして作る符号が、字ごとに符号を決めるやり方の中で平均の長さが一番短くなる (冗長さが一番少ない) ことを示しました。

区切りが無くても読めるのは、接頭語の性質のおかげ

ハフマン符号は、どの字の符号も、ほかの字の符号の頭の部分になっていません。この性質を接頭語の性質 (プレフィックスの性質) と呼び、区切りの印が無くても、頭から読んで迷わずに切れます。

たとえば a を 0、b を 01 にすると、01 は「b」とも「a のあとに 1 で始まる何か」とも読めて迷います。ハフマン符号は字を木の葉だけに置くので、ある字の符号の先に別の字が続くことがありません。

動かして確かめる

まず、abracadabra の字ごとの回数、確率、情報量と、エントロピーを計算します。

動かす 字ごとの情報量とエントロピー

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

a 5 0.455 1.14
b 2 0.182 2.46
c 1 0.091 3.46
d 1 0.091 3.46
r 2 0.182 2.46
H 2.04
下限 22.4

5 回出る a の情報量は 1.14 ビットで、1 回しか出ない c と d は 3.46 ビットです。平均のエントロピーは 1 字あたり 2.04 ビットで、11 字を掛けた 22.4 ビットが、字ごとの確率だけを使う符号の長さの下限です。

次に、ハフマン木を作って符号を決め、11 字を符号にします。heapq は、入れた物の中から一番小さい物を取り出す道具で、回数の一番少ない 2 つを取るのに使います。

動かす ハフマン木を作り符号にする

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

a 0
b 110
c 100
d 101
r 111
01101110100010101101110
23 33 88
2.091

符号の合計は 23 ビットになりました。1 字 3 ビットの固定の長さなら 33 ビット、1 字 1 バイトなら 88 ビットです。1 字あたり 2.091 ビットで、エントロピーの 2.04 ビットより少しだけ長く、下限の 22.4 ビットを下回ることはありません。

最後に、符号を頭から読んで元に戻します。区切りの印は入れていません。

動かす 区切り無しで元に戻す

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

0 a
110 b
111 r
0 a
100 c
0 a
101 d
0 a
110 b
111 r
0 a
abracadabra

1 ビットずつ足していき、表にある符号になった所で 1 字に戻しました。接頭語の性質があるので、どこで切るかに迷う所が 1 つもありません。

縮まないのはどんなときか

ハフマン符号化は字の出る回数の偏りを使うので、偏りが無いデータは縮みません。どんな圧縮のやり方でも、すべてのデータを縮めることはできません。

偏りが無ければ、エントロピーは固定の長さと同じ

4 種類の字が同じ回数ずつ出るデータのエントロピーを計算してみます。

動かす 偏りがあるときと無いとき

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

abcdabcdabcdabcd 2.0
aaaaaaaaaaaaabcd 0.993
aaaaaaaaaaaaaaaa 0.0

4 種類が 4 回ずつなら 1 字 2.0 ビットで、4 種類を区別する固定の長さの 2 ビットと同じです。ハフマン符号を作っても全部 2 ビットになり、1 ビットも縮みません。同じ 16 字でも a に偏ると 0.993 ビットに下がり、a だけなら 0 です。毎回 a と分かっている字は、驚きが無く、情報を運ばないからです。

どんな圧縮も、全部を縮めることはできない

8 ビットのデータは 256 通りあります。どれか 1 つでも縮めるなら、縮めた先は 7 ビット以下の並びです。7 ビット以下の並びの数を数えます。

動かす 縮めた先の数を数える

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

8 ビット 256
7 ビット以下 255

長さ 0 の並びを含めても、7 ビット以下の並びは 255 通りしかありません。256 通りのデータを全部それより短い並びに置き換えると、どこかで 2 つのデータが同じ並びになり、元に戻せなくなります。だから、どの可逆の圧縮にも、縮まないか、かえって長くなるデータがあります。

縮まないデータと、縮んだデータをもう一度縮める

Python の zlib は、ZIP や gzip と同じ DEFLATE という形式で圧縮します。でたらめに見えるデータと、同じ文の繰り返しで比べます。

動かす zlib で縮むデータと縮まないデータ

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

1000 1011 1022
1200 29

上の行は、SHA-256 (データから決まった並びを作る計算) を繰り返して作った、偏りの無い 1000 バイトです。圧縮すると 1011 バイトに増え、もう一度圧縮すると 1022 バイトにさらに増えました。下の行の同じ文の 100 回の繰り返しは、1200 バイトが大きく縮みました。JPEG の写真や ZIP のファイルをもう一度 ZIP にしてもほとんど縮まないのは、すでに偏りが取り除かれているからです。

崩れる前提をまとめると、次の通りです。

  • どんなデータも圧縮すれば縮む、という前提。偏りの無いデータや、圧縮済みのデータは縮まず、少し増える
  • 圧縮した長さは秘密と関係無い、という前提。中身の偏りが長さに出るので、長さから中身を当てられることがある (下の実例)
  • 小さいファイルは展開しても小さい、という前提。同じ並びの繰り返しは極端に縮むので、小さい圧縮ファイルが展開すると巨大になることがある

仕事でどう確かめるか

仕事では、データの偏りを先に測り、圧縮が効くかを数で確かめてから使います。

1 つ目は、縮める前に測ることです。上のエントロピーの関数や、zlib.compress で縮んだ長さを、元の長さと比べます。画像や動画、ZIP のように圧縮済みのデータを、さらに圧縮の工程に通しても得はありません。

2 つ目は、展開の大きさに上限を付けることです。Python の公式文書は、ZIP ファイルの展開で、圧縮爆弾 (小さく縮めた巨大なデータ) がディスクを使い切るおそれを注意しています。外から受け取ったファイルを展開するときは、展開した後の大きさを決めた上限で止めます。

3 つ目は、束ねると縮めるを分けて考えることです。tar はファイルを 1 つに束ねる道具で、gzip は縮める道具です。下の図で 2 つのつまみを別々に入れると、ファイルの数と合計の大きさが別々に動きます。

束ねるのと縮めるのは別

関わる実例

圧縮した長さが中身の偏りを映すことは、暗号の通信の穴にもなりました。

TLS の圧縮を突いた CRIME CVE-2012-4929 (NVD の公開 2012 年 9 月 15 日)

米国の脆弱性データベース NVD によると、TLS 1.2 以前の暗号の通信は、データを圧縮してから暗号にするとき、元の長さを隠していませんでした。通信の途中にいる攻撃者は、利用者の送る文に当て推量の文字列を混ぜさせ、暗号にされた長さの違いを見ることで、HTTP の頭にある秘密 (ログインの状態を表す cookie など) を当てられました。CRIME と呼ばれる攻撃です。

崩れた前提は「暗号にすれば、長さから中身は分からない」です。当て推量が秘密と一致すると、繰り返しとして縮んで、暗号文が短くなります。TLS の攻撃をまとめた RFC 7457 は、2.6 節で CRIME を圧縮を突く攻撃として挙げています。

よくある問い

ハフマン符号化は可逆圧縮ですか

ハフマン符号化は可逆圧縮で、符号の表があれば元のデータを 1 ビットも失わずに戻せます。上の「区切り無しで元に戻す」のコードで、abracadabra がそのまま戻りました。細かい情報を捨てて縮める非可逆圧縮とは違い、縮める前と後で中身は同じです。

エントロピー符号化とハフマン符号化の違いは何ですか

エントロピー符号化は、字の確率に合わせて符号の長さを決め、平均の長さをエントロピーに近づけるやり方の総称で、ハフマン符号化はその代表の 1 つです。ハフマン符号は 1 字に整数のビットを割り当てるので、この頁の例のように、平均がエントロピーよりわずかに長くなります。算術符号化のように、もっとエントロピーに近づける方法もあります。

ハフマン符号化はどこで使われていますか

ZIP や gzip、Python の zlib が使う DEFLATE という形式は、繰り返しを短く書き直す LZ77 と、ハフマン符号を組み合わせています。DEFLATE の決まりの RFC 1951 にそう書いてあります。繰り返しを先に縮め、残りの偏りをハフマン符号で縮める 2 段の作りです。

情報量のビットと、データの大きさのビットは同じですか

単位の名前は同じですが、指す物が違います。データの大きさのビットは保存に使う 0 と 1 の数で、情報量のビットはその中に含まれる驚きの量です。a ばかりの 16 字は保存に 128 ビットかかっても、情報量は 0 ビットで、だから大きく縮められます。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。4 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

ハフマン木を作るとき、毎回束ねるのはどの 2 つですか。

2 問目

このコードを動かすと何が出ますか。

符号を足し合わせる

code = {"a": "0", "b": "10",
        "c": "11"}
s = "aaab"
print(sum(len(code[ch])
          for ch in s))

3 問目

a を 0、b を 01、c を 1 とする符号の問題はどれですか。

4 問目

ZIP で圧縮したファイルを、もう一度 ZIP で圧縮するとどうなることが多いですか。

説明課題

次のことを、自分の言葉で 3 行にまとめてください。書いたら、下の模範解答を開いて比べてください。

  • よく出る字ほど短い符号にすると、全体が縮む理由
  • 偏りの無いデータが縮まない理由

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

圧縮の考え方は、配信するファイルの大きさや通信の量を見積もる仕事で、縮む物と縮まない物を見分ける助けになります。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

一次資料

どれも 2026年10月26日に開いて、題と中身を確かめました。

次へ

前の回 1-6Base64 の仕組み64 字の表、= の詰め物、長さ 4/3次の回 1-8チューリングマシンと停止問題テープ、状態、計算できない問題

道 1 数と論理と計算量の回

  1. 1-12 進数と 16 進数桁の重み、変換、表せる範囲頁で読む
  2. 1-2文字コードと文字化けUnicode、UTF-8、Shift_JIS、BOM頁で読む
  3. 1-3計算量を数えるBig-O、ループの回数頁で読む
  4. 1-4論理と真理値表AND、OR、NOT、ド・モルガン準備中
  5. 1-5リトルエンディアンとビッグエンディアンバイトの並び順、ネットワーク、ファイル頁で読む
  6. 1-6Base64 の仕組み64 字の表、= の詰め物、長さ 4/3頁で読む
  7. 1-7情報量とハフマン符号化ビット、確からしさ、圧縮この回
  8. 1-8チューリングマシンと停止問題テープ、状態、計算できない問題頁で読む

道 1 の頁へ戻るほかの道を見る