シャノン符号化

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

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

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

[編集] 符号化の原理

以上の操作を分割したデータが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