シャノン符号化

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

シャノン符号とは、1948年にクロード・シャノンによって考案された符号である。 ほぼ同時期にロベルト・ファノによっても考案されたため、シャノン・ファノ符号ともいうが、この記事ではシャノン符号で統一する。

シャノン符号は常に最短の符号長を表すとは限らない。それに対し、ハフマン符号は常に最短の符号長を表すことができ、コンパクト符号と呼ばれる。

この符号が用いられることは少なく、多くの場合はハフマン符号、あるいは算術符号Range Coderが用いられる。

符号化の原理[編集]

  1. 圧縮したいデータに出現する記号の個数を求め、その個数で記号をソートする。
  2. ソートしたデータを、なるべく総数が等しくなるようなところで二分割する。分割した片方のデータに0、もう片方のデータに1を割り当てる。
  3. 分割して出来た2つのデータをそれぞれ更に二分割していき、同様に0と1を割り当てていく。

以上の操作を分割したデータが1つになるまで行う。それにより、記号の個数に反比例した長さの符号が得られる。

符号化の原理上、各記号の出現頻度をあらかじめ知っておく必要がある。

[編集]

Aが5個、Bが3個、Cが7個、Dが1個出現するデータを考える。

AAAAABBBCCCCCCCD

個数の順にソートすると、C→A→B→Dの順になるので、以下のように並び変わる。

CCCCCCCAAAAABBBD

なるべく個数が等しくなるよう分割するには、C(7個)とそれ以外(9個)に分ければよいので、以下の様になる。

CCCCCCC AAAAABBBD
<  0  >|<   1   >

続いて、この右半分(「1」を割り当てられた区間)については、A(5個)とそれ以外(4個)に分ければよいので、以下の様になる。

CCCCCCC AAAAA BBBD
<  0  >|<    1   >
       |< 0 >|< 1>

最後に、BとDに分けて符号化が完了となる。

CCCCCCC AAAAA BBB  D
<  0  >|<     1     >
       |< 0 >|<  1  >
             |<0>|<1>

以上より、符号化の結果は以下の様になる。

A ... 10
B ... 110
C ... 0
D ... 111

関連項目[編集]