シャノン・ファノ符号化とは - わかりやすく解説 Weblio辞書

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

シャノン・ファノ符号化

(シャノン・ファノ符号から転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/31 04:39 UTC 版)

ナビゲーションに移動検索に移動

「シャノン符号化」あるいは「シャノン・ファノ・イライアス符号化」とは異なります。

6つの記号による単純な例

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

概要

記号の（推定もしくは実際の）出現確率に基づく接頭符号を使用している。同じ接頭符号でも、常に最短の符号長を表すことができ、コンパクト符号と呼ばれるハフマン符号に比べ、シャノン・ファノ符号化は最適化されていない。しかし、ハフマン符号とは違い、全ての記号のコード長が理論上の理想 ${-\log }P(x)$

シャノン・ファノ符号化のアルゴリズム

5種類の記号が以下の個数出現するデータを考える。

記号	A	B	C	D	E
個数	15	7	6	6	5
出現確率	0.38461538	0.17948718	0.15384615	0.15384615	0.12820513

記号は左から右に出現個数の順に並べてある（右図のaの状態）。ここで、BとCの間で分割をすると、左の集合は合計22個、右の集合は合計17個となる。この分割が、2つの集合の合計個数の差が最も小さくなる分割である。ここで、左の集合に含まれる記号A,Bに"0"、右の集合に含まれる記号C,D,Eに"1"を与え、それぞれの符号の1桁目とする（右図のbの状態）。

右の集合は含まれる記号が2つしかないので、AとBの間で分割して、アルゴリズムは終了となる。Aに"0"、Bに"1"を与えて符号の2桁目とし、Aの符号は"00"、Bの符号は"01"となる。左の集合はCとDの間で分割して同様に"0"、"1"を与える（右図のcの状態）。さらにD,Eの集合はDとEに分割される（右図のdの状態）。

上記の4回の分割手順により、符号木が生成される。最も頻度の高い3つの記号は全て2ビットの符号が割り当てられ、頻度の低い2つの記号には3ビットの符号が割り当てられた。