【知識:基礎理論】データを賢く縮める！「シャノン・ハフマンの符号化」

コンピュータが扱う「0」と「1」の組み合わせ（符号）。すべての記号を同じ長さにせず、よく出る文字には短い符号を、滅多に出ない文字には長い符号を割り当てることで、データ全体のサイズを劇的に小さくできます。

■ 符号化の基本概念

特定の規則に従って、データ（文字や数値）をビット列に変換することを符号化（エンコード）と呼びます。特に、出現確率を利用した圧縮は「エントロピー符号化」の基礎となります。

手法	手順とアルゴリズムの考え方
1. シャノン符号化 (Shannon Coding)	「上から下へ」分割する方式 1. 記号を発生確率の高い順に並べる。 2. 確率の合計がなるべく均等になるよう2つのグループに分割する。 3. 各グループに「0」と「1」を割り当てる。 4. 記号が1つになるまで分割を繰り返す。
2. ハフマン符号化 (Huffman Coding)	「下から上へ」統合する方式（より効率的） 1. 確率が低い順に2つの記号を選び、枝で結んで合計確率を持つ親ノードを作る。 2. 親ノードを新しい記号と見なし、再び低い順に2つ選ぶ作業を繰り返す（ハフマン木の作成）。 3. 根から各記号までの道筋（左右）を「0」と「1」に対応させる。

具体的な例（ハフマン符号化）

例えば、「A(60%)、B(30%)、C(10%)」という確率の記号がある場合：

• 手順： 低い「B」と「C」を合体させて1つのグループ（40%）とし、次に残った「A（60%）」と合体させます。
• 結果： 最も多い「A」には「0」などの短い符号、少ない「B」「C」には「10」「11」などの長い符号が割り当てられます。
• メリット： すべてを2ビット（AA=00, B=01, C=10）で表すより、平均ビット数が少なくなります。

試験対策の重要ポイント

• 可変長符号：記号によってビット長が異なる符号のこと。ハフマン符号はその代表例です。
• 一意復号可能：短い符号が長い符号の「接頭辞」にならない（例：Aが0なら、Bは01にできない）ように設計されており、どこで区切るか迷わずに解凍できます。
• データ圧縮：ZIPファイルやJPEG、MPEGなどの圧縮技術の根幹として使われています。

※シャノン符号化は歴史的に重要ですが、現在の実用シーンではより圧縮効率が高いハフマン符号化が主流となっています。