可逆圧縮アルゴリズムの種類と仕組みを図解 — ハフマン符号・LZ77・ランレングス
※この記事にはプロモーション（広告）が含まれます。広告表記の方針
「ZIPとJPEGは何が違うの？」「可逆圧縮ってどういう仕組み？」——データ圧縮は、ムダを削ってサイズを小さくする技術です。この記事では、可逆・非可逆の違いから、代表的な可逆圧縮アルゴリズムの種類と仕組み（ランレングス・ハフマン符号・辞書式LZ77）、身近なファイル形式の例、ハフマン木の作り方までを図解します。木構造の基礎は データ構造、文字とビットの話は 文字コード も役に立ちます。
データ圧縮とは — 可逆と非可逆
データ圧縮には大きく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でたどる考え方は、二分探索の可視化の「半分ずつ絞る」動きとも通じます。文字をビットで表す基礎は 文字コード もあわせて見てみてください。
代表的な可逆圧縮アルゴリズムの種類
可逆圧縮アルゴリズムとは、圧縮したデータを1ビットも欠けずに元どおりに戻せる圧縮手順のことです。やっていることは大きく分けて2系統——「くり返しを短く書き直す」（ランレングス・辞書式）と、「よく出る記号を短い符号で表す」（ハフマン符号・算術符号）です。
| アルゴリズム | 系統 | 仕組み | 使われる例 |
|---|---|---|---|
| ランレングス圧縮 | くり返し | 同じ値の連続を「値＋個数」に置き換える | FAX・単純な画像 |
| 辞書式（LZ77 / LZ78 / LZW） | くり返し | 過去に出た並びを「参照」に置き換える | ZIP・gzip・PNG・GIF |
| ハフマン符号 | 符号化 | 出現頻度が高い記号ほど短いビットを割り当てる | ZIP・gzip（Deflateの後段） |
| 算術符号 | 符号化 | データ全体を1つの小数で表し、1記号あたり1ビット未満まで詰められる | 画像・動画の符号化 |
| BWT（ブロックソート） | 前処理 | 同じ文字が並びやすいように並べ替えてから圧縮する | bzip2 |
実際のZIPやgzipは、LZ77でくり返しを縮め、さらにハフマン符号で仕上げる「Deflate」という二段構えです。系統の違う手法を組み合わせると、単独よりよく縮みます。いずれも可逆なので、文書やプログラムを1ビットも損なわずに縮められます。
各アルゴリズムの仕組み（もう少し詳しく）
ランレングス圧縮の仕組み。 同じ値が連続する部分を「値＋個数」にまとめます。たとえば AAAAABBB は A5B3 と表せ、8文字が4文字に。FAXやベタ塗りの画像のように同じ値が長く続くデータで効きますが、連続しないデータではかえって増えることもあります。
ハフマン符号の仕組み。 よく出る記号ほど短いビット、めったに出ない記号ほど長いビットを割り当てて、全体の平均ビット数を減らします。どの符号も他の符号の先頭にならない（語頭条件）ため、区切りがなくても一意に戻せます（上のハフマン木の例を参照）。
辞書式（LZ系）の仕組み。 一度出てきた並びを、「何文字前から、何文字ぶんコピー」という参照に置き換えます。たとえば abcabcabc は「abc ＋ 3文字前から6文字コピー」と表せます。ソースコードや文書のように同じ並びがくり返し現れるデータに強く、ZIP・gzip・PNGの中心です。
なぜ可逆（元に戻せる）なのか。 これらはどれも情報を捨てているのではなく、「同じ内容をより短い表現に置き換えているだけ」だからです。復元の手順をたどれば、1ビットも欠けずに元のデータに戻せます。ここが、細部を捨てて縮める非可逆圧縮（JPEG・MP3など）との決定的な違いです。
辞書式（LZ77）を手でたどってみる
ZIPの中心にあるLZ77の動きを、ABCABCABCD（10文字）で追ってみます。先頭から読み進め、すでに書いた部分に同じ並びがあれば「何文字戻って何文字コピー」に置き換えます。
| 読む部分 | 過去に同じ並びは？ | 出力 |
|---|---|---|
A B C（1〜3文字目） | 無し（初登場） | そのまま A B C |
ABCABC（4〜9文字目） | 3文字前から始まる並びと6文字一致 | （3文字戻る, 6文字コピー） |
D（10文字目） | 無し | そのまま D |
10文字が A B C （3戻る,6文字） D の5要素で表せました。「3文字戻って6文字」はコピー元とコピー先が重なっていますが、1文字ずつ順にコピーするので、書いたそばから次のコピー元になり問題ありません。
展開するときは逆をたどるだけです。ABC を書き、3文字戻って1文字ずつ6回コピー（ABCABC）、最後に D ——元の ABCABCABCD にぴったり戻ります。これが「可逆」の正体です。
可逆圧縮の例 — 身近なファイル形式
ふだん使っているファイル形式の多くが、実は上のアルゴリズムの組み合わせです。
| 分野 | 形式 | 中身の方式 |
|---|---|---|
| ファイル圧縮 | ZIP・gzip（.tar.gz） | Deflate（LZ77＋ハフマン符号） |
| ファイル圧縮 | 7z | LZMA（LZ77系＋レンジ符号） |
| ファイル圧縮 | bzip2 | BWT＋ハフマン符号 |
| 画像 | PNG | 予測フィルタ＋Deflate |
| 画像 | GIF | LZW（色数は最大256色） |
| 音声 | FLAC | 波形を予測し、予測との差分を符号化 |
| Web通信 | HTTPのgzip・Brotli | 辞書式＋符号化（HTMLやJSONを転送前に縮める） |
どれも展開すれば元のデータに1ビットも欠けずに戻るので、プログラム・文書・スクリーンショット・音源の保存など、劣化が許されない用途に使われます。
圧縮方式の種類（可逆・非可逆の一覧）
非可逆圧縮も含めて、圧縮方式の種類を「何を利用して縮めるか」で整理すると次のようになります。
| 種類 | 方式 | 何を利用して縮める？ | 例 |
|---|---|---|---|
| 可逆 | ランレングス | 同じ値の連続 | FAX |
| 辞書式（LZ系） | 同じ並びのくり返し | ZIP・PNG・GIF | |
| エントロピー符号化（ハフマン・算術符号） | 記号の出現頻度の偏り | ZIPの後段・JPEGの後段 | |
| 非可逆 | 変換符号化＋量子化 | 画像を周波数成分に分け、目立たない細かい成分を粗く丸める | JPEG |
| 聴覚心理モデル | 人に聞こえにくい音（大きな音にかき消される音など）を削る | MP3・AAC | |
| フレーム間予測 | 前後のコマとの差分だけを記録し、さらに細部を丸める | H.264・H.265（MP4などの動画） |
ポイントは、非可逆方式も最後の段では可逆の符号化を使っていることです。たとえばJPEGは「量子化で細部を捨てる（ここが非可逆）」→「残ったデータをハフマン符号で詰める（ここは可逆）」の順。情報を捨てる工程が1つでも入れば、全体としては非可逆になります。
基本情報技術者試験ではこう出る
「可逆圧縮と非可逆圧縮の違い・具体例（ZIP/JPEG）」「ハフマン符号の符号を求める」「ハフマン符号での平均ビット数・圧縮率の計算」「ランレングス圧縮」が頻出です。押さえるべきは、可逆＝完全に戻せる（文書・プログラム）／非可逆＝大きく縮むが戻せない（画像・音声）と、ハフマン＝頻度が高い文字ほど短いビットという原則。木を作って符号を求める手順も練習しておきましょう。
よくある質問
Q. 可逆圧縮アルゴリズムにはどんな種類がある？
A. 大きく「くり返しを短く書き直す」系（ランレングス・辞書式のLZ77/LZ78/LZW）と、「よく出る記号を短い符号にする」系（ハフマン符号・算術符号）があります。ZIPやgzipはLZ77とハフマン符号を組み合わせたDeflateを使っています。
Q. 可逆圧縮の身近な例は？
A. ZIP・gzip・7z、画像のPNG・GIF、音声のFLACなどです。展開すれば元のデータに完全に戻ります。JPEG・MP3・MP4（H.264）は非可逆です。
Q. なぜハフマン符号は区切り文字がなくても復号できるの？
A. どの符号も「他の符号の先頭にならない」ように作られているからです（語頭符号・接頭符号）。たとえばAが「0」なら、他の符号は必ず「1」で始まるので、先頭から読んでいけば迷わず1文字ずつ区切れます。
Q. 圧縮率は「大きい方がいい」の？
A. 定義によります。「圧縮後÷圧縮前」で表す場合は小さいほどよく縮んでいます（例：40%）。「どれだけ削減したか」で表す場合は大きいほど良い（例：60%削減）。問題文がどちらの定義かを確認しましょう。
Q. どんなデータでも圧縮できる？
A. いいえ。すでにランダムに近い（偏りのない）データは、ほとんど縮みません。圧縮は「データの偏り・くり返し」を利用するため、規則性のないデータには効きません。すべてのデータを必ず縮められる万能な圧縮法は存在しません。
まとめ
データ圧縮は、可逆（完全に戻せる／文書・プログラム）と非可逆（大きく縮むが戻せない／画像・音声）の2種類。可逆圧縮アルゴリズムは、くり返しを短く書き直す系（ランレングス・LZ77などの辞書式）と、よく出る記号を短い符号にする系（ハフマン符号・算術符号）に分かれ、ZIPやPNGはこれを組み合わせています。ハフマン符号は頻度が高い文字ほど短いビットを割り当て、木をたどって符号を決めます。木構造・文字コードと合わせて理解すると、情報の表し方の全体像がつながります。