ハフマン符号

●ハフマン符号とは
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
広告
カテゴリー: 基本情報技術者試験 パーマリンク