第6回 ハフマン符号

ハフマン符号

初めに必ず連絡事項を確認してください。

概要

解説動画

シンボルが a~f の6つだけの場合は、例えば

表1
シンボル 符号語
a 000
b 001
c 010
d 011
e 100
f 101
のようにすべてのシンボルに対して3ビットの符号語を割り当てれば重複なく符号化できる (等長符号)。
もちろんこの符号の平均符号長も3ビットになる。これはシンボルの出現確率がどうであっても変わらない。

非等長符号ではシンボルの出現率の偏りに応じて割り当てる符号語の長さを工夫すれば平均符号長を短くできる。
このうち、もっとも効率の良い、つまり平均符号長が小さくなるものをコンパクト符号という。これから見るハフマン符号もコンパクト符号の一つである。

情報源事象系が
\( X= \begin{bmatrix} x_a & x_b & x_c & x_d & x_e & x_f \cr 0.14 & 0.25 & 0.02 & 0.35 & 0.06 & 0.18 \end{bmatrix} \cdots(1) \)
の場合を例として、ハフマン符号を作る手順次を以下に示す。
① 出現率が大きい順に上からシンボルを並べ、その横に出現率を書く。
② 出現率が最小のもの・その次に小さいものをつないで節点を作る。元になったものの出現率の数字は消し、つないだ節点にそれらの和の値を書く。最小のものが2つ以上あるときはその中のどれか2つを任意に選ぶ。
③ すべてをつなぐまで同様のことを繰り返す (最後の数値は必ず1になる)。
①~③の手順を追うとこのようになる。
④ 一番左に書いた「1」を消し、枝に0, 1を割り当てる
(厳密な決まりはないが、上が0・下が1のようにルールを決めておくと間違えにくい)
これで (多少いびつだが) 符号の木の形になる。あとはこれをそれぞれ左から順に読めば、このような符号が得られる。

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

②のルールに従っても、シンボルをくっつける方法が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} \)
のような情報源事象系では、以下のどちらの符号もハフマン符号の作り方として正しい。

シンボル 符号語
a 0
b 10
c 1100
d 1110
e 11010
f 11011
g 11110
h 11111
シンボル 符号語
a 0
b 10
c 110
d 11110
e 11100
f 11101
g 111110
h 111111
シンボルに割り当てられる符号語の長さは異なるが、どちらも効率は最適化されている。平均符号長を計算してみると

左の符号では
\( \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} \)


で、確かに等しい。

課題1

表2のハフマン符号の平均符号長 \(L\) を求めよ。
課題1ヒント

(1)式にあるそれぞれのシンボルの出現率と、表2の符号語の長さをそれぞれかけて総和を求める。
等長符号の平均符号長が3ビットなので、これよりも小さい値になるはず。

課題2

シンボルが a~h の8つで、情報源事象系が
\( X= \begin{bmatrix} x_a & x_b & x_c & x_d & x_e & x_f & x_g & x_h \cr 0.05 & 0.16 & 0.07 & 0.13 & 0.18 & 0.09 & 0.11 & 0.21 \end{bmatrix} \)
である場合のハフマン符号を求めよ。ただし導出に使った符号の木も残すこと。
課題2ヒント

符号の木は枝が交差するなどかなり入り組んだ状態になるので、①の段階で広くスペースを取るとよい。
導出過程の図が汚くなってしまった場合は、それとは別の場所に④のような形 (シンボル・符号アルファベットが書かれていて、確率などの余計なものが書かれていない) で清書する。
ハフマン符号の表を書くときはシンボルを符号の木の右側のように並べ替えずに、a~h が上から順に並ぶようにする。

課題3

課題2で求めたハフマン符号の平均符号長 \(L\) を求めよ。
課題3ヒント

シンボルが8つの場合の最適な等長符号もすべての符号語の長さが3ビットになるので、平均符号長は3ビット。
ハフマン符号はコンパクト符号なので、その平均符号長は3よりも小さい値になるはず。

提出

ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は10/19(土) 正午です。提出によって出席・点数がつきます。