「シャノン符号化」あるいは「シャノン・ファノ・イライアス符号化」とは異なります。
6つの記号による単純な例

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

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

この符号化法は1948年のシャノンの情報理論の記事『通信の数学的理論』の中で提案された。この符号化法はファノによるもので、ファノは後にテクニカルレポート（英語版）として発表している[1]。

シャノン・ファノ符号化は、シャノンの情報源符号化定理の証明のために用いられたシャノン符号化や、算術符号の先駆者であるシャノン・ファノ・イライアス符号化（英語版）（またはイライアス符号化）とは異なる。
符号化の原理
記号を出現確率の高い物から低い物の順に並べ替える。

それぞれの集合の確率の合計ができるだけ等しくなるようなところで二分割する。

分割した片方の集合に"0"、もう片方の集合に"1"を割り当て、符号の1桁目とする。

分割して出来た2つの集合をそれぞれ更に二分割し、同様に0と1を割り当てる。

この操作を、各集合に含まれる記号が1つになるまで行うと、それぞれの記号の符号が得られる。

このアルゴリズムは、かなり効率の良い可変長の符号を生成する。分割によって作られた2つの集号は、実際にほぼ等しい出現確率がある。それらを識別するのに用いられる1ビットの情報は、最も効率的に使われる。残念なことに、シャノン・ファノ符号化は常に最短の符号を表すとは限らない。{0.35, 0.17, 0.17, 0.16, 0.15}という出現確率の集合からは、シャノン・ファノ符号化では最適化されていない符号が生成される。

この理由から、シャノン・ファノ符号化が用いられることは少ない。多くの場合はハフマン符号、あるいは算術符号やRange Coderが用いられる。
例シャノン・ファノ符号化のアルゴリズム

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

記号ABCDE
個数157665
出現確率0.384615380.179487180.153846150.153846150.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ビットの符号が割り当てられた。

記号ABCDE
符号000110110111

1文字あたりの平均符号長は 2 bits ⋅ ( 15 + 7 + 6 ) + 3 bits ⋅ ( 6 + 5 ) 39 symbols ≈ 2.28 bits per symbol. {\displaystyle {\frac {2\,{\text{bits}}\cdot (15+7+6)+3\,{\text{bits}}\cdot (6+5)}{39\,{\text{symbols}}}}\approx 2.28\,{\text{bits per symbol.}}}

となる。
脚注^ Fano 1949

参考文献

Shannon, C.E. (July 1948). ⇒“A Mathematical Theory of Communication”. Bell System Technical Journal 27: 379?423. ⇒http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf. 

Fano, R.M. (1949). “The transmission of information”. Technical Report No. 65 (アメリカ合衆国マサチューセッツ州ケンブリッジ: MIT電子工学研究所). 

外部リンク

⇒Shannon?Fano at Binary Essence

表

話

編

歴
データ圧縮方式
可逆

エントロピー符号

一進法

算術

Asymmetric numeral systems（英語版）

ゴロム

ハフマン

適応型（英語版）

正準（英語版）

MH


レンジ

シャノン

シャノン・ファノ

シャノン・ファノ・イライアス（英語版）

タンストール（英語版）

ユニバーサル（英語版）

指数ゴロム（英語版）

フィボナッチ（英語版）

ガンマ

レーベンシュタイン（英語版）


辞書式（英語版）

BPE

Deflate

Lempel-Ziv

LZ77

LZ78

LZFSE

LZH

LZJB（英語版）

LZMA

LZO

LZRW（英語版）

LZS（英語版）

LZSS

LZW

LZWL（英語版）

LZX

LZ4

ROLZ（英語版）

統計型（英語版）

Brotli

Snappy

Zstandard


その他

BWT

CTW（英語版）

Delta

DMC（英語版）

MTF

PAQ

PPM

RLE


音声

理論

ビットレート

平均(ABR)

固定(CBR)

可変(VBR)


コンパンディング

畳み込み

ダイナミックレンジ

レイテンシ（英語版）

標本化定理

標本化

音質

音声符号化

サブバンド符号化

変換符号化

知覚符号化

コーデック

A-law

μ-law

ACELP

ADPCM

CELP

DPCM

フーリエ変換

LPC

LAR

LSP