シャノン・ファノ法
読み：シャノンファノほう
外語：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という符号が出来上がり、これで元の情報を置き換えるためのビットが割り当てられた。
現在
現在ではハフマン符号の方がより短い符号を生成することが証明されたため、使われることはまず無くなった。
再検索