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

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

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

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

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

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

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

Comments are closed.

Post Navigation