データ圧縮はなぜできるのか──可逆・非可逆・ランレングス・ハフマンを原理から【情報Ⅰ第36講】

こんにちは、数強塾代表の藤原進之介です。この記事は参考書『藤原進之介の最強120講義』の第36講「データ圧縮（可逆・非可逆・ランレングス・ハフマン）」のWeb版です。共通テスト「情報Ⅰ」での重要度はS（毎年出る。落とすと致命的）、情報Ⅱでの接続先は(3)情報とデータサイエンスです。

圧縮は「ランレングス法は同じ文字が続いたらまとめる、ハフマン法はよく出る文字に短い符号」と手順だけ覚えて終わりにされがちな分野です。しかしその暗記では、問題文で独自の記録形式を定義してくる共通テスト型の出題に太刀打ちできません。この講ではそもそもなぜデータが小さくなるのか、そしてなぜ「どんなデータでも縮む万能圧縮」が原理的に存在しないのかを証明つきで示し、その考え方が情報Ⅱのデータサイエンスにそのまま使われることまでお見せします。

1. この講の問い

なぜデータは小さくできるのか。そして、なぜ「どんなデータでも小さくできる万能の圧縮」は原理的に存在しないのか。

2. 結論

3. なぜそうなるのか

3-1. 「デジタル化」と「圧縮」は別の工程です

標本化・量子化・符号化はアナログを0と1に変える工程、圧縮はその後の0と1の列を言い直す工程です。順番に並んだ別の作業だと切り分けておいてください。デジタル化の手順そのものは第34講 画像のデジタル化（解像度・階調・データ量）にまとめてあります。

ところで、学習指導要領（平成30年告示）解説 情報編を読むと、圧縮は情報Ⅰの(2)「コミュニケーションと情報デザイン」の中に置かれています。書かれているのは次の一文です。

求められているのは「実際に圧縮・展開して特性の違いを把握する」ことであり、なぜ縮むのかという原理は要求されていません。だから多くの授業で圧縮は用語と手順で終わります。本講はそこを埋めます。

3-2. なぜ縮むのか——冗長性という一語

情報を短く言い直せるのは、元の表現に無駄（冗長性）があるからです。冗長性には大きく2種類あります。

逆に言えば、どちらの偏りも無いデータは縮みません。ランダムなビット列や、すでに圧縮済みのZIPファイルをもう一度圧縮しても小さくならないのはこのためです。「圧縮ソフトを2回かければ半分の半分になる」は起きません。

3-3. なぜ「万能圧縮」は存在しないのか（鳩の巣原理）

「どんなファイルでも必ず1ビット以上小さくする圧縮ソフト」は作れません。これは実装が難しいという話ではなく、数学的に不可能です。証明は高校生でも追えます。

可逆圧縮は元に戻せなければなりません。つまり圧縮は一対一（異なる入力は必ず異なる出力になる）である必要があります。

いま、長さ n ビットのデータをすべて n−1 ビット以下に写せたとしましょう。入力は 2ⁿ 通りあります。一方、長さが n−1 ビット以下のビット列は全部でいくつあるでしょうか。

2ⁿ 個のものを 2ⁿ − 1 個の箱に一対一で入れることはできません。これが鳩の巣原理です。したがって必ずどこかで衝突が起き、元に戻せなくなります。

3-4. だから可逆と非可逆を使い分ける

判断基準はただ一つ、「1ビット変わったら困るか」です。プログラムは1ビット変わったら動きません。会計データは1円変わったら別の数字です。だから可逆でなければなりません。一方、写真の空のグラデーションが隣の色に1段階ずれても、人間の目は気づきません。

ここを私はしつこく言います。非可逆圧縮は「人間の知覚の鈍さ」という外部条件を利用しているのであって、数学的に情報が保存されているわけではありません。だから同じJPEGでも、人間が見る写真なら十分でも、機械が微細な傷を検査する画像には使えないのです。

3-5. なぜ接頭符号でないと復号できないのか

ハフマン法は文字ごとに長さの違う符号を割り当てます（可変長符号）。ここで必ず問題になるのが区切りです。

文部科学省の「情報Ⅰ」教員研修用教材は、この失敗をわざわざ先に見せています。i に「1」、n に「01」、t に「100」を割り当てると、並べたビット列は別の読み方もできてしまう、と。

区切り記号を入れれば解決しますが、それではデータが増えて本末転倒です。そこで課す条件が接頭符号（prefix code）——どの符号も、他の符号の先頭部分になっていないことです。

なぜこれで復号できるのでしょうか。ビット列を左から1ビットずつ読み、手元のビット列が符号表のどれかに一致した瞬間に文字を確定させます。接頭符号なら「一致したけれど、実はもっと長い符号の途中だった」という事態が起こり得ません。だから先読みも後戻りも不要で、一意に復号できるのです。

ハフマン木を使うと接頭符号が自動的にできあがります。文字はすべて葉に置かれ、葉は他の葉の途中を通らないからです。これが「木で作る」ことの意味であり、単なる作図手順ではありません。

3-6. なぜ「よく出る記号に短い符号」で縮むのか

記号 i の符号長を 、出現確率を とすると、1文字あたりの平均符号長は次の式で表せます。

固定長符号ではすべての が同じなので、L はその値そのものです。ここで出現確率の大きい記号の符号長を1減らし、小さい記号の符号長を1増やすとどうなるでしょうか。L の変化は「−（大きい確率）＋（小さい確率）」ですから、負になる＝平均が縮みます。

これがハフマン法のすべてです。ハフマン木を「出現回数の小さい2つから順に併合する」のは、出現回数の小さいものほど木の深いところ（＝長い符号）に押し込むための手続きにすぎません。手順を覚えるのではなく、この一行を覚えてください。

なお、この平均符号長には理論的な下限があり、情報量（エントロピー）と呼ばれます。情報処理推進機構（IPA）の基本情報技術者試験シラバスでは「情報量の概念，事象の生起確率と情報量との関係を理解する」が情報理論の項目として置かれ、符号理論の用語例に「ハフマン符号，情報源符号化（データ圧縮）」が並びます。高校の情報Ⅰでは確率の話が外されていますが、圧縮は本来「確率の話」であることは押さえておいてください。第43講 論理演算と同じで、情報Ⅰの各項目は必ずその先の理論につながっています。

4. 手で確かめる

4-1. ランレングス符号化——縮む例と、膨らむ例

「同じ文字が続いたら〈文字＋連続回数〉に置き換える」だけです。

下の行を見てください。2倍に膨らんでいます。 3-3で証明した「必ず膨らむデータが存在する」が、最短の形で目に見えました。教員研修用教材も同じことを intelligence という単語で示しており、ランレングス法をかけると22文字になり「ほとんどの文字の後ろに『1』がつくために約2倍のデータ量となってしまう」と書いています。

4-2. 白黒画像の1行をビットで数える

32画素のモノクロ1行（1画素1ビット）を考えます。白が12、黒が3、白が17と並んでいるとしましょう。

11111111111100011111111111111111
（白12 → 黒3 → 白17 の3つのラン）

そのままなら32ビットです。これを「色1ビット＋（長さ−1）を5ビット」の6ビット単位で3つのランとして書けば、6 × 3 = 18ビット。圧縮率は 18 ÷ 32 = 56.3% になります。

FAXが実用になるのはこの構造のおかげです（教員研修用教材もランレングス法をFAXの例で説明しています）。ランの数が少ないほど縮むので、細かい網点が並ぶ写真をこの方式で送ると悲惨なことになります。手法には向き不向きがあるのです。

4-3. ハフマン木を手で作る

文字列 abracadabra（11文字）を圧縮します。出現回数は a=5、b=2、r=2、c=1、d=1 の5種類です。

5種類なので固定長なら1文字3ビット必要です（2²=4 では足りず、2³=8 で足ります）。11 × 3 = 33ビット。これが比較の基準になります。

できた木がこちらです。左の枝に0、右の枝に1を振ります。

接頭符号になっていることを確かめます。0 は他のどの符号の先頭でもありません（他はすべて1で始まります）。100 から 111 までは互いに同じ長さなので、一方が他方の先頭になることはあり得ません。合格です。

4-4. 圧縮率と平均符号長を計算する

abracadabra を符号化すると次のようになります。

a   b   r   a  c   a  d   a  b   r   a
0  110 111  0 100  0 101  0 110 111  0
 
→ 01101110100010101101110  （23ビット）

理論的な下限であるエントロピーも計算しておきます。

ハフマンの2.09ビットは、下限2.04ビットのわずか0.05ビット上です。ハフマン符号がほぼ最適だということが、自分の手で確認できました。

4-5. 接頭符号でないと何が起きるか（実演）

わざと a=0、b=01、r=1 としてみます。b の符号「01」は、a の符号「0」で始まっていますね。接頭符号ではありません。すると 01 という2ビットは、

の2通りに読めてしまいます。どちらが正しいか、ビット列だけからは決まりません。 元に戻せない＝可逆圧縮として失敗です。復号プログラムを書いても、入力によって答えが割れます。ハフマン木を経由して符号を作れば、この事故は原理的に起こりません。

4-6. Pythonで検算する

以下は私の手元（Python 3）で実際に実行し、出力を確認したものです。コメントの行が実際の出力です。

from collections import Counter
s = "abracadabra"
code = {'a':'0', 'c':'100', 'd':'101', 'b':'110', 'r':'111'}
 
ks = list(code.values())
print(all(not (x != y and y.startswith(x)) for x in ks for y in ks))
# True   ← どの符号も他の符号の先頭になっていない（接頭符号）
 
bits = ''.join(code[c] for c in s)
print(bits, len(bits))
# 01101110100010101101110 23
 
print(3 * len(s), len(bits) / (3 * len(s)))
# 33 0.696969696969697

次に復号します。左から1ビットずつ足していき、符号表に一致したら確定させるだけです。先読みも後戻りもしていないことを目で確認してください。

inv = {v: k for k, v in code.items()}
buf, out = '', ''
for b in bits:
    buf += b
    if buf in inv:
        out += inv[buf]
        buf = ''
print(out, out == s)
# abracadabra True

最後にエントロピーです。

import math
n = len(s)
f = Counter(s)
H = -sum((c/n) * math.log2(c/n) for c in f.values())
print(H)
# 2.0403666152949836

自分で書いて動かすと、「接頭符号だから復号できる」が実感に変わります。第40講 2進数・10進数・16進数の変換と同じで、圧縮も手で確かめられる範囲の話なのです。

5. 共通テストではこう出る（重要度S）

デジタル化とデータ量の計算は毎年出ます。圧縮はその一部として問われます。ここでは設問の型だけを整理します（当塾では共通テストの問題文・選択肢・図表は転載していません）。

落とし穴

• 圧縮率の向きを取り違える。 「圧縮率が高い＝よく縮んだ」と日常語で読むと、教材の定義と逆になります。
• 「圧縮すれば必ず小さくなる」と思い込む。 ランレングスは膨らむことがあります。
• 符号表の分を忘れる。 短いデータでは表のほうが大きくなります。
• 接頭符号でない符号表を平気で選ぶ。 選択肢に混ぜられます。必ず「他の符号の先頭になっていないか」を確認してください。
• 非可逆圧縮を「劣化コピー」とだけ覚える。 捨てているのは「人間が気づきにくい情報」であって、ランダムに削っているのではありません。

練習用の自作問題（本記事オリジナル）

共通テスト情報Ⅰの学習計画全体については共通テスト「情報Ⅰ」対策はいつから何をやるべきかにまとめました。120講の全体像は情報Ⅰ 最強120講義の目次から辿れます。

6. 情報Ⅱではこうなる

6-1. 圧縮は情報Ⅱでも名指しで出てきます

学習指導要領解説 情報編の情報Ⅱ(2)ア(ウ)「コンテンツを様々な手段で適切かつ効果的に社会に発信する方法を理解すること」には、こう書かれています。

情報Ⅰでは「実際に圧縮・展開して特性の違いを把握する」（＝体験）だったものが、情報Ⅱでは発信のための技術として理解する対象に上がっています。同じ「圧縮」という語でも、要求水準が違うのです。

6-2. 本丸は「次元削減」——非可逆圧縮の一般化

そして情報Ⅱ(3)「情報とデータサイエンス」で、圧縮の発想は主成分分析による次元削減として再登場します。文部科学省「情報Ⅱ」教員研修用教材の学習14を読んだとき、私は思わず声が出ました。

「捨てる」という動詞が一致しています。 非可逆圧縮が「人間の知覚に効かない情報を捨てる」のに対し、次元削減は「対象の弁別に効かない成分を捨てる」。捨てる基準が〈人間の目〉から〈データの分散〉に変わっただけで、構造はまったく同じです。

さらに文部科学省が公開している情報Ⅱ向けの教材スライドは、タイトルからしてこうなっています。

国の教材そのものが、主成分分析を「圧縮」と呼んでいるのです。第36講と第114講がつながっているというのは、私の見立てではなく教材の文言そのものです。

6-3. 8次元を2次元に落として67%

この教材は、独立行政法人統計センターが公開している教育用標準データセット「SSDSE-家計消費（SSDSE-C）」を題材にしています。都道府県庁所在市別に、1世帯当たりの食料の年間支出金額を品目別に集めたデータ（出典は総務省統計局「家計調査」）です。これをRの prcomp 関数にかけて主成分分析を行い、こう結論します。

8次元を2次元に落として、情報の67%が残った。 これはまさに、写真をJPEGで小さくしたときの圧縮率と画質のトレードオフそのものです。教材では寄与率（Proportion of Variance）を「データ全体のばらつきをどれくらい説明できているか」、累積寄与率（Cumulative Proportion）を「その成分までで，データ全体のばらつきをどれくらい説明できているか」と定義しています。これが情報Ⅱ版の「画質」だと思ってください。

6-4. 情報Ⅰと情報Ⅱの扱いの違い

情報Ⅰの圧縮は「運ぶため」、情報Ⅱの圧縮は「見るため」。 捨てるという操作は同じでも、目的が変わります。この一段の跳躍を高校のうちに見ておくと、大学のデータサイエンスで主成分分析が出てきたときに「ああ、あのJPEGの話か」と着地できます。

まとめ

• データが縮むのは冗長性（同じものが続く／頻度の偏り）があるから。偏りが無いデータは縮まない。
• 鳩の巣原理により、あらゆるデータを短くする万能圧縮は存在しない。可逆圧縮は必ず膨らむデータを持つ。
• 可逆と非可逆の判断基準は「1ビット変わったら困るか」の一点。非可逆は人間の知覚の鈍さを利用している。
• 可変長符号は接頭符号でなければ復号できない。ハフマン木を使えば自動的に接頭符号になる。
• ハフマンの核心は「出現確率の大きい記号の符号長を減らせば平均符号長が縮む」の一行。手順は結果にすぎない。
• 情報Ⅱでは同じ発想が主成分分析による次元削減として再登場する。文科省の教材自身がそれを「圧縮」と呼んでいる。

出典（すべて2026年8月3日に取得）

• 文部科学省「高等学校学習指導要領（平成30年告示）解説 情報編」平成30年7月
• 文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第2章 コミュニケーションと情報デザイン（令和2年）
• 文部科学省「高等学校情報科『情報Ⅱ』教員研修用教材」第3章 情報とデータサイエンス 前半（令和2年7月）
• 文部科学省「情報とデータサイエンス 主成分分析による次元縮約」（2024年3月公開）
• 独立行政法人統計センター「SSDSE（教育用標準データセット）」
• 情報処理推進機構（IPA）「基本情報技術者試験（レベル2）シラバス Ver.9.2」

制度に関する記述は2026年8月時点のものです。情報Ⅰがなぜ必修になったのかという背景は情報Ⅰはなぜ必修になったのかに書きました。