シャノン符号化

シャノン符号化（シャノンふごうか、Shannon coding）は、クロード・シャノンによって考案された、可逆圧縮の方法である。

概要編集

記号の（推定もしくは実際の）出現確率に基づく接頭符号を使用している。同じ接頭符号でも、常に最短の符号長を表すことができるハフマン符号に比べ、シャノン符号化は最適化されていない。シャノン・ファノ符号化とは同程度かそれより劣る。

シャノン符号化は接頭符号の最初のもので、1948年のシャノンの記事『通信の数学的理論』でシャノンの情報源符号化定理の証明のために用いられた^[1]。

この符号化法は情報理論の分野に進歩をもたらした。そして、シャノン符号化を元にして多くの符号化が生み出された（シャノン・ファノ符号化、ハフマン符号、算術符号など）我々の日々の生活はデジタルデータに大きく影響されているが、これは、シャノン符号化やその後継の符号化の恩恵なくしては不可能である。

記号を出現確率の高い順に並べる。
それぞれの記号について、その1つ前の記号までの累積の確率を求める。( $\sum \limits _{i=k}^{i-1}p_{k}(x)$ )
2.の値を二進数にする。
3.の値の $l_{i}=\left\lceil -\log _{2}p_{i}(x)\right\rceil$ 桁までをその記号の符号とする（ $\lceil x\rceil$ は切り上げを意味する）。