データ圧縮とハフマン符号をやさしく図解 — 可逆・非可逆・符号木
「ZIPとJPEGは何が違うの？」「ハフマン符号ってどう作るの？」——データ圧縮は、ムダを削ってサイズを小さくする技術です。この記事では、可逆・非可逆の違いから、出現頻度を使うハフマン符号の作り方（符号木）までを図解します。木構造の基礎は データ構造、文字とビットの話は 文字コード もどうぞ。
データ圧縮とは — 可逆と非可逆
データ圧縮には大きく2種類あります。完全に元に戻せる「可逆圧縮」と、一部を捨てて大きく縮める「非可逆圧縮」です。用途によって使い分けます。
| 可逆圧縮 | 非可逆圧縮 | |
|---|---|---|
| 元に戻せる？ | 完全に戻せる | 完全には戻せない |
| 圧縮の効き | ほどほど | 大きく縮む |
| 向くデータ | 文書・プログラム・データ | 写真・音声・動画 |
| 例 | ZIP・PNG・GIF | JPEG・MP3・MP4 |
プログラムや文書は1ビットでも変わると壊れるので可逆一択。一方、写真や音楽は人間が気づきにくい細部を捨てても実用上問題ないので、非可逆で大きく縮めます。ハフマン符号は可逆圧縮の代表的な手法です。
まずは簡単な例：ランレングス圧縮
圧縮の考え方を、いちばん単純なランレングス圧縮でつかみましょう。同じ値が連続する部分を「値＋個数」で置き換える方法です。
AAAAABBBBBBBCC （14文字）
→ A5 B7 C2 （6文字に短縮）
同じ色が続く画像（FAX・アイコン等）で効果的です。ただし「ABABAB…」のように連続しないデータでは、かえって増えることもあります。データの性質に合った圧縮法を選ぶのが大切、という好例です。
ハフマン符号 — よく出る文字ほど短く
ハフマン符号の発想はシンプルです。ふつうは1文字を固定のビット数で表しますが、よく出てくる文字ほど短いビット列、めったに出ない文字ほど長いビット列を割り当てれば、全体のビット数を減らせます。モールス信号で、よく使う「E」を短点1つ、まれな「Q」を長く表すのと同じ考え方です。
ハフマン木の作り方
次の出現頻度の文字を圧縮してみます：A（頻度5）・B（頻度2）・C（頻度1）・D（頻度1）。頻度の小さいものから2つずつ束ねて、頻度を足していくと、1本の木（ハフマン木）ができます。
根（一番上）から各文字までたどると、符号が決まります。
| 文字 | 頻度 | ハフマン符号 | ビット長 |
|---|---|---|---|
| A | 5 | 0 | 1ビット |
| B | 2 | 10 | 2ビット |
| C | 1 | 110 | 3ビット |
| D | 1 | 111 | 3ビット |
よく出るAが最短の1ビット、まれなC・Dが3ビット。これがハフマン符号の効果です。
どれだけ縮む？ — 平均ビット数の比較
4種類の文字を固定長で表すには、1文字2ビット必要です（00・01・10・11）。全9文字なら 9×2 ＝ 18ビット。一方ハフマン符号では：
A:5×1 ＋ B:2×2 ＋ C:1×3 ＋ D:1×3 ＝ 5＋4＋3＋3 ＝ 15ビット
18ビットが15ビットに縮みました（約17%削減）。文字の出現に偏りがあるほど、ハフマン符号はよく効きます。なお、どの符号も他の符号の先頭部分になっていない（語頭条件）ため、区切りがなくても一意に復号できます。
🌲 木構造でたどるしくみを理解するなら：ハフマン木はデータ構造で扱う木構造（二分木）そのものです。根から葉へ0/1でたどる考え方は、二分探索の可視化の「半分ずつ絞る」動きとも通じます。文字をビットで表す基礎は 文字コード もどうぞ。
代表的な可逆圧縮アルゴリズム
可逆圧縮（完全に元に戻せる）には、いくつかの代表的なアルゴリズムがあります。実際のZIPなどは複数を組み合わせています。
| アルゴリズム | 仕組み | 使われる例 |
|---|---|---|
| ランレングス圧縮 | 同じ値の連続を「値＋個数」に置き換える | FAX・単純な画像 |
| ハフマン符号 | 出現頻度が高い記号ほど短いビットを割り当てる | JPEG・ZIPの一部 |
| 辞書式（LZ77 / LZ78 / LZW） | 過去に出た並びを「参照」に置き換える | ZIP・gzip・PNG・GIF |
ZIPやgzipは「辞書式（LZ系）でくり返しを縮め、さらにハフマン符号で仕上げる」という二段構えが定番です。いずれも可逆なので、文書やプログラムを1ビットも損なわずに縮められます。
各アルゴリズムの仕組み（もう少し詳しく）
ランレングス圧縮の仕組み。 同じ値が連続する部分を「値＋個数」にまとめます。たとえば AAAAABBB は A5B3 と表せ、8文字が4文字に。FAXやベタ塗りの画像のように同じ値が長く続くデータで効きますが、連続しないデータではかえって増えることもあります。
ハフマン符号の仕組み。 よく出る記号ほど短いビット、めったに出ない記号ほど長いビットを割り当てて、全体の平均ビット数を減らします。どの符号も他の符号の先頭にならない（語頭条件）ため、区切りがなくても一意に戻せます（上のハフマン木の例を参照）。
辞書式（LZ系）の仕組み。 一度出てきた並びを、「何文字前から、何文字ぶんコピー」という参照に置き換えます。たとえば abcabcabc は「abc ＋ 3文字前から6文字コピー」と表せます。ソースコードや文書のように同じ並びがくり返し現れるデータに強く、ZIP・gzip・PNGの中心です。
なぜ可逆（元に戻せる）なのか。 これらはどれも情報を捨てているのではなく、「同じ内容をより短い表現に置き換えているだけ」だからです。復元の手順をたどれば、1ビットも欠けずに元のデータに戻せます。ここが、細部を捨てて縮める非可逆圧縮（JPEG・MP3など）との決定的な違いです。
基本情報技術者試験ではこう出る
「可逆圧縮と非可逆圧縮の違い・具体例（ZIP/JPEG）」「ハフマン符号の符号を求める」「ハフマン符号での平均ビット数・圧縮率の計算」「ランレングス圧縮」が定番です。押さえるべきは、可逆＝完全に戻せる（文書・プログラム）／非可逆＝大きく縮むが戻せない（画像・音声）と、ハフマン＝頻度が高い文字ほど短いビットという原則。木を作って符号を求める手順も練習しておきましょう。
よくある質問
Q. なぜハフマン符号は区切り文字がなくても復号できるの？
A. どの符号も「他の符号の先頭にならない」ように作られているからです（語頭符号・接頭符号）。たとえばAが「0」なら、他の符号は必ず「1」で始まるので、先頭から読んでいけば迷わず1文字ずつ区切れます。
Q. 圧縮率は「大きい方がいい」の？
A. 定義によります。「圧縮後÷圧縮前」で表す場合は小さいほどよく縮んでいます（例：40%）。「どれだけ削減したか」で表す場合は大きいほど良い（例：60%削減）。問題文がどちらの定義かを確認しましょう。
Q. どんなデータでも圧縮できる？
A. いいえ。すでにランダムに近い（偏りのない）データは、ほとんど縮みません。圧縮は「データの偏り・くり返し」を利用するため、規則性のないデータには効きません。すべてのデータを必ず縮められる万能な圧縮法は存在しません。
まとめ
データ圧縮は、可逆（完全に戻せる／文書・プログラム）と非可逆（大きく縮むが戻せない／画像・音声）の2種類。可逆の代表ハフマン符号は、頻度が高い文字ほど短いビットを割り当て、木をたどって符号を決めます。木構造・文字コードと合わせて理解すると、情報の表し方の全体像がつながります。