ハフマン符号

●ハフマン符号とは

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　　　　　　　　 

KL　　　　　   0.18
M　　　　　    0.25　　　　　         
N　　　　　    0.12　　　　　         

 

つぎに、出現確率が低いのは、JとNである。

 

文字　　　　　出現確率　　　　　
I　　　　　　　　0.3　　　　　　　　   
JN　　　　　   0.27　　　　　　　　 

KL　　　　　   0.18
M　　　　　    0.25　　　　　         

 

これを繰り返していくと、

 

文字　　　　　出現確率　　　　　
I　　　　　　　　0.3　　　　　　　　   
JN　　　　　   0.27　　　　　　　　 

KLM　　　　　0.43

 

　　　　↓

 

文字　　　　　出現確率　　　　　　   
JNI　　　　　   0.57　　　　　　←0を割り当てる　　 

KLM　　　　　0.43　　　　　　 ←1を割り当てる

 

・JNIに着目

文字　　　　　出現確率　　　　　
I　　　　　　　　0.3　　　　　　　←0を割り当てる　　　　　　　   
JN　　　　　   0.27　　　　　　←1を割り当てる

 

文字　　　　　出現確率　　　　　　　　   
J　　　　　　   0.15 　　　　　　←0を割り当てる
N　　　　　    0.12　　　　　    ←1を割り当てる

 

・KLMに着目

文字　　　　　出現確率　　

KL　　　　　   0.18　　　　　　←1を割り当てる
M　　　　　    0.25　　　　　　←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

 

となる。

したがって、

(答え)

a.010

b.10