1948年に C. E. Shannon と R. M. Fano がほぼ同時期に考案した符号で、以下の特徴をもつ。

 ・ すべての符号語の長さは一定でない。
 ・ 出現確率の小さい記号に長い符号語、出現確率の大きい記号に短い符号語を割り当てる。
 ・ 符号語列から、元の記号列を一意的に復号できる。

シャノン・ファノ符号は、最初に考案された符号だが、つねに最小の平均符号長が得られるハフマン符号には圧縮性能が劣るため、その歴史的意義から情報理論の教科書に取り上げれているものの、実際のデータ圧縮アルゴリズムとしては、ほとんど使われていない。

符号語を以下のように構成できる。

 1.テキストにある各記号(文字)に対応する出現頻度リストをつくる。
 2.リストを出現頻度の降順に並び換える。
 3.リストを上下2分割する。このとき、上半分にある出現頻度の和と、下半分にある出現頻度の和がなるべく等しくなるように分割する。
 4.上半分に 0 を、下半分に 1 を割り当てる。このことは、上半分に含まれる記号に対応する符号語が 0 で始まり、下半分に含まれる記号に対応する符号語が 1 で始まることを意味する。
 5.分割して得られたそれぞれのリストは、やはり記号の出現頻度の降順で並んでいる。そこで、3. と 4. の手順でそれぞれのリストを再分割して、符号語の次の1ビットを割り当てる。この操作をそれぞれのリストに含まれる記号の数が1つになるまで繰り返す。

符号化プログラムでは、テキストを2回走査する。1回目では各記号(文字)の出現頻度を調べた上で、符号語をつくる。また復号できるように、各記号の出現頻度を符号の一部として出力する。2回目の走査では、実際に各文字を符号化する。

出力符号のフォーマットは、先頭に1文字2バイトずつの出現頻度、計 512バイトのヘッダ部と、その後に続く符号語列からなる。

なお、符号語列の終了を表すために、出現頻度が1のEOF記号(コード256)に対応する符号語を書き込む。

<関数名>
  enShannon シャノン・ファノ符号
  deShannon シャノン・ファノ符号からの復号

<形式>
  シャノン・ファノ符号
    long enShannon(unsigned char *code, long clen,
      unsigned char *text, long tlen);

  シャノン・ファノ符号からの復号
    long deShannon(unsigned char *text, long tlen,
     unsigned char *code, long clen);

<引数>
  シャノン・ファノ符号関数において
    code (入出力)シャノン・ファノ符号を格納する配列
    clen (入力) 配列codeの長さ
    text (入力) テキストを格納する配列
    tlen (入力) 配列textの長さ

  シャノン・ファノ符号からの復号関数において
    text (入出力)テキストを格納する配列
    tlen (入力) 配列textの長さ
    code (入力) シャノン・ファノ符号を格納する配列
    clen (入力) 配列codeの長さ

<関数値>
  シャノン・ファノ符号関数について
    シャノン・ファノ符号の長さ。符号化に失敗したときは -1L。

  シャノン・ファノ符号からの復号関数について
    テキストの長さ。復号に失敗したときは -1L。

用例

<関数本体>
  shannon.c

Comments are closed.

Post Navigation