情報理論 第12回　ハフマン符号

• ハフマン符号
前回見たように、同じ文を符号化した(0, 1の並びに置き換えた) としても、符号(置き換えの対応表) によってデータ量は変わる。このうち、もっとも効率の良い、つまりデータ量の少ない符号化ができるものをコンパクト符号という。これから見るハフマン符号もコンパクト符号の一つである。

例えばシンボルが a～f の6つで、情報源符号が $X=\left[\begin{array}{cccccc}{x}_a& x_b& x_c& x_d& x_e& x_f\\ 0.14& 0.25& 0.02& 0.35& 0.06& 0.18\end{array}\right]$ なら、ハフマン符号は次の手順で作ることができる。



① 出現率が大きい順に上からシンボルを並べ、その横に出現率を書く。

② 出現率が最小のもの・その次に小さいものをつないで節点を作る。元になったものの出現率の数字は消し、つないだ節点にそれらの和の値を書く。 (最小のものが2つ以上あるときはその中のどれか2つを任意に選ぶ)

③～⑥ すべてをつなぐまで同様のことを繰り返す (最後の数値は必ず1になる)。

⑦ 枝に0, 1を割り当てる

これで (多少いびつだが) 符号の木の形になる。あとはこれをそれぞれ左から順に読めば、このような符号が得られる。

シンボル	符号語
a	110
b	01
c	1111
d	00
e	1110
f	10



②のルールに従っても、シンボルをくっつける方法が1通りに決まらないこともある。例えば $X=\left[\begin{array}{cccc}{x}_a& x_b& x_c& x_d\\ 0.25& 0.25& 0.25& 0.25\end{array}\right]$ なら、以下の組み合わせ方はどれも正しい。



• 練習問題1
上の例の条件で、a～f を扱える最短の等長符号と、その平均符号長 $L$ を求めよ (必要なのは表と数値)。


• 練習問題2
上の例で求めたハフマン符号の平均符号長 $L$ を求めよ。


• 練習問題3
a～h の8つのシンボルを扱える最短の等長符号と、その平均符号長 $L$ を求めよ (必要なのは表と数値)。


• 練習問題4
シンボルが a～h の8つで、情報源事象系が $X=\left[\begin{array}{cccccccc}{x}_a& x_b& x_c& x_d& x_e& x_f& x_g& x_h\\ 0.05& 0.16& 0.07& 0.13& 0.18& 0.09& 0.11& 0.21\end{array}\right]$ である場合のハフマン符号を求めよ。また、その平均符号長 $L$ を求めよ (必要なのは図、表、数値)。


• 練習問題5
シンボルが a～h の8つで、情報源事象系が $X=\left[\begin{array}{cccccccc}{x}_a& x_b& x_c& x_d& x_e& x_f& x_g& x_h\\ 0.01& 0.03& 0.45& 0.03& 0.07& 0.02& 0.04& 0.35\end{array}\right]$ である場合のハフマン符号を2通り求めよ。また、その平均符号長 $L$ を求めよ (必要なのは図x2、表x2、数値x1)。

ここでいう「2通り」とは、最長の符号語の長さが異なる、構造的に異なったもの2つということ。
aとfをつないだものは(0.03)になる。この時点で(0.03)は「b」「d」「aとf」の3つあり、どれをつなぐかで全体の構造が変わる。