圧縮


1948年にShannonとFanoがほぼ同時期に考案。 ルールは次の通り。

  1. 各文字の出現頻度表を作る。
  2. 頻度によって表をソートする。
  3. 出現頻度の総和が出来るだけ等しくなるように表を分割する。
  4. 分割した上半分には0を割り当て、下半分には1を割り当てる。
  5. 2分割した表のそれぞれについて、3,4,5を繰り返し、次の記号を決めていく。それぞれの表に文字が1つしか入らないようになるまで行う。

abcebeeeccfgeddddccaaaの場合

文字頻度符号1桁目2桁目3桁目4桁目
e500--
c501--
a4100-
d4101-
b2110-
f11110
g11111

Shannon-Fano法では平均符号長が最小になるとは限らない。平均符号長最小(=エントロピー)となる符号化の代表格がHuffman符号である。


edited by A-Leo


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2005-02-07 (月) 02:14:55