シャノン符号化

ウィキペディア

シャノン符号化

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/21 21:54 UTC 版)

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

概要

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

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

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

符号化の原理

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

例

以下の表は、a_1-6の記号の符号化の様子を示したものである。l_iは-2の累乗を示し、二進数による累積確率の小数点以下のこの桁までを符号とする。第5列は二進数による累積確率を示す。最終列がその記号の符号である。

ai	p(ai)	li	i-1までのpiの合計	p(ai)（二進数）	結果
a1	0.36	2	0.0	0.0000	00
a2	0.18	3	0.36	0.0100	010
a3	0.18	3	0.54	0.1000	100
a4	0.12	4	0.72	0.1011	1011
a5	0.09	4	0.84	0.1101	1101
a6	0.07	4	0.93	0.1110	1110