シャノン・ファノ符号化のソースを表示

{{混同|シャノン符号化|シャノン・ファノ・イライアス符号化}}

[[File:Fano-en.svg|thumb|300x300px|6つの記号による単純な例]]
'''シャノン・ファノ符号化'''（シャノン・ファノふごうか）とは、1948年に[[クロード・シャノン]]と[[ロベルト・ファノ]]によって考案された[[可逆圧縮]]の方法である。

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

この符号化法は1948年のシャノンの[[情報理論]]の記事『[[通信の数学的理論]]』の中で提案された。この符号化法はファノによるもので、ファノは後に{{仮リンク|テクニカルレポート|en|technical report}}として発表している<ref>{{harvnb|Fano|1949}}</ref>。

シャノン・ファノ符号化は、[[シャノンの情報源符号化定理]]の証明のために用いられた[[シャノン符号化]]や、[[算術符号]]の先駆者である{{仮リンク|シャノン・ファノ・イライアス符号化|en|Shannon–Fano–Elias coding}}（またはイライアス符号化）とは異なる。

==符号化の原理==
#記号を出現確率の高い物から低い物の順に並べ替える。
#それぞれの集合の確率の合計ができるだけ等しくなるようなところで二分割する。
#分割した片方の集合に"0"、もう片方の集合に"1"を割り当て、符号の1桁目とする。
#分割して出来た2つの集合をそれぞれ更に二分割し、同様に0と1を割り当てる。
この操作を、各集合に含まれる記号が1つになるまで行うと、それぞれの記号の符号が得られる。

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

この理由から、シャノン・ファノ符号化が用いられることは少ない。多くの場合はハフマン符号、あるいは[[算術符号]]や[[Range Coder]]が用いられる<!--
が、[[gzip]]では[[LZ77]]とシャノン・ファノ符号によって圧縮を行っている
-->。

===例===
[[Image:ShannonCodeAlg.svg|right|thumb|300px|シャノン・ファノ符号化のアルゴリズム]]
5種類の記号が以下の個数出現するデータを考える。
:{| class="wikitable"
! 記号
! 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ビットの符号が割り当てられた。
:{| class="wikitable"
! 記号
! A
! B
! C
! D
! E
|-
| 符号
| 00
| 01
| 10
| 110
| 111
|}
1文字あたりの平均符号長は
:<math>\frac{2\,\text{bits}\cdot(15+7+6) + 3\,\text{bits} \cdot (6+5)}{39\, \text{symbols}} \approx 2.28\,\text{bits per symbol.}</math>
となる。

==脚注==
{{reflist}}

==参考文献==
* {{cite journal | first = C.E. | last = Shannon | url = http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf | title = A Mathematical Theory of Communication | journal = [[Bell System Technical Journal]] | volume = 27 | pages = 379–423 |date=July 1948}}
* {{cite journal | first = R.M. | last = Fano | title = The transmission of information | work = Technical Report No. 65 | year = 1949 | publisher = [[MIT電子工学研究所]] | location = アメリカ合衆国マサチューセッツ州ケンブリッジ | ref =harv}}

==外部リンク==
*[http://www.binaryessence.com/dct/en000041.htm Shannon–Fano at Binary Essence]

{{データ圧縮}}
{{デフォルトソート:しやのんふあのふこうか}}
[[Category:データ圧縮]]
[[Category:クロード・シャノン]]
[[Category:エポニム]]