応用情報 令和6年度 春期 問1基礎理論に関する問題

正解は「出現頻度の高い記号に短い符号を割り当てる可変長符号化方式である」です。

ハフマン符号化はデータを「縮める（圧縮する）」方法の1つです。アイデアはシンプルで「よく出てくる文字には短い記号、めったに出てこない文字には長い記号」を割り当てます。

たとえば「a」が100回、「z」が1回出てくる文章なら、「a」を1bit、「z」を10bitで表すと、全体としてかなり縮みます。

ただし圧縮率はデータ次第で、たとえばすべての文字が均等に出現する場合は縮みません。

覚え方：「よく出る記号は短く、めったに出ない記号は長く」。

正解は b「出現頻度の高い記号に短い符号を割り当てる可変長符号化方式である」です。

ハフマン符号化（Huffman Coding）は1952年に David A. Huffman が考案した可変長符号化方式で、以下の特徴があります：

• 可逆圧縮：元データを完全に復元できる
• 可変長符号：記号ごとに異なるビット長を割り当てる
• 接頭符号性（Prefix-free）：どの符号も別の符号の接頭辞にならない → 区切り文字不要
• 最適性：1記号ずつ符号化する方式としては理論限界（情報エントロピー）に最も近い

アルゴリズム：

1. 各記号の出現頻度を集計

2. 頻度が最小の2記号をマージし、新ノードの頻度はその合計

3. 最小2要素のマージを繰り返し、1本の2分木に

4. 木の左枝に0、右枝に1を割り当て、葉までの経路を符号とする

例：頻度 A=5, B=2, C=1, D=1 のとき、A→0, B→10, C→110, D→111 のような符号が得られます。

用途：

• ZIP / DEFLATE：LZ77 + ハフマン符号の組合せ
• JPEG：DCT変換後の量子化係数をハフマン符号化
• PNG：deflate圧縮
• MP3：周波数係数のハフマン符号化

他選択肢の解説：

• a「固定長」→ × ハフマンは可変長
• c「連続値特化」→ × 離散記号の符号化が前提
• d「必ず圧縮率向上」→ × 均一頻度の場合は逆に圧縮率が悪化することもある

圧縮率の限界：

シャノンの情報源符号化定理により、平均符号長は情報エントロピー H(X) 以上にならない（下限あり）。ハフマン符号は1記号単位ではこの下限に近づくが、算術符号化（Arithmetic Coding）はさらに下限に肉迫できます。

AP午前ではアルゴリズム・データ表現分野で頻出（シラバス「基礎理論・情報理論・符号化」）。

正解は b「出現頻度の高い記号に短い符号を割り当てる可変長符号化方式である」です。

ハフマン符号化は情報理論の古典的成果ですが、現代の圧縮技術においても根幹を成すアルゴリズムで、JPEG・PNG・gzip・MP3 等の主要フォーマットで採用されています。上級者として理解すべきは「情報理論的位置づけ」「実装上のバリエーション」「現代の圧縮アルゴリズムとの関係」の3点です。

1. 情報理論的位置づけ

シャノンの情報源符号化定理（1948）は、確率分布 P(X) を持つ情報源の平均符号長 L に対して以下の下限を与えます：

```

H(X) ≤ L < H(X) + 1

```

ここで H(X) = -Σ p(x) log₂ p(x) は情報エントロピー（bit/記号）。ハフマン符号は1記号単位での符号化として最適ですが、エントロピーが小数値（例 H=2.3）の場合、1記号あたり整数bitしか割り当てられないため、平均符号長は H+1 未満に留まり、エントロピーと正確には一致しません。

2. 実装上のバリエーション

| 種類 | 特徴 | 用途 |

|---|---|---|

| 静的ハフマン | 事前に頻度集計し符号表を構築。符号表を別途送信。 | JPEG, PNG |

| 動的ハフマン（適応型） | 符号化中に符号表を更新。1パスで完了。 | gzip, LZMA |

| 正準ハフマン（Canonical Huffman） | 符号長順に並べた標準形式。符号表の格納が小さく済む。 | DEFLATE, JPEG |

| ハフマン木の長さ制限版 | 最大符号長を制限し復号速度向上。 | DEFLATE（最大15bit） |

DEFLATE（gzip/PNG）では「ハフマン符号表自体もハフマン符号で圧縮」する2段階の最適化を採用しています。

3. 算術符号化との比較

算術符号化（Arithmetic Coding）は確率分布を実数区間で表現し、1記号未満のbitで符号化できるため、エントロピーにより近づきます：

| 観点 | ハフマン | 算術符号 |

|---|---|---|

| 平均符号長 | H ≤ L < H+1 | H ≤ L < H+ε |

| 計算コスト | 高速 | 重い（特に符号化） |

| 実装複雑性 | 容易 | 複雑 |

| 特許 | フリー | かつて IBM が特許保有（期限切れ） |

算術符号化は JPEG 2000、H.264 のCABACで採用されています。

4. 現代圧縮アルゴリズムとの関係

• LZ77 / LZ78（1977）：辞書ベース圧縮。繰返しパターンを参照に置換。
• DEFLATE（1996）：LZ77 + ハフマン。gzip, ZIP, PNG で採用。
• LZMA：LZ77 + 範囲符号化（算術符号の派生）。7-Zip, xzで採用。
• Brotli（Google, 2015）：辞書事前定義 + ハフマン + 文脈モデル。Webフォント・HTTP圧縮で採用。
• Zstandard（Facebook, 2016）：ハフマンの拡張FSE（有限状態エントロピー）+ LZ77。圧縮率と速度のバランスが優秀。
• ANS（Asymmetric Numeral Systems, 2009）：ハフマンと算術符号の中間的性能。zstd, Apple LZFSE で採用。

つまり現代の主要圧縮アルゴリズムはすべて「LZ系の繰返し検出 + ハフマンまたはその後継のエントロピー符号化」というハイブリッド構造で、ハフマン符号化は依然として核心的役割を担っています。

5. JPEG / PNGでの具体的利用

• JPEG：DCT変換 → 量子化 → ジグザグスキャン → ランレングス + ハフマン符号化。ハフマン表は標準テーブルまたはカスタムテーブル。
• PNG：DEFLATEで圧縮。リテラル/長さ符号と距離符号それぞれを別々のハフマン木で符号化。

6. ハードウェア実装と並列化

ハフマン復号は「逐次的にビットを読みながら木を辿る」性質上、並列化が難しいことが指摘されています。これに対し以下の最適化があります：

• テーブルベース復号：符号最大長分のビットを先読みし、ルックアップテーブルで一気に復号
• JPEG 2000の算術符号：並列化困難だがエントロピーに近い
• GPU並列ハフマン復号：ブロック単位で独立復号

NVIDIA の nvCOMP、Intel ISA-L 等が GPU/SIMD でのハフマン復号を高速化しています。

7. データ分布と圧縮率

ハフマン符号化が効果を発揮するのは「頻度分布の偏りが大きい」場合です：

• 自然言語テキスト：英文での 'e' 出現率12.7% → 高効率
• 乱数データ：均一分布 → 圧縮効果なし（むしろメタデータで悪化）
• 既圧縮データ：ほぼ均一分布 → 再圧縮効果なし

このため「pre-compression check」として情報エントロピーを推定し、圧縮の損得を判定する実装もあります。

8. AP午後問題での出題

AP午後では「圧縮アルゴリズムの仕組み」よりも「符号化前後のサイズ計算」「効率指標の算出」が問われがちです。情報エントロピーの計算、ハフマン木の構築、圧縮率の計算は手計算で答えられるよう習熟しておきましょう。

実務的示唆：

• 自前でハフマン符号化を実装する場面はほぼなく、zstd / gzip / brotli を選択するだけ
• ストリーミングデータには適応型符号化（adaptive Huffman）が有効
• 既圧縮データ（JPEG, MP3, ZIP）の再圧縮は逆効果

ハフマン符号化は「アルゴリズムを覚える」のは初級、「情報理論の文脈で位置づけ、現代圧縮技術との関係を語れる」のが上級レベルです。