非等長符号ではシンボルの出現率の偏りに応じて割り当てる符号語の長さを工夫すれば平均符号長を短くできます。
このうち、もっとも効率の良い、つまり平均符号長が小さくなるものをコンパクト符号といいます。これから見るハフマン符号もコンパクト符号の一つです。
情報源事象系が
| \( X= \begin{bmatrix} 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{bmatrix} \) |
シンボルが6種類なので、等長符号では符号語が重複しないようにするためにはたとえばこのように最低3bit必要になります。
表1
| シンボル | 符号語 |
|---|---|
| a | 000 |
| b | 001 |
| c | 010 |
| d | 011 |
| e | 100 |
| f | 101 |
ハフマン符号を作る手順を以下に示します。
① 出現率が大きい順に上からシンボルを並べ、その横に出現率を書く
② 出現率が最小のもの・その次に小さいものをつないで節点を作る。元になったものの出現率の数字は消し、つないだ節点にそれらの和の値を書く。最小のものが2つ以上あるときはその中のどれか2つを任意に選ぶ
③ すべてをつなぐまで同様のことを繰り返す (最後の数値は必ず1になる)
(厳密な決まりはありませんが、上が0・下が1のようにルールを決めておくと間違えにくいです)
これで符号の木の完成です。あとはこれをそれぞれ左から順に読めば、このような符号が得られます。② 出現率が最小のもの・その次に小さいものをつないで節点を作る。元になったものの出現率の数字は消し、つないだ節点にそれらの和の値を書く。最小のものが2つ以上あるときはその中のどれか2つを任意に選ぶ
③ すべてをつなぐまで同様のことを繰り返す (最後の数値は必ず1になる)
①～③の手順を追うとこのようになります。
④ 一番左に書いた「1」を消し、枝に0, 1を割り当てる
|
|
(厳密な決まりはありませんが、上が0・下が1のようにルールを決めておくと間違えにくいです)
表2
| シンボル | 符号語 |
|---|---|
| a | 110 |
| b | 01 |
| c | 1111 |
| d | 00 |
| e | 1110 |
| f | 10 |
\(L=0.14\times3+0.25\times2+0.02\times4+0.35\times2+0.06\times4+0.18\times2\)
\(=(0.25+0.35+0.18)\times2+0.14\times3+(0.02+0.06)\times4\)
\(=2.30\) (bit)
\(=(0.25+0.35+0.18)\times2+0.14\times3+(0.02+0.06)\times4\)
\(=2.30\) (bit)
②のルールに従っても、シンボルをくっつける方法が1通りに決まらないこともあります。例えば
のような情報源事象系では、以下のどちらの符号もハフマン符号の作り方として正しいものです。
シンボルに割り当てられる符号語の長さは異っていますが、どちらも効率は最適化されています。平均符号長を計算してみると
左の符号では
右の符号では
で、等しくなることが確かめられます。
| \( X= \begin{bmatrix} x_a & x_b & x_c & x_d & x_e & x_f & x_g & x_h \\ 0.45 & 0.35 & 0.07 & 0.04 & 0.03 & 0.03 & 0.02 & 0.01 \end{bmatrix} \) |
|
|
||||||||||||||||||||||||||||||||||||
|
|
左の符号では
| \( \begin{eqnarray} L&&=0.45+0.35\times2+(0.07+0.04)\times4+(0.03+0.03+0.02+0.01)\times5\\ &&=0.45+0.7+0.44+0.45\\ &&=2.04 (ビット) \end{eqnarray} \) |
右の符号では
| \( \begin{eqnarray} L&&=0.45+0.35\times2+0.07\times3+(0.04+0.03+0.03)\times5+(0.02+0.01)\times6\\ &&=0.45+0.7+0.21+0.5+0.18\\ &&=2.04 (ビット) \end{eqnarray} \) |
で、等しくなることが確かめられます。