通信用語の基礎知識 日本文化チャンネル桜二千人委員会 戻る

通常PC用 / 人気 更新 今日 カテ
自然科学 > 数学 > アルゴリズム > 圧縮
シャノン・ファノ法
辞書:電算用語の基礎知識 ファイル圧縮編 (PFCP)
読み:シャノンファノほう
外語:Shannon-Fano coding
品詞:固有名詞

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

目次
概要

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という符号が出来上がり、これで元の情報を置き換えるためのビットが割り当てられた。

現在

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

リンク
用語の所属
圧縮アルゴリズム
関連する用語
圧縮
ハフマン符号
生起確率
マサチューセッツ工科大学

[再検索] [戻る]


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