シャノン・ファノ法

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

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

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

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