●ハフマン符号とは
1952年にDavid A. Huffmanによって開発された符号である。
データ圧縮方法の一つであり、JPEGやLHAなどの圧縮フォーマットで使用されている。
●符号化の原理
ハフマン符号化の原理は、出現確率の高い文字を少ないビット数で表すことによって、
データ中の1文字当たりの平均ビット数を少なくするということである。
ハフマン符号化では、次のような方法で符号の割り当てをおこなう。
出現確率の低いほうから2つずつまとめ、新しい集合と考える。
この新しい集合の出現確率は、それを構成する各要素の出現確率の和である。
そして、新たな集合とのこりの要素から、つぎの符号化対象データとし、
再び出現確率の低いほうから2つずつまとめ、新たな集合を作る操作をおこなう。
この操作を繰り返し、最終的に2つの集合となったとき、
0と1のビット表現を割り当てる。ここで、各要素に表現ビットを割り当てる方法は任意である。
そして、ビット表現が割り当てられたものが集合の場合は、
ビット表現の最後に0と1を加えてその構成要素を区別する。
このとき0と1の割り当て方法は、上記の方法に準ずる。
これを、最初に与えた要素すべてに符号が割り当てられるまで繰り返す。
以下に具体例を示す。
例題:
a, bに入るべき字句を答えよ。
ただし、出現確率の高いほうに0ビットを割り当てるとする。
文字 出現確率 ビット表現
I 0.3 00
J 0.15 a
K 0.08 111
L 0.1 110
M 0.25 b
N 0.12 011
解説:
出現確率がもっとも低いのは、KとLである。
これを集合として考えると、
文字 出現確率
I 0.3
J 0.15
I 0.3
J 0.15
KL 0.18
M 0.25
N 0.12
M 0.25
N 0.12
つぎに、出現確率が低いのは、JとNである。
文字 出現確率
I 0.3
JN 0.27
I 0.3
JN 0.27
KL 0.18
M 0.25
M 0.25
これを繰り返していくと、
文字 出現確率
I 0.3
JN 0.27
I 0.3
JN 0.27
KLM 0.43
↓
文字 出現確率
JNI 0.57 ←0を割り当てる
JNI 0.57 ←0を割り当てる
KLM 0.43 ←1を割り当てる
・JNIに着目
文字 出現確率
I 0.3 ←0を割り当てる
JN 0.27 ←1を割り当てる
I 0.3 ←0を割り当てる
JN 0.27 ←1を割り当てる
文字 出現確率
J 0.15 ←0を割り当てる
N 0.12 ←1を割り当てる
J 0.15 ←0を割り当てる
N 0.12 ←1を割り当てる
・KLMに着目
文字 出現確率
KL 0.18 ←1を割り当てる
M 0.25 ←0を割り当てる
M 0.25 ←0を割り当てる
文字 出現確率
K 0.08 ←1を割り当てる
L 0.1 ←0を割り当てる
K 0.08 ←1を割り当てる
L 0.1 ←0を割り当てる
これらをまとめると、
文字 出現確率 ビット表現
I 0.3 00
J 0.15 010
K 0.08 111
L 0.1 110
M 0.25 10
N 0.12 011
I 0.3 00
J 0.15 010
K 0.08 111
L 0.1 110
M 0.25 10
N 0.12 011
となる。
したがって、
(答え)
a.010
b.10