通信用語の基礎知識 IPv4
戻る
参加者募集中

シャノン・ファノ法

辞書:電算用語の基礎知識 ファイル圧縮編 (PFCP)
読み:シャノンファノほう
外語:Shannon-Fano coding 英語
品詞:固有名詞
1997/11/24 作成
2008/07/16 更新

圧縮アルゴリズムの一つで、エントロピー符号に属する。

1948(昭和23)年に、AT&Tベル研究所のシャノン(Claude Elwood Shannon)と、MITのファノ(Robert Mario Fano)がほぼ同時に考案した符号法。

このため、両者の名前を冠して、シャノン・ファノ法と呼ばれる。

用途

シャノン・ファノ法とは本来は符号法の事であるが、この符号を使い圧縮することを指す場合もある。

各符号の生起確率を求め、その順番によって符号化していく。

ロジック

{ebcedadecabd}という情報元であるならば、この情報は{a,b,c,d,e}の中から要素を選んでいることになるので、a:1/6、b:1/6、c:1/6、d:1/4、e:1/4が各生起確率の全リストとなる。

ここで生起確率によってソートし、上からの和によって二分する。上の方には0の符号を、下の方に1の符号を付ける。つまり{d,e}:0、{a,b,c}:1となる。

次に上の要素をまた生起確率によって二分すると、d:00、e:01となる。ここまでで要素が一つになったので、次は最初の試行の下の要素の符号化に移る。

下は、a:10、{b,c}:11、b:110、c:111となる。

こうしてa:10、b:110、c:111、d:00、e:01という符号が出来上がり、これで元の情報を置き換えるためのビットが割り当てられた。

現在

現在ではハフマン符号の方がより短い符号を生成することが証明されたため、使われることはまず無くなった。

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.03 (16-May-2019)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club