Category Archives: C言語・符号

1960年代に P. Elias によって考案された符号が、記号（文字）列全体を１つの符号語にするもので、符号化や復号化に算術演算（四則演算）によって実行されることから算術符号と総称されている。算術符号は幅広く研究がなされるようになったのは1970年代の後半であり、当時では一般的にあまり知られていなかった。

算術符号は理論上、平均符号長がエントロピーとなる。つまり、平均符号長に関しては、算術符号は最適符号だ。これに対して、よく知られている ハフマン符号はその平均符号長は必ずしもエントロピーにならない。しかし算術符号においては、符号化の際、無限桁の実数演算が理論上必要となるので、実用上有限桁の整数で近似する工夫が必要であろう。

算術符号は入力記号（文字）の出現確率に基づいて単位区間 [0, 1)（左端が0 を含み、右端が1を含まない区間）を逐次縮小し、最終的に得られた区間内の値を符号とする符号である。ハフマン符号では出現確率の大きい記号に短い符号語を割り当てるのに対して、算術符号では、出現確率の大きい文字に幅の大きい区間を振り分ける。

＜関数名＞
　　enArith 算術符号
　　deArith 算術符号からの復号

＜形式＞
　　算術符号
　　　　long enArith(unsigned char *code, long clen,
　　　　 unsigned char *text, long tlen);

　　算術符号からの復号
　　　　long deArith(unsigned char *text, long tlen,
　　　　 unsigned char *code, long clen);

＜引数＞
　　算術符号関数において
　　　　code （入出力）算術符号を格納する配列
　　　　clen （入力）　配列codeの長さ
　　　　text （入力）　テキストを格納する配列
　　　　tlen （入力）　配列textの長さ

　　算術符号からの復号関数において
　　　　text （入出力）テキストを格納する配列
　　　　tlen （入力）　配列textの長さ
　　　　code （入力）　算術符号を格納する配列
　　　　clen （入力）　配列codeの長さ

＜関数値＞
　　算術符号関数について
　　　　算術符号の長さ。符号化に失敗したときは -1L。

　　算術符号からの復号関数について
　　　　テキストの長さ。復号に失敗したときは -1L。

＜用例＞

＜関数本体＞
　　arithmetic.c

1952年に D. A. Huffman によって考案された符号で、以下の特徴をもつ。

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

ハフマン符号を以下のように構成できる。

　１．テキストにある各記号（文字）に対応するノードをつくる。それぞれのノードには、その記号の出現頻度を書き込む。
　２．出現頻度のもっとも小さい２つのノードに対し、親ノードをつくり、一方に 0 のラベル、他方に 1 のラベルをつける。また親ノードに、子ノードの出現頻度の和を書き込む。この親ノードは以降、子ノードの代わりとなる。
　３．残りのノードと親ノードから、ノードの数が１つになるまで、 2. の処理を繰り返す。
　４・ルートから記号に対応するノードまで枝をたどったときに得られる 0、1 のラベル列がその記号に対する符号語となる。また、このように構成される符号の木を、ハフマン木と呼ぶ。

実際の符号化プログラムでは、テキストを２回走査する。１回目では各記号（文字）の出現頻度を調べた上で、ハフマン木をつくる。また復号できるように、各記号の出現頻度を符号の一部として出力する。２回目の走査では、ハフマン木をはどりながら各文字を符号化する。

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

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

＜関数名＞
　　enHuffman　ハフマン符号
　　deHuffman　ハフマン符号からの復号

＜形式＞
　　ハフマン符号
　　　　long enHuffman(unsigned char *code, long clen,
　　　　 unsigned char *text, long tlen);

　　ハフマン符号からの復号
　　　　long deHuffman(unsigned char *text, long tlen,
　　　　 unsigned char *code, long clen);

＜引数＞
　　ハフマン符号関数において
　　　　code （入出力）ハフマン符号を格納する配列
　　　　clen （入力）　配列codeの長さ
　　　　text （入力）　テキストを格納する配列
　　　　tlen （入力）　配列textの長さ

　　ハフマン符号からの復号関数において
　　　　text （入出力）テキストを格納する配列
　　　　tlen （入力）　配列textの長さ
　　　　code （入力）　ハフマン符号を格納する配列
　　　　clen （入力）　配列codeの長さ

＜関数値＞
　　ハフマン符号関数について
　　　　ハフマン符号の長さ。符号化に失敗したときは -1L。

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

＜用例＞

＜関数本体＞
　　huffman.c

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

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

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

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

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

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

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

なお、符号語列の終了を表すために、出現頻度が１の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