データ構造入門：ハフマン符号とエントロピーの基本を徹底解説

データ構造と情報理論の分野では、効率的なデータ圧縮を実現するための重要な概念として「ハフマン符号」と「エントロピー」があります。本記事では、ハフマン符号の基本的な仕組みと歴史、そしてシャノンエントロピーの理論的背景から具体的な計算方法までを、わかりやすく解説します。

ハフマン符号とは

ハフマン符号とは、可逆データ圧縮（ロスレス圧縮）で広く利用されている「最適な接頭辞符号（プレフィックスコード）」の一種です。

この符号を構成する手法は「ハフマン符号化」と呼ばれ、David A. Huffman（デイビッド・ハフマン）がMITの博士課程（Sc.D.）在学中に考案し、1952年の論文「A Method for the Construction of Minimum-Redundancy Codes（最小冗長符号の構成方法）」で発表しました。

ハフマンのアルゴリズムが出力するのは、ファイル内の文字などの元記号を符号化するための可変長コード表です。この表は、各記号の出現確率や出現頻度（重み）の推定値をもとに生成されます。他のエントロピー符号化手法と同様に、出現頻度の高い記号ほど少ないビット数で表現され、出現頻度の低い記号には多くのビットが割り当てられます。

さらに、ハフマン法は効率的に実装でき、重みが事前にソートされていれば、入力された重みの数に対して線形時間で符号を求めることができます。

エントロピーとは

情報理論において、シャノンの源符号化定理（ノイズレス符号化定理とも呼ばれます）は、データ圧縮の理論的な限界と、シャノンエントロピーの操作的な意味を示したものです。

この定理によれば、独立かつ同一の確率分布に従う（i.i.d.）データ列の長さが無限大に近づく極限において、情報の損失がほぼ確実に発生しない範囲では、符号化レート（記号あたりの平均ビット数）を源のシャノンエントロピーより小さく圧縮することは不可能です。一方で、損失の確率を無視できる程度に抑えながら、シャノンエントロピーに限りなく近い符号化レートを実現することは可能です。

情報エントロピーとは、「データの確率的な発生源が生み出す情報の平均的な割合」として定義されます。

確率変数のエントロピーを計算する

確率変数にどれほどの情報が含まれているのかを計算することもできます。

たとえば、確率分布pに従う確率変数Xの情報量を求める場合、H(X)のように関数H()を用いて表記します。

本質的に、確率変数の情報量を計算することは、その確率変数が取りうる事象の確率分布について情報量を計算することと同じです。

確率変数について計算された情報量は、「情報エントロピー」「シャノンエントロピー」、あるいは単に「エントロピー」と呼ばれます。

この名称は物理学におけるエントロピーの概念へのアナロジーであり、どちらも「不確実性」を扱う点で共通しています。

エントロピーの直感的な意味は、「確率変数の確率分布から抽出される事象を表現・伝送するために必要な平均ビット数」です。

分布のシャノンエントロピーは、その分布から抽出される事象が持つ期待情報量として定義されます。言い換えれば、分布Pから抽出される記号を符号化する際に必要となる平均ビット数の下限を与えます。

K個の離散状態kを持つ確率変数Xのエントロピーは、次の式で計算できます。

H(X) = -Σ ( p(k) × log(p(k)) )　※k ∈ K

これは「各事象の確率と、その確率の対数の積をすべての事象について足し合わせ、全体にマイナスの符号を付けたもの」を意味します。

情報量の場合と同様に、log()は底2の対数を使用し、単位はビットになります。自然対数を用いることも可能です。

エントロピーが最小になるのは、確率1.0の事象（確定事象）しか持たない確率変数の場合です。逆に、すべての事象が等しい確率で発生するとき、エントロピーは最大になります。