データ圧縮とハフマン符号をやさしく図解 — 可逆・非可逆・符号木

「ZIPとJPEGは何が違うの？」「ハフマン符号ってどう作るの？」——データ圧縮は、ムダを削ってサイズを小さくする技術です。この記事では、可逆・非可逆の違いから、出現頻度を使うハフマン符号の作り方（符号木）までを図解します。木構造の基礎は データ構造、文字とビットの話は 文字コード もどうぞ。

データ圧縮とは — 可逆と非可逆

データ圧縮には大きく2種類あります。完全に元に戻せる「可逆圧縮」と、一部を捨てて大きく縮める「非可逆圧縮」です。用途によって使い分けます。

プログラムや文書は1ビットでも変わると壊れるので可逆一択。一方、写真や音楽は人間が気づきにくい細部を捨てても実用上問題ないので、非可逆で大きく縮めます。ハフマン符号は可逆圧縮の代表的な手法です。

まずは簡単な例：ランレングス圧縮

圧縮の考え方を、いちばん単純なランレングス圧縮でつかみましょう。同じ値が連続する部分を「値＋個数」で置き換える方法です。

AAAAABBBBBBBCC （14文字）
→ A5 B7 C2 （6文字に短縮）

同じ色が続く画像（FAX・アイコン等）で効果的です。ただし「ABABAB…」のように連続しないデータでは、かえって増えることもあります。データの性質に合った圧縮法を選ぶのが大切、という好例です。

ハフマン符号 — よく出る文字ほど短く

ハフマン符号の発想はシンプルです。ふつうは1文字を固定のビット数で表しますが、よく出てくる文字ほど短いビット列、めったに出ない文字ほど長いビット列を割り当てれば、全体のビット数を減らせます。モールス信号で、よく使う「E」を短点1つ、まれな「Q」を長く表すのと同じ考え方です。

ハフマン木の作り方

次の出現頻度の文字を圧縮してみます：A（頻度5）・B（頻度2）・C（頻度1）・D（頻度1）。頻度の小さいものから2つずつ束ねて、頻度を足していくと、1本の木（ハフマン木）ができます。

根（一番上）から各文字までたどると、符号が決まります。

よく出る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%削減）。文字の出現に偏りがあるほど、ハフマン符号はよく効きます。なお、どの符号も他の符号の先頭部分になっていない（語頭条件）ため、区切りがなくても一意に復号できます。

基本情報技術者試験ではこう出る

「可逆圧縮と非可逆圧縮の違い・具体例（ZIP/JPEG）」「ハフマン符号の符号を求める」「ハフマン符号での平均ビット数・圧縮率の計算」「ランレングス圧縮」が定番です。押さえるべきは、可逆＝完全に戻せる（文書・プログラム）／非可逆＝大きく縮むが戻せない（画像・音声）と、ハフマン＝頻度が高い文字ほど短いビットという原則。木を作って符号を求める手順も練習しておきましょう。

よくある質問

Q. なぜハフマン符号は区切り文字がなくても復号できるの？
A. どの符号も「他の符号の先頭にならない」ように作られているからです（語頭符号・接頭符号）。たとえばAが「0」なら、他の符号は必ず「1」で始まるので、先頭から読んでいけば迷わず1文字ずつ区切れます。

Q. 圧縮率は「大きい方がいい」の？
A. 定義によります。「圧縮後÷圧縮前」で表す場合は小さいほどよく縮んでいます（例：40%）。「どれだけ削減したか」で表す場合は大きいほど良い（例：60%削減）。問題文がどちらの定義かを確認しましょう。

Q. どんなデータでも圧縮できる？
A. いいえ。すでにランダムに近い（偏りのない）データは、ほとんど縮みません。圧縮は「データの偏り・くり返し」を利用するため、規則性のないデータには効きません。すべてのデータを必ず縮められる万能な圧縮法は存在しません。

まとめ

データ圧縮は、可逆（完全に戻せる／文書・プログラム）と非可逆（大きく縮むが戻せない／画像・音声）の2種類。可逆の代表ハフマン符号は、頻度が高い文字ほど短いビットを割り当て、木をたどって符号を決めます。木構造・文字コードと合わせて理解すると、情報の表し方の全体像がつながります。

関連ページ: データ構造 ／ 文字コード ／ 誤り検出・訂正 ／ 記事一覧